Pagini recente » Cod sursa (job #2988074) | Cod sursa (job #1396569) | Cod sursa (job #1043431) | Cod sursa (job #2821900) | Cod sursa (job #1042903)
program infasuratoare_convexa;
type lista=^celula;
celula=record
xi,yi:extended;
next:lista;
end;
var bufin,bufout:array [1..1000] of byte;
n,i:longint;
x,y,panta:array [1..1200] of extended;
xmin,ymin,xx,yy:extended;
posmin:longint;
stiva,r:lista;
procedure sort(l,r: longint);
var
i,j:longint;
x1,y1:extended;
begin
i:=l;
j:=r;
x1:=panta[(l+r) div 2];
repeat
while panta[i]<x1 do
inc(i);
while x1<panta[j] do
dec(j);
if not(i>j) then
begin
y1:=panta[i];
panta[i]:=panta[j];
panta[j]:=y1;
y1:=x[i];
x[i]:=x[j];
x[j]:=y1;
y1:=y[i];
y[i]:=y[j];
y[j]:=y1;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
procedure scrie(q:lista;h:longint);
begin
if q=nil then writeln(h)else
begin
scrie(q^.next,h+1);
writeln(q^.xi:0:6,' ',q^.yi:0:6);
end;
end;
begin
assign(input,'infasuratoare.in');
reset(input);
settextbuf(input,bufin);
assign(output,'infasuratoare.out');
rewrite(output);
settextbuf(output,bufout);
readln(n);
xmin:=1000000000;
for i:=1 to n do
begin
readln(x[i],y[i]);
if x[i]<xmin then
begin
ymin:=y[i];
xmin:=x[i];
posmin:=i;
end else
if x[i]=xmin then
begin
if y[i]<ymin then begin ymin:=y[i];posmin:=i;end;
end;
end;
xx:=x[1];
yy:=y[1];
x[1]:=xmin;
y[1]:=ymin;
x[posmin]:=xx;
y[posmin]:=yy;
for i:=2 to n do
if x[i]<>x[1] then panta[i]:=(y[i]-y[1])/(x[i]-x[1])
else panta[i]:=10000000 ;
sort(2,n);
new(stiva);
stiva^.xi:=x[1];
stiva^.yi:=y[1];
stiva^.next:=nil;
new(r);
r^.xi:=x[2];
r^.yi:=y[2];
r^.next:=stiva;
stiva:=r;
for i:=3 to n do {produs scalar }{a,b,c obrazuit povorot nalevo esli}
begin {(bx-ax)(cy-ay)-(by-ay)(cx-ax)>0}
while not((stiva^.xi-stiva^.next^.xi)*(y[i]-stiva^.next^.yi)-
(stiva^.yi-stiva^.next^.yi)*(x[i]-stiva^.next^.xi)>0) do
begin
stiva:=stiva^.next;
end;
new(r);
r^.xi:=x[i];
r^.yi:=y[i];
r^.next:=stiva;
stiva:=r;
end;
scrie(stiva,0);
close(output);
end.