【bzoj1913】[Apio2010]signaling 信号覆盖

2015年4月17日2,4740

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)。