Cod sursa(job #285654)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 22 martie 2009 20:08:59
Problema Infasuratoare convexa Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 2.18 kb
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.