思路:

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

思路:

首先第一次看的时候认为是神题.

再一次看的时候卧槽这不是FFT裸题么.

然后写的时候发现有点坑...

(FFT都告诉你了难道还不会么)

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
static const f2 pi=acos(-1.0);
 
struct Complex{
    f2 u,v;
    Complex(){}
    Complex(f2 _u,f2 _v):u(_u),v(_v){}
     
    Complex operator+(const Complex&B)const{return Complex(u+B.u,v+B.v);}
    Complex operator-(const Complex&B)const{return Complex(u-B.u,v-B.v);}
    Complex operator*(const Complex&B)const{return Complex(u*B.u-v*B.v,u*B.v+v*B.u);}
    Complex operator*(const f2&p)const{return Complex(p*u,p*v);}
    Complex operator/(const f2&p)const{return Complex(u/p,v/p);}
    inline void operator=(const f2&p){u=p,v=0;}
    inline void operator+=(const Complex&B){u+=B.u,v+=B.v;}
    inline void operator-=(const Complex&B){u-=B.u,v-=B.v;}
    inline void operator*=(const Complex&B){f2 uu=u*B.u-v*B.v,vv=u*B.v+v*B.u;u=uu,v=vv;}
    inline void operator*=(const f2&p){u*=p,v*=p;}
    inline void operator/=(const f2&p){u/=p,v/=p;}
};
 
inline int revbit(int x,int b){
    int res=0;for(int i=0;i<b;++i)if((x>>i)&1)res+=1<<(b-1-i);return res;
}
inline void fft(Complex A[],int n,int rev){
    register int i,j,k;
    int bit=0,tmp=n;for(;tmp^1;tmp>>=1)++bit;
    int ano;for(i=0;i<n;++i){ano=revbit(i,bit);if(i<ano)swap(A[i],A[ano]);}
    Complex wn,w,t;
    for(k=2;k<=n;k<<=1)
        for(wn=Complex(cos(2*pi/k),rev*sin(2*pi/k)),i=0;i<n;i+=k)
            for(w=1,j=0;j<k/2;++j,w*=wn)
                t=w*A[i+j+k/2],A[i+j+k/2]=A[i+j]-t,A[i+j]+=t;
    if(rev==-1)for(i=0;i<n;++i)A[i]/=n;
}
 
#define N 131072
 
inline void mul(Complex A[],Complex B[],Complex C[]){
    static Complex sa[N],sb[N];
    memcpy(sa,A,N*sizeof(Complex)),memcpy(sb,B,N*sizeof(Complex));
    fft(sa,N,1),fft(sb,N,1);
    for(int i=0;i<N;++i)C[i]=sa[i]*sb[i];
    fft(C,N,-1);
}
 
Complex A[N],A2[N],A3[N];
Complex mul2[N],mul3[N],mul3_2[N];
 
long long res[N];
 
long long up(const f2&p){
    return(long long)(p+.5);
}
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int x;while(n--)scanf("%d",&x),A[x]=1,A2[2*x]=1,A3[3*x]=1;
     
    mul(A,A,mul2);
    mul(mul2,A,mul3);
    mul(A,A2,mul3_2);
     
    for(int i=0;i<N;++i)mul2[i]-=A2[i],mul2[i]*=.5;
    for(int i=0;i<N;++i)mul3_2[i]-=A3[i];
    for(int i=0;i<N;++i)mul3[i]-=A3[i]+mul3_2[i]*3,mul3[i]/=6;
     
    for(int i=0;i<N;++i)res[i]+=up(A[i].u)+up(mul2[i].u)+up(mul3[i].u);
     
    for(int i=0;i<N;++i)if(res[i]!=0)printf("%d %lld\n",i,res[i]);
    return 0;
}