BZOJ1913 [APIO2010] 信号覆盖 signaling

BZOJ1913

题意:

给出平面上n个点,在这N个点中选3点构成一个圆,求圆上或圆内总点数的期望值。n 1500,保证无特殊情况。

题解:

显然一共有种情况,暴力枚举不可取。

考虑任取四个点构成一个四边形,可能有凸四边形和凹四边形两种情况。显然在一个四边形上任取三个点,有4种情况,每种情况都至少有3个点在圆上(即构成圆的3点),因此可以在计算时忽略这3个点,在输出时+3即可。由几何知识可得,在一个凸四边形上任取三个点,剩余的那个点在圆内可能有2种情况,而对于一个凹四边形可能有1种情况,那么要求的就变成了统计两种四边形的数目。

因为一共有个四边形,所以我们可以统计凸四边形的个数。首先枚举一个点,以这个点为原点,将其余点以极角序排序,然后使用类似旋转卡壳的思想,枚举另外两个点,保持这两个点的极角差<π,统计两点之间的点数即可。

时间复杂度为