G - 3G网络

· · 个人记录 

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

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

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

更形式化地描述这个问题，记 nnn 个3G网络基站的位置分别为 (x1,y1),(x2,y2),…,(xn,yn)(x_1,y_1),(x_2,y_2),\ldots,(x_n, y_n)(x1​,y1​),(x2​,y2​),…,(xn​,yn​)，定义 Ci,r={(x,y)∈R2∣(x−xi)2+(y−yi)2≤r2}C_{i,r} = \{(x,y) \in \mathbb{R}^2 \mid (x-x_i)^2+(y-y_i)^2 \le r^2\}Ci,r​={(x,y)∈R2∣(x−xi​)2+(y−yi​)2≤r2} 为第 iii 个3G网络基站覆盖的范围，你需要计算

f(r)=S(C1,r∪C2,r∪…∪Cn,r)S(C1,r)+S(C2,r)+…+S(Cn,r)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})}
f(r)=S(C1,r​)+S(C2,r​)+…+S(Cn,r​)S(C1,r​∪C2,r​∪…∪Cn,r​)​当 r→+∞r \rightarrow +\inftyr→+∞ 时 f(r)f(r)f(r) 的极限 lim⁡r→+∞f(r)\lim_{r \rightarrow +\infty} f(r)limr→+∞​f(r)，其中 S(X)S(X)S(X) 表示平面点集 XXX 的面积。

Input

第一行包含一个正整数 nnn (1≤n≤2 0001 \le n \le 2\,0001≤n≤2000)，表示3G网络基站的个数。

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

Output

输出一行，包含一个实数表示 lim⁡r→+∞f(r)\lim_{r \rightarrow +\infty} f(r)limr→+∞​f(r)，要求绝对误差不超过 10−910^{-9}10−9。

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

题解：因为r无穷大，所以所有圆的面积是重叠的。只需要求出1:圆的个数即可求出答案。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

double n;

int main()
{
    scanf("%lf",&n);
    n=1.0/n;
    printf("%.15lf",n);
    return 0;
}