bzoj1913[Apio2010]signaling 信号覆盖计算几何

1913: [Apio2010]signaling 信号覆盖

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1583 Solved: 646
[Submit][Status][Discuss]

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。

题意就是求任选三个点围成一个圆，圆内包含的点数的期望
可以由 sum/C(n,3) 得到，那么要求的就是sum即任选三个点构成圆包含点的个数的总和
暴力枚举肯定不行，。。
网上的题解说的是求凹凸四边形个数，开始不是很懂，后来莫名其妙懂了。
我的理解是：
对于任意的一个三点确定的圆，如果它其中包含了一些点，那么这三点和里面包含的任意一点可以构成四边形
如果是凹四边形，只可能由外边的三点形成圆包含它
如果是凸四边形，对于同一个四边形来说可能有两种形成圆的方式使得圆包含这四个点
所以寻找四边形个数就可以了，关键就是把每个四边形看成了三个点形成一个圆+一个点在圆内贡献的答案

凸四边形数s2不好处理，可以处理凹四边形s1的个数，s1+s2=C(n,4)可以算出s2

处理凹四边形，用四边形总数-凸的个数
枚举每一个点作为凹四边形里面的点，考虑另外三点：
如果要构成凹四边形，那么一定有两条边的角度大于180，枚举每一个点，找到它的下一个目标点（与他构成角大于180度）计算即可

 1 #include<bits/stdc++.h>
 2 #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 ang<b.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<=n;i++){
16         if(i==x)q[0]=a[i];
17         else q[++tp]=a[i];
18     }
19     for(int i=1;i<=tp;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<=tp;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<=n;i++)
38     scanf("%d%d",&a[i].x,&a[i].y);
39     for(int i=1;i<=n;i++)s1+=solve(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 }