Pagini recente » Cod sursa (job #1402441) | Cod sursa (job #3237569) | Cod sursa (job #2369717) | Cod sursa (job #616406) | Cod sursa (job #564226)
Cod sursa(job #564226)
type vector=array[1..1000000]of real;
var x,y,h:vector; n:longint;
function polar(x,y:real):real;
begin
if x>0 then
begin
if y>0 then polar:=arctan(y/x) else polar:=arctan(y/x)+pi*2;
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:=3*pi/2 else
polar:=0;
end;
end;
function det(x1,y1,x2,y2,x3,y3:real):real;
begin
det:=(x1*y2+x2*y3+x3*y1)-(x1*y3+x2*y1+x3*y2);
end;
procedure init;
var i:longint; px,py:real; f:text;
begin
assign(f,'infasuratoare.in');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,x[i],y[i]);
close(f);
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:real);
var t:real;
begin
t:=a;a:=b;b:=t;
end;
procedure qs(left,right:longint);
var i,j:longint; p:real;
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(x[i],x[j]);sw(y[i],y[j]);sw(h[i],h[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[i-2],py[i-2],px[i-1],py[i-1],px[i],py[i])<0) then
begin
while (det(px[pn-2],py[pn-2],px[pn-1],py[pn-1],px[pn],py[pn])<0) do
begin
px[pn-1]:=px[pn];
py[pn-1]:=py[pn];
end;
end;
end;
assign(f,'infasuratoare.out');
rewrite(f);
for i:=1 to pn do writeln(f,px[i]:0:6,' ',py[i]:0:6);
close(f);
end;
begin
init;
qs(1,n);
hull;
readln;
end.