APIO2010信号覆盖 单调性+计算几何+容斥原理

思路:

一开始只是YY出了一个\(O(n^3logn)\)的算法.

我们枚举每两个点,同时再枚举另外一个点,就能得到这三个点的圆心前在两个点垂直平分线的位置.

那么现在我们再枚举每个点出现在这种圆中有多少种情况:这个点已经给定时,我们可以考虑圆心在垂直平分线上的可行位置,通过解不等式发现仅仅满足一个限制就是可行的圆心.于是就可以用数据结构维护快速得到有多少个可行的圆心.

然而正解的思路非常巧妙:

考虑每四个点,要么形成一个凸多边形,要么形成一个凹多边形.

由于没有任意四个点在一个圆上,那么对于一个凸多边形对于答案的贡献是2,一个凹多边形对于答案的贡献是1.

考虑如何计算凹多边形的数目.(然后我们也可以知道凸多边形的数目)

我们枚举中间的凹点,那么发现形成凹多边形的另外三个点必然不在凹点的同侧.因此我们就转化为计算总数减去在凹点同侧的三元组数目,这个利用极角序排序以及单调性可以\(O(nlogn)\)得到.

因此就在\(O(n^2logn)\)的时间内做出来了.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
typedef double f2;
 
#define N 1510
int x[N],y[N];
 
struct Point{
    int x,y;
    f2 Ang;
    inline void read(){scanf("%d%d",&x,&y);}
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    bool operator<(const Point&B)const{return Ang<B.Ang;}
    inline void print(){printf("%d %d\n",x,y);}
}P[N],seq[N<<1];int cnt;
inline LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
 
int main(){
    //freopen("tt.in","r",stdin);
    int n;scanf("%d",&n);int i,j,k;
    for(i=1;i<=n;++i)P[i].read();
     
    LL res=0;
    for(i=1;i<=n;++i){
        for(cnt=0,j=1;j<=n;++j)if(i^j)seq[++cnt]=P[j],seq[cnt].Ang=atan2(P[j].y-P[i].y,P[j].x-P[i].x);
        sort(seq+1,seq+cnt+1);
        for(j=cnt+1;j<=2*cnt;++j)seq[j]=seq[j-cnt];
         
        res+=(LL)(n-1)*(n-2)*(n-3)/6;
        int get;k=1;
        for(j=1;j<=cnt;++j){
            while(k+1!=j+cnt&&Cross(seq[j]-P[i],P[i]-seq[k+1])<=0)++k;
            //printf("j=%d ",j);seq[j].print();printf("k=%d ",k),seq[k].print();puts("");
            get=k-j;
            res-=(LL)get*(get-1)/2;
        }
    }
     
    LL all=(LL)n*(n-1)*(n-2)*(n-3)/24;
    LL ret=res+(all-res)*2;
    printf("%.3lf",3.0+(f2)ret*6/n/(n-1)/(n-2));
     
    return 0;
}