Pagini recente » Cod sursa (job #2392443) | Cod sursa (job #1940705) | Cod sursa (job #753693) | Cod sursa (job #1110030) | Cod sursa (job #572078)
Cod sursa(job #572078)
type vector=array[1..1000000]of extended;
var x,y:vector;
h:array[1..1000000]of extended;
n:longint;
function polar(x,y:extended):extended;
begin
if x>0 then
begin
if y>0 then polar:=arctan(y/x) else polar:=arctan(y/x)+2*pi;
end else
if x<0 then polar:=arctan(y/x)+pi else
if x=0 then
begin
if y>0 then polar:=pi/2 else
if y<0 then polar:=arctan(3*pi/2) else
polar:=0;
end;
end;
function det(x1,y1,x2,y2,x3,y3:extended):extended;
begin
det:=(x1*y2+x2*y3+x3*y1)-(x1*y3+x2*y1+x3*y2);
end;
procedure init;
var i:longint;px,py:extended; f:text;
begin
assign(f,'infasurare.in');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,x[i],y[i]);
px:=x[1]; py:=y[1];
for i:=2 to n do
if y[i]<py then begin px:=x[i];py:=y[i]; end;
for i:=1 to n do h[i]:=polar(x[i]-px,y[i]-py);
end;
procedure sw(var a,b:extended);
var t:extended;
begin
t:=a;a:=b;b:=t;
end;
procedure qs(left,right:longint);
var i,j:longint; p:extended;
begin
i:=left; j:=right; p:=h[(i+j)div 2];
while i<j do
begin
while h[i]<p do inc(i);
while h[j]>p do dec(j);
if i<=j then begin sw(h[i],h[j]);sw(x[i],x[j]);sw(y[i],y[j]);inc(i);dec(j);end;
end;
if i<right then qs(i,right);
if j>left then qs(left,j);
end;
procedure hull;
var px,py:vector; pn,i:longint;f:text;
begin
px[1]:=x[1];py[1]:=y[1];
px[2]:=x[2];py[2]:=y[2];
pn:=2;
for i:=3 to n do
begin
inc(pn);px[pn]:=x[i];py[pn]:=y[i];
if (pn>2)and(det(px[pn-2],py[pn-2],px[pn-1],py[pn-1],px[pn],py[pn])<0)then
begin
while det(px[pn-2],py[pn-2],px[pn-1],py[pn-1],px[pn],py[pn])<0 do
begin
py[pn]:=py[pn-1];
px[pn]:=px[pn-1];
dec(pn);
end;
end;
end;
assign(f,'infasurare.out');
rewrite(f);
writeln(f,pn);
for i:=1 to pn do writeln(f,px[i],' ',py[i]);
close(f);
end;
begin
init;
qs(1,n);
hull;
end.