【题目分析】:还是很裸的凸包,Master_Chivu的数据eps要1e-12.
【Code】:
const
eps=1e-12;
type
point=record
x,y:extended;
end;
var
p,q:array[0..200000]of point;
n,m,i,k:longint; ans:extended;
procedure qsort(l,r:longint);
var i,j:longint; t:point; x,y:extended;
begin
i:=l; j:=r; x:=p[(l+r)>>1].x; y:=p[(l+r)>>1].y;
repeat
while (p[i].x<x) or (p[i].x=x) and (p[i].y<y) do inc(i);
while (p[j].x>x) or (p[j].x=x) and (p[j].y>y) do dec(j);
if i<=j then begin
t:=p[i]; p[i]:=p[j]; p[j]:=t; inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j); if i<r then qsort(i,r);
end;
function cross(p0,p1,p2:point):extended;
begin
exit((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
end;
begin
readln(n);
for i:=1 to n do readln(p[i].x,p[i].y);
qsort(1,n);
m:=0;
for i:=1 to n do begin
while (m>1) and (cross(q[m-1],q[m],p[i])<=eps) do dec(m);
inc(m); q[m]:=p[i];
end;
k:=m;
for i:=n-1 downto 1 do begin
while (m>k) and (cross(q[m-1],q[m],p[i])<=eps) do dec(m);
inc(m); q[m]:=p[i];
end;
for i:=m downto 2 do writeln(q[i].x:0:4,' ',q[i].y:0:4);
end.