bzoj1913[Apio2010]signaling 信号覆盖 计算几何
2021-07-16 15:18
阅读：436
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。
题意就是求任选三个点围成一个圆，圆内包含的点数的期望
可以由 sum/C(n,3) 得到，那么要求的就是sum即任选三个点构成圆包含点的个数的总和
暴力枚举肯定不行，。。
网上的题解说的是求凹凸四边形个数，开始不是很懂，后来莫名其妙懂了。
我的理解是：
对于任意的一个三点确定的圆，如果它其中包含了一些点，那么这三点和里面包含的任意一点可以构成四边形
如果是凹四边形，只可能由外边的三点形成圆包含它
如果是凸四边形，对于同一个四边形来说可能有两种形成圆的方式使得圆包含这四个点
所以寻找四边形个数就可以了，关键就是把每个四边形看成了三个点形成一个圆+一个点在圆内贡献的答案
凸四边形数s2不好处理，可以处理凹四边形s1的个数，s1+s2=C(n,4)可以算出s2
处理凹四边形，用四边形总数-凸的个数
枚举每一个点作为凹四边形里面的点，考虑另外三点：
如果要构成凹四边形，那么一定有两条边的角度大于180，枚举每一个点，找到它的下一个目标点（与他构成角大于180度）计算即可
1 #include2 #define ll long long 3 #define N 1505 4 using namespace std; 5 int n,tp;ll s1,s2; 6 struct P{ 7 int x,y;double ang; 8 P operator - (const P &b)const{return (P){x-b.x,y-b.y};} 9 bool operator const P &b)const{return angb.ang;} 10 }a[N],q[N]; 11 ll crs(P a,P b){return (ll)a.x*b.y-(ll)a.y*b.x;} 12 ll solve(int x){ 13 tp=0; 14 ll all=1ll*(n-1)*(n-2)*(n-3)/6; 15 for(int i=1;i){ 16 if(i==x)q[0]=a[i]; 17 else q[++tp]=a[i]; 18 } 19 for(int i=1;i){ 20 P tmp=q[i]-q[0]; 21 q[i].ang=atan2(tmp.y,tmp.x); 22 } 23 sort(q+1,q+1+tp); 24 int p=2,cnt=0; 25 for(int i=1;i){ 26 while(crs(q[i]-q[0],q[p]-q[0])>=0){ 27 p=p%tp+1;cnt++; 28 if(p==i)break; 29 } 30 all-=cnt*(cnt-1)/2;cnt--; 31 } 32 return all; 33 } 34 int main(){ 35 scanf("%d",&n); 36 if(n==3){puts("3.00");return 0;} 37 for(int i=1;i) 38 scanf("%d%d",&a[i].x,&a[i].y); 39 for(int i=1;isolve(i); 40 s2=1ll*n*(n-1)*(n-2)*(n-3)/24-s1; 41 double ans=2*s2+s1;ans/=1ll*n*(n-1)*(n-2)/6; 42 printf("%.6lf",ans+3); 43 return 0; 44 }
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj1913[Apio2010]signaling 信号覆盖 计算几何
文章链接：http://soscw.com/essay/106039.html
文章标题：bzoj1913[Apio2010]signaling 信号覆盖 计算几何
文章链接：http://soscw.com/essay/106039.html
评论
亲，登录后才可以留言！