Pagini recente » Cod sursa (job #111965) | Cod sursa (job #1946926) | Cod sursa (job #358080) | Cod sursa (job #2432363) | Cod sursa (job #285654)
Cod sursa(job #285654)
var v:array[1..120000]of integer;
viz:array[1..120000]of boolean;
x,y:array[1..120000]of real;
f,g:text;
i,n,min,p,poz,pct,eu:longint;
umin,ung:real;
function cadran(u:real):real;
begin
if (x[i]>=x[pct])and(y[i]>=y[pct])then cadran:=u;
if (x[i]>=x[pct])and(y[i]<y[pct])then cadran:=2*pi+u;
if (x[i]<x[pct])and(y[i]>y[pct])then cadran:=u+pi;
if (x[i]<x[pct])and(y[i]<=y[pct])then cadran:=u+pi;
end;
begin
assign(f,'infasuratoare.in');reset(f);
assign(g,'infasuratoare.out');rewrite(g);
readln(f,n);
for i:=1 to n do read(f,x[i],y[i]);
min:=1;
for i:=2 to n do if y[i]<y[min] then min:=i
else if (y[i]=y[min])and(x[i]<x[min]) then min:=i;
eu:=1;
for i:=2 to n do if y[i]>y[eu] then eu:=i
else if (y[i]=y[eu])and(x[i]>x[eu])then eu:=i;
p:=1; v[p]:=min;
while not viz[min] do begin
pct:=v[p];
umin:=2*pi+1;
for i:=1 to n do
if (not viz[i])and(i<>pct) then begin
if x[i]-x[pct]=0 then begin
if y[i]-y[pct]<0 then ung:=-pi/2
else ung:=pi/2;
end
else ung:=arctan((y[i]-y[pct])/(x[i]-x[pct]));
ung:=cadran(ung);
if not viz[eu] then begin
if ung<umin then begin
umin:=ung;
poz:=i;
end;
end
else
if (ung>=pi)and(ung<umin)then begin
umin:=ung;
poz:=i;
end;
end;
inc(p);
v[p]:=poz;
viz[poz]:=true;
end;
writeln(g,p-1);
for i:=1 to p-1 do writeln(g,x[v[i]]:0:6,' ',y[v[i]]:0:6);
close(g);
end.