Preparing NOJ

3G网络

1000ms 524288K

Description:

比特镇建镇多年一直没有通网,工程师小C为了改善比特镇人民的生活,立下了宏伟的目标,致力于比特镇3G网络全域覆盖的实现。

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

现在工程师小C想知道,当 $$$r$$$ 足够大以至于比特镇的每一个角落都有3G网络覆盖时,比特镇3G网络覆盖范围的面积与这 $$$n$$$ 个基站的3G网络覆盖范围的面积之和的比值。

更形式化地描述这个问题,记 $$$n$$$ 个3G网络基站的位置分别为 $$$(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$$$ 个3G网络基站覆盖的范围,你需要计算

$$$$$$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 \rightarrow +\infty$$$ 时 $$$f(r)$$$ 的极限 $$$\lim_{r \rightarrow +\infty} f(r)$$$,其中 $$$S(X)$$$ 表示平面点集 $$$X$$$ 的面积。

Input:

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

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

Output:

输出一行,包含一个实数表示 $$$\lim_{r \rightarrow +\infty} f(r)$$$,要求绝对误差不超过 $$$10^{-9}$$$。

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

Sample Input:

1
0 0

Sample Output:

1.000000000000000

Sample Input:

2
0 0
0 1

Sample Output:

0.500000000000000

Sample Input:

3
0 0
0 1
1 0

Sample Output:

0.333333333333333

Sample Input:

4
0 0
0 1
1 0
1 1

Sample Output:

0.250000000000000

Info

CodeForces Gym

Provider CodeForces Gym

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

Code GYM103389G

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:31

Related

Nothing Yet