408964: GYM103389 H 4G网络

经过多年的努力，比特镇终于实现了3G网络的全域覆盖，工程师小C想趁热打铁推行4G网络，进一步提高比特镇人民的生活水平。

比特镇可以被视为一个充分大的二维平面，工程师小C敲定了 $$$n$$$ 个建立4G网络基站的位置，每个基站能够实现以基站为圆心的半径为 $$$r$$$ 的圆内区域的4G网络覆盖。

由于4G网络部署的成本远高于3G网络，工程师小C准备对 $$$q$$$ 个方案进行调研，每个方案分别给出了4G网络基站覆盖范围的半径 $$$r$$$ 的具体数值。

现在工程师小C想知道，在每个方案中，比特镇4G网络覆盖范围的面积与这 $$$n$$$ 个基站的4G网络覆盖范围的面积之和的比值。

更形式化地描述这个问题，记 $$$n$$$ 个4G网络基站的位置分别为 $$$(x_1,y_1),(x_2,y_2),\ldots,(x_n, y_n)$$$，定义 $$$C_{i,r} = \{(x,y) \in \mathbb{R}^2 \mid (x-x_i)^2+(y-y_i)^2 \le r^2\}$$$ 为第 $$$i$$$ 个4G网络基站覆盖的范围，你需要分别计算

$$$$$$f(r) = \frac{S(C_{1,r} \cup C_{2,r} \cup \ldots \cup C_{n,r})}{S(C_{1,r})+S(C_{2,r})+\ldots+S(C_{n,r})} $$$$$$当 $$$r = r_1, r_2, \ldots, r_q$$$ 时 $$$f(r)$$$ 的值 $$$f(r_1), f(r_2), \ldots, f(r_q)$$$，其中 $$$S(X)$$$ 表示平面点集 $$$X$$$ 的面积。

第一行包含一个正整数 $$$n$$$ ($$$1 \le n \le 2\,000$$$)，表示4G网络基站的个数。

接下来 $$$n$$$ 行，每行包含两个整数 $$$x,y$$$ ($$$-10\,000 \le x,y \le 10\,000$$$)，表示4G网络基站建立的位置，保证任意两个4G网络基站都不建在同一处。

下一行包含一个正整数 $$$q$$$ ($$$1 \le q \le 2\,000$$$)，表示方案的个数。

接下来 $$$q$$$ 行，第 $$$i$$$ 包含一个整数 $$$r_i$$$ ($$$1 \le r_i \le 20\,000$$$)，表示第 $$$i$$$ 个方案中每个4G网络基站覆盖范围的半径。

输出 $$$q$$$ 行，第 $$$i$$$ 行包含一个实数表示 $$$f(r_i)$$$，要求绝对误差不超过 $$$10^{-9}$$$。

也就是说，如果你给出的答案是 $$$a$$$，标程给出的答案是 $$$b$$$，你的答案被认为是正确的当且仅当 $$$|a - b| \le 10^{-9}$$$。

1
0 0
1
1

1.000000000000000

2
0 0
0 1
1
1

0.804498890522115

3
0 0
0 1
1 0
1
1

0.725769222409340

4
0 0
0 1
1 0
1 1
1
1

0.634076362068062