2021年中国大学生程序设计竞赛女生专场 G. 3G网络

104 阅读 0 评论 69 点赞

我是靠谱客的博主端庄酸奶，最近开发中收集的这篇文章主要介绍2021年中国大学生程序设计竞赛女生专场 G. 3G网络，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：Problem - G - Codeforces

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

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

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

更形式化地描述这个问题，记 nn 个3G网络基站的位置分别为 (x1,y1),(x2,y2),…,(xn,yn)(x1,y1),(x2,y2),…,(xn,yn)，定义 Ci,r={(x,y)∈R2∣(x−xi)2+(y−yi)2≤r2}Ci,r={(x,y)∈R2∣(x−xi)2+(y−yi)2≤r2} 为第 ii 个3G网络基站覆盖的范围，你需要计算

f(r)=S(C1,r∪C2,r∪…∪Cn,r)S(C1,r)+S(C2,r)+…+S(Cn,r)f(r)=S(C1,r∪C2,r∪…∪Cn,r)S(C1,r)+S(C2,r)+…+S(Cn,r)

当 r→+∞r→+∞ 时 f(r)f(r) 的极限 limr→+∞f(r)limr→+∞f(r)，其中 S(X)S(X) 表示平面点集 XX 的面积。

Input

第一行包含一个正整数 nn (1≤n≤20001≤n≤2000)，表示3G网络基站的个数。

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

Output

输出一行，包含一个实数表示 limr→+∞f(r)，要求绝对误差不超过 10−9。

也就是说，如果你给出的答案是 a，标程给出的答案是 b，你的答案被认为是正确的当且仅当 |a−b|≤10−9。

Examples

input

Copy

1
0 0

output

Copy

1.000000000000000

input

Copy

2
0 0
0 1

output

Copy

0.500000000000000

input

Copy

output

Copy

0.333333333333333

input

Copy

output

Copy

0.250000000000000

思路：当r趋向与无穷的时候，任意一个点都可以覆盖整个小镇，所以比例就是1/n

#include<bits/stdc++.h>
using namespace std;

int x[2005], y[2005];

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i];
	}
	double a = 1.00000000000;
	a = 1 / (n * 1.00000000000);
	printf("%.15fn", a);
	return 0;
}