这是一道好题,要求每个三点圆覆盖的点数和

我们可以算四边形的贡献,四边形显然分成两种:凸四边形和凹四边形

显然,凹四边形的覆盖只可能是三个点组成三角形包含另一个点,所以贡献是1

凸四边形,其最小圆覆盖是以最长对角线为直径的

注意一个很重要的条件,四点不共圆,所以凸四边形的贡献是2

四边形总数是一定的,显然统计凹四边形更方便

穷举一个点作为原点,即求包含原点的三角形数目——转化为bzoj1914,解决了!

 uses math;
type node=record
x,y:longint;
end; var c,b:array[..] of node;
tot,n,a,d:int64;
i:longint; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; function cross(a,b:node):double;
begin
exit(int64(a.x)*int64(b.y)-int64(a.y)*int64(b.x));
end; function cmp(a,b:node):boolean;
begin
if (a.y>) and (b.y<=) then exit(true);
if (b.y>) and (a.y<=) then exit(false);
if cross(a,b)> then exit(true);
exit(false);
end; procedure sort(l,r:longint);
var i,j:longint;
x:node;
begin
i:=l;
j:=r;
x:=c[(l+r) shr ];
repeat
while cmp(c[i],x) do inc(i);
while cmp(x,c[j]) do dec(j);
if not(i>j) then
begin
swap(c[i],c[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function dis(a:node):double;
begin
exit(sqrt(sqr(a.x)+sqr(a.y)));
end; function get(k:longint):int64;
var i,s,t,r:longint;
p:node;
begin
p:=b[k];
t:=;
for i:= to n do
if i<>k then
begin
inc(t);
c[t].x:=b[i].x-p.x;
c[t].y:=b[i].y-p.y;
end;
sort(,t);
get:=(n-)*(n-)*(n-) div ;
r:=;
s:=;
for i:= to t do
begin
while cross(c[i],c[r])>= do
begin
r:=r mod t+;
inc(s);
if r=i then break;
end;
get:=get-(s-)*s div ;
dec(s);
end;
end; begin
readln(n);
if n= then
begin
writeln(3.00);
halt;
end;
for i:= to n do
readln(b[i].x,b[i].y);
for i:= to n do
a:=a+get(i); d:=n*(n-)*(n-)*(n-) div -a;
tot:=(n-)*(n-)*n div ;
writeln((a+*d)/tot+::);
end.
05-11 16:11