bzoj1132

每次都选最左边的点,然后以这个点为原点

统计和这个点构成的三角形面积和

不难想到极角排序然后由叉积很容易求出

 const oo= shl ;
eps=1e-8;
var i,j,k,m,n:longint;
x,y:array[..] of longint;
z:array[..] of double;
ans,xx,yy:int64; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j:longint;
p,q:double;
begin
i:=l; j:=r;
p:=z[(l+r) shr ];
repeat
while z[i]<p-eps do inc(i);
while z[j]>p+eps do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
q:=z[i]; z[i]:=z[j]; z[j]:=q;
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; begin
readln(n);
for i:= to n do
readln(x[i],y[i]);
for i:= to n- do
begin
k:=i;
for j:=i to n do
if x[j]<x[k] then k:=j;
swap(x[i],x[k]);
swap(y[i],y[k]);
for j:=i+ to n do
if x[j]=x[i] then
if y[j]>y[i] then z[j]:=oo
else z[j]:=-oo
else z[j]:=(y[j]-y[i])/(x[j]-x[i]);
sort(i+,n);
xx:=; yy:=;
for j:=i+ to n do
begin
ans:=ans+(x[j]-x[i])*yy-(y[j]-y[i])*xx;
xx:=xx+x[j]-x[i]; yy:=yy+y[j]-y[i];
end;
end;
writeln(abs(ans)/::);
end.
上一篇:Elasticsearch聚合 之 Range区间聚合


下一篇:[团队项目]expat不兼容BUG