1913: [Apio2010]signaling 信号覆盖
Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 1232 Solved: 506[][][]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。Source
Solution
这题的思路还是很巧妙的QwQ
首先要是枚举点，复杂度是$O(N^4)$的，而且难以进一步优化。
这里保证四点不共圆，所以可以考虑一下从多边形对答案的贡献的入手。
对于一个凸多边形，它对答案的贡献是$2$，即以一组对角和$>\pi$的两个点中的任意一个和另外两个点做圆，一定能覆盖另一个点。
对于一个凹多边形，它对答案的贡献只有$1$，即以靠外三个点做圆可以覆盖凹进去的那个点。
所以可以得到答案$ans=3+\frac {2*cnt_{凸}+1*cnt_{凹}} {C^{N}_{3}}$
然后就是如何快速的求出凸多边形和凹多边形的数量了。
因为这里保证了不存在三点共线，考虑$O(N^2)$的枚举两个点组成的一条直线，算出直线两边的两个点和直线上两点组成多边形的情况。
对于直线两边的点数量分别是$a$和$b$，就对答案加入$C^{a}_{2}$和$C^{b}_{2}$，这里利用极角排序，可以利用单调性做到直线旋转时的均摊$O(1)$的复杂度。
然后考虑这样统计出来的是什么，对于一个凸多边形，利用这样的方式，会被统计四次，对于一个凹多边形，这样会统计三次，所以这样的答案就是$4*cnt_{凸}+3*cnt_{凹}$
然后减掉$2*(cnt_{凸}+cnt_{凹})=2*cnt_{总}=2*C^{n}_{4}$，就可以得到$2*cnt_{凸}+1*cnt_{凹}$。同时就可以得到答案。
所以总复杂度是$O(N^2)$就得到解决。
Code
#include#include #include #include #include using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}#define Pi acos(-1.0)#define MAXN 2010 int N,tot;struct Point{ int x,y;}P[MAXN];double k[MAXN<<1],ans; inline double C(int n,int m){ double re=1; for (int i=n-m+1; i<=n; i++) re=re*i; for (int i=1; i<=m; i++) re=re/i; return re;} int main(){ N=read(); for (int i=1; i<=N; i++) P[i].x=read(),P[i].y=read(); for (int i=1; i<=N; i++) { tot=0; for (int j=1; j<=N; j++) if (i!=j) k[++tot]=atan2(P[j].x-P[i].x,P[j].y-P[i].y); sort(k+1,k+tot+1); for (int j=1; j<=tot; j++) k[tot+j]=k[j]+2.0*Pi; for (int j=1,now=1; j<=tot; j++) { while (k[now]-k[j]