Pagini recente » Cod sursa (job #2729790) | Cod sursa (job #3038584) | Cod sursa (job #1412578)
program infasuratoare_convexa_pregatire_oni;
type pct=record
x,y:real;
end;
var f,g:text;
h,n,i,j,k,q:longint;
v:array[1..120000] of pct;
ok:array[1..120000] of 0..1;
stiva:array[1..120000] of longint;
bufin,bufout:array[1.. 1 shl 16] of byte;
function pivot(st,dr:longint):longint; inline;
var di,dj,i,j,aux:longint;
auxx:pct;
begin
i:=st; j:=dr;
di:=0; dj:=1;
while i<j do
begin
if (v[i].x>v[j].x) or ((v[i].x=v[j].x) and (v[i].y>v[j].y)) then
begin
aux:=di;
di:=dj;
dj:=aux;
auxx:=v[i];
v[i]:=v[j];
v[j]:=auxx;
end;
i:=i+di;
j:=j-dj;
end;
pivot:=i;
end;
procedure sort(st,dr:longint); inline;
var p:longint;
begin
if st<dr then
begin
p:=pivot(st,dr);
sort(st,p-1);
sort(p+1,dr);
end;
end;
function det(a,b,c:pct):real;
begin
det:=a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.x*c.y-a.y*b.x;
end;
begin
assign(f,'infasuratoare.in'); reset(f);
assign(g,'infasuratoare.out'); rewrite(g);
settextbuf(f,bufin); settextbuf(g,bufout);
readln(f,n);
for i:=1 to n do
readln(f,v[i].x,v[i].y);
sort(1,n);
stiva[1]:=1; stiva[2]:=2; q:=1; k:=2; i:=3;
ok[stiva[2]]:=1;
while ok[1]=0 do
begin
while ok[i]=1 do
begin
if i=n then q:=-1;
i:=i+q;
end;
while (k>=2) and (det(v[stiva[k-1]],v[stiva[k]],v[i])<0) do
begin
ok[stiva[k]]:=0;
dec(k);
end;
inc(k);
stiva[k]:=i;
ok[i]:=1;
end;
h:=k-1;
writeln(g,h);
for i:=1 to h do
writeln(g,v[stiva[i]].x:0:6,' ',v[stiva[i]].y:0:6);
close(f);
close(g);
end.