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

2021/11/1 20:11:06

本文主要是介绍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

3
0 0
0 1
1 0

output

Copy

0.333333333333333

input

Copy

4
0 0
0 1
1 0
1 1

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("%.15f\n", a);
	return 0;
}



这篇关于2021年中国大学生程序设计竞赛女生专场 G. 3G网络的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程