思路:
一开始只是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; }