「BZOJ1913」[Apio2010] signaling 信号覆盖

2015年4月17日5,1690

Description

Input

输入第一行包含一个正整数 n, 表示房子的总数。接下来有 n 行，分别表示 每一个房子的位置。对于 i = 1, 2, .., n, 第i 个房子的坐标用一对整数 xi和yi来表 示，中间用空格隔开。

Output

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出 结果与精确值的绝对误差不超过0.01。

Sample Input

4
0 2
4 4
0 0
2 0

Sample Output

3.500

HINT

3.5, 3.50, 3.500, … 中的任何一个输出均为正确。此外，3.49, 3.51,
3.499999，…等也都是可被接受的输出。
「数据范围」
100%的数据保证，对于 i = 1, 2, .., n, 第 i 个房子的坐标(xi, yi)为整数且
–1,000,000 ≤ xi, yi ≤ 1,000,000. 任何三个房子不在同一条直线上，任何四个房子不
在同一个圆上；
40%的数据，n ≤ 100；
70%的数据，n ≤ 500；
100%的数据，3 ≤ n ≤ 1,500。

题解

pyc：

题目大意：一个平面上n个点，随机选3个点构成一个圆，问期望有多少个点在这个圆内和圆上。数据保证没有4点共圆、3点共线和重点。

算法讨论：考虑四边形，凸四边形对答案的贡献为2，凹四边形对答案的贡献为1。设凹四边形个数为a，凸四边形个数为b，那么b=C(n,4)-a。枚举凹四边形的中间点，以中间点为原点，把其他点按照极角排序，枚举极角差刚刚不小于π的两条边，那么这两条边之间的点和其中一条边上的点不包含中间点。由于按照极角排序，那么枚举的时间复杂度是O(n)。设p为不包含中间点的三角形个数，那么以该点为中间点的凹四边形个数为C(n-1,3)-p。最后的期望即为(a+2*b)/C(n,3)。

 

avatar
  Subscribe  
提醒