Cod sursa(job #921675)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 21 martie 2013 10:45:55
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.54 kb
program infasuratoare;
type hacking=record
 x,y:real;
end;
var f,g:text;
    n,i,nr,pozmin,poz:longint;
    v:array[1..120000] of hacking;
    retine:array[1..120000] of hacking;
    viz:array[1..120000] of 0..1;
    bufin,bufout:array[1..65000] of byte;
    min:hacking;
    max:real;
    m1,m2,tangenta, arctangenta:real;

begin
 assign (f,'infasuratoare.in'); reset (f);
 assign (g,'infasuratoare.out'); rewrite (G);
 readln (f,n);
 min.x:=maxlongint; min.y:=maxlongint;
 for i:=1 to n do
 begin
    readln (f,v[i].x,v[i].y);
    if v[i].y<min.y then
    begin
     min:=v[i] ;
     pozmin:=i;
    end
    else
     if v[i].y=min.y then
      if v[i].x<min.x then
      begin
       min:=v[i];
       pozmin:=i;
      end;
 end;
 nr:=1;
 retine[1]:=min;
 while viz[pozmin]=0 do
 begin
  max:=-maxlongint;
  if nr=1 then m1:=0
  else
  begin
   if retine[nr].x-retine[nr-1].x<>0 then
   m1:=(retine[nr].y-retine[nr-1].y)/(retine[nr].x-retine[nr-1].x)
   else m1:=0;

   end;
   for i:=1 to n do
   begin
   if v[i].x-retine[nr].x<>0 then
    m2:=(v[i].y-retine[nr].y)/(v[i].x-retine[nr].x)
   else m2:=0;
    if 1+m1*m2<>0 then
    tangenta:=(abs(m1-m2))/(1+m1*m2)
    else tangenta:=0;
    arctangenta:=arctan (tangenta);
    if arctangenta>max then
    begin
     max:=arctangenta;
     poz:=i;
    end;
   end;
   inc(nr);
   retine[nr]:=v[poz];
   viz[poz]:=1;
  end;
  dec(nr);
  writeln (g,nr);
  for i:=1 to nr do
   writeln (g,retine[i].x:0:6,' ',retine[i].y:0:6);
  close (f);close (G);
end.