Cod sursa(job #593088)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 1 iunie 2011 11:34:17
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.91 kb
type punct=record x,y:real; end;
var a,b:array[1..120001] of punct;
    q,p,k,i,n:longint;
    min,max,t,minx,miny,maxx,maxy:real;
begin
assign(input,'infas.in');reset(input);
assign(output,'infas.out');rewrite(output);
readln(n);
miny:=maxlongint;
for i:=1 to n do
begin
readln(a[i].x,a[i].y);
if (a[i].y<miny) or ((a[i].y=miny) and (a[i].x<minx)) then
begin
minx:=a[i].x;
miny:=a[i].y;
end;
if (a[i].y>maxy) or ((a[i].y=maxy) and (a[i].x>maxx)) then
begin
maxx:=a[i].x;
maxy:=a[i].y;
end;
end;
k:=1;
b[1].x:=minx;
b[1].y:=miny;
q:=1;
while (b[k].x<>maxx) or (b[k].y<>maxy) do
begin
min:=maxlongint;
for i:=1 to n do
if (i<>q) and (b[k].y<=a[i].y) then
begin
if (a[i].x<>b[k].x) and (a[i].y<>b[k].y) then
begin
t:=arctan((a[i].y-b[k].y)/(a[i].x-b[k].x))*180/pi;
if t<0 then t:=-t+90;
end
else begin
if (a[i].x=b[k].x) then
if (a[i].y>b[k].y) then t:=90 else t:=270;
if (a[i].y=b[k].y) then
if (a[i].x>b[k].x) then t:=0 else t:=180;
end;
if ((t<min) or ((t=min) and (sqrt(sqr(a[i].x-b[k].x)+sqr(a[i].y-b[k].y))>max))) then
begin
min:=t;
max:=sqrt(sqr(a[i].x-b[k].x)+sqr(a[i].y-b[k].y));
p:=i;
end;
end;
inc(k);
b[k].x:=a[p].x;
b[k].y:=a[p].y;
q:=p;
end;
while (b[k].x<>minx) or (b[k].y<>miny) do
begin
min:=maxlongint;
for i:=1 to n do
if (i<>q) and (b[k].y>=a[i].y) then
begin
if (a[i].x<>b[k].x) and (a[i].y<>b[k].y) then
begin
t:=arctan((b[k].y-a[i].y)/(b[k].x-a[i].x))*180/pi;
if t<0 then t:=90-t;
end
else begin
if (a[i].x=b[k].x) then
if (a[i].y<b[k].y) then t:=90 else t:=270;
if (a[i].y=b[k].y) then
if (a[i].x<b[k].x) then t:=0 else t:=180;
end;
if ((t<min) or ((t=min) and (sqrt(sqr(a[i].x-b[k].x)+sqr(a[i].y-b[k].y))>max))) then
begin
min:=t;
max:=sqrt(sqr(a[i].x-b[k].x)+sqr(a[i].y-b[k].y));
p:=i;
end;
end;
inc(k);
b[k].x:=a[p].x;
b[k].y:=a[p].y;
q:=p;
end;
dec(k);
writeln(k);
for i:=1 to k do
writeln(b[i].x:0:6,' ',b[i].y:0:6);
end.