题解 P3630 【[APIO2010]信号覆盖 】

· · 题解

N^4的算法很好想，枚举三个点组成一个圆，再枚举一个点判断点是否在圆内，统计输出就可以了，但这样显然只能拿到40分。

对于任意4个点，组成的图形只有两种，一种是凸四边形，一种是凹四边形，即一个点在另外三个点组成的三角形内。

对于凸四边形，必有一组对角大于180°，此时这组对角所对应的顶点必然在另外三个点组成的圆中，所以每个凸四边形对于总的答案贡献两个点。

对于凹四边形，设D在三角形ABC内，那么只有D在三角形ABC组成的圆中，A，B和C都不在另外三个点的圆中，所以凹四边形对总的答案贡献一个点。

由于总的四边形个数一定，我们只需要求出凹四边形的个数。

首先枚举凹点D，以D作为极点，x轴正半轴为极轴进行极角排序，对于一个合法的三角形ABC，过D的任意一条直线都不能使三个点在D的同一侧，这样我们就用总的三角形个数C（n-1，3）来减去同一侧的三角形个数。这样枚举一个点A，找到A到C的角小于180°的最远点C，设A的编号为i，C的编号为j，那么此时在一侧的三角形个数为C（j-i，2），由于C对于每一个A是单调的，所以每一次的复杂度均为n，总的复杂度就是n^2，加上排序的复杂度，总复杂度为n^2logn。

Code

program test3;
uses math;
var x,y:array[0..1500]of extended;
    p,q:array[0..3000]of extended;
    i,j,m,k:longint;
    tot,sum1,sum2,sum,now,n:int64;
    ans:extended;
procedure kp(l,r:longint);
var i,j:longint;
    x,y:extended;
begin
    i:=l;j:=r;
    x:=p[(l+r)shr 1];
    repeat
        while p[i]<x do inc(i);
        while p[j]>x do dec(j);
        if i<=j then
        begin
            y:=p[i];
            p[i]:=p[j];
            p[j]:=y;
            inc(i);
            dec(j);
        end;
    until i>j;
    if l<j then kp(l,j);
    if i<r then kp(i,r);
end;
begin
    readln(n);
    for i:=1 to n do readln(x[i],y[i]);
    tot:=n*(n-1)*(n-2)div 6;
    for k:=1 to n do
    begin
        p[k]:=0;
        for i:=1 to n do
        begin
            if i=k then continue;
            q[i]:=(x[i]-x[k])/sqrt(sqr(x[i]-x[k])+sqr(y[i]-y[k]));
            p[i]:=arccos(q[i]);
            if y[i]<y[k] then p[i]:=2*pi-p[i];
        end;
        kp(1,n);
        for i:=2 to n do p[i+n-1]:=p[i];
        j:=2;
        now:=0;
        for i:=2 to n do
        begin
            while (((p[j+1]-p[i]<=pi)and(p[j+1]>=p[i]))or(p[j+1]-p[i]<-pi))and(j<i+n-2) do inc(j);
            now:=now+(j-i)*(j-i-1)div 2;
        end;
        sum:=sum+(n-1)*(n-2)*(n-3)div 6-now;
    end;
    sum1:=sum;
    sum2:=n*(n-1)*(n-2)*(n-3)div 24-sum1;
    sum:=sum1+sum2*2+tot*3;
    ans:=sum/tot;
    writeln(ans:0:6);
end.