#P3496. PA2010 The Goat

    ID: 2708 传统题 2000ms 256MiB 尝试: 9 已通过: 4 难度: 9 上传者: 标签>难度分类省选/NOI-概率与期望指示变量期望线性性补事件计算计算几何圆相交排序与序列处理环形区间拆分离线与分治事件排序扫描中维护贡献格林公式CF2600鸣谢xyz111提供SPJ

PA2010 The Goat

The Goat

题目描述

Bajtazar 在一片没有边界的草场上钉了 nn 根木桩。接下来 kk 天,他每天上午独立地等概率挑选一根木桩,将山羊用一根长为 rr 的绳子拴在那里。同一根木桩可以在多天被选中。

山羊当天会吃掉以所选木桩为圆心、半径为 rr 的圆盘中的全部草。吃掉的草不会再长出来。

求 kk 天后,已经被吃掉的草所覆盖的总面积的期望。

输入格式

第一行有三个整数 n,k,rn,k,r。

接下来 nn 行,每行有两个整数 xi,yix_i,y_i,表示第 ii 根木桩的位置。任意两根木桩的位置不同。

输出格式

输出一行一个实数,表示所求期望。绝对误差不超过 10−610^{-6}。小数点后至多写 2020 位。

样例 #1

2 2 1
0 0
1 0
4.098204131080311

两天选中同一根木桩和选中不同木桩的概率各为 12\tfrac12。前一种情况下总面积为 π\pi,后一种为 4π3+32\tfrac{4\pi}{3}+\tfrac{\sqrt3}{2},因此期望为 7π6+34\tfrac{7\pi}{6}+\tfrac{\sqrt3}{4}。

数据范围

1≤n,k,r≤10001\le n,k,r\le 1000,−1000≤xi,yi≤1000-1000\le x_i,y_i\le 1000。