Preparing NOJ

4G网络

8000ms 524288K

Description:

经过多年的努力,比特镇终于实现了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$$$ 的面积。

Input:

第一行包含一个正整数 $$$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网络基站覆盖范围的半径。

Output:

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

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

Sample Input:

1
0 0
1
1

Sample Output:

1.000000000000000

Sample Input:

2
0 0
0 1
1
1

Sample Output:

0.804498890522115

Sample Input:

3
0 0
0 1
1 0
1
1

Sample Output:

0.725769222409340

Sample Input:

4
0 0
0 1
1 0
1 1
1
1

Sample Output:

0.634076362068062

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389H

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:34

Related

Nothing Yet