Pagini recente » Cod sursa (job #2784982) | Cod sursa (job #689705) | Cod sursa (job #2881319) | Cod sursa (job #1306811) | Cod sursa (job #293027)
Cod sursa(job #293027)
type punct=record
x,y:real;
end;
var v:array[1..120001]of punct;
pct:punct;
det:real;
st:array[1..120001]of longint;
ung:array[1..120001]of real;
n,i,j,poz,u:longint;
procedure sort(l,r:longint);
var aux1:punct;
aux,y:real;
st,dr,x:longint;
begin
st:=l; dr:=r;
x:=(l+r)div 2;
y:=ung[x];
repeat
while ung[st]<y do inc(st);
while ung[dr]>y do dec(dr);
if st<=dr then begin
aux:=ung[st]; ung[st]:=ung[dr]; ung[dr]:=aux;
aux1:=v[st]; v[st]:=v[dr]; v[dr]:=aux1;
inc(st);dec(dr);
end;
until st>dr;
if l<dr then sort(l,dr);
if st<r then sort(st,r);
end;
function determinant(a,b,c:punct):boolean;
begin
determinant:=(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y) < 0;
end;
begin
assign(input,'infasuratoare.in');reset(input);
assign(output,'infasuratoare.out');rewrite(output);
read(n);
read(v[1].x,v[1].y);
pct:=v[1]; poz:=1;
for i:=2 to n do begin
read(v[i].x,v[i].y);
if v[i].y<pct.y then begin
pct:=v[i];
poz:=i;
end
else if (v[i].y=pct.y)and(v[i].x<pct.x)then begin
pct:=v[i];
poz:=i;
end;
end;
for i:=1 to n do
if i<>poz then begin
if v[i].x-pct.x<>0 then ung[i]:=arctan((v[i].y-pct.y)/(v[i].x-pct.x))
else ung[i]:=pi/2;
if ung[i]<0 then ung[i]:=ung[i]+pi;
end;
sort(1,n);
u:=1;
st[1]:=1;
for i:=2 to n do begin
while (u>=2)and(determinant(v[st[u-1]],v[st[u]],v[i]))do dec(u);
inc(u);
st[u]:=i;
end;
writeln(u);
for i:=1 to u do writeln(v[st[i]].x:0:6,' ',v[st[i]].y:0:6);
close(output);
end.