Cod sursa(job #923990)

Utilizator promix2012petruta andrei promix2012 Data 24 martie 2013 00:03:36
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.55 kb
program infasuratoare;
type hacking=record
 x,y,dist,unghi:extended;
end;
const pi=3.14159265;
var f,g:text;
    p:array[0..120000] of hacking;
    min:longint;
    i,n:longint;
    bufin,bufout:array[1..65000] of byte;
    st:array[1..120000] of hacking;
    vf:longint;
    determinant:extended;
    vector:array[1..120000] of hacking;


procedure adauga_stiva (valoare:hacking);
begin
 inc(vf);
 st[vf]:=valoare;
end;

function calcul_determinant1(a,b,c:hacking):real;
begin
 calcul_determinant1:=(a.x*b.y)+(a.y*c.y)+(b.x*c.y)-(c.x*b.y)-(a.x*c.y)-(b.x*a.y);

end;

procedure sterge_stiva;
begin
 dec(vf);
end;
function pivot(st,dr:longint):longint;
var r,d,di:longint;
aux:hacking;
begin
r:=st;
d:=dr;
di:=1;
while r<d do
   begin
   if p[r].unghi>=p[d].unghi then
       begin
       aux:=p[r];
       p[r]:=p[d];
       p[d]:=aux;
       di:=-di;
       end;
   if di<0 then
   dec(d) else
   inc(r);
   end;
   pivot:=r;
end;
procedure sort(st,dr:longint);
var p1:longint;
begin
if st<dr then
   begin
   p1:=pivot(st,dr);
   sort(st,p1-1);
   sort(p1+1,dr);
   end;
end;
function calcul_determinant(p1,p2,p3:hacking):real;
begin
calcul_determinant:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;

begin
 assign (f,'infasuratoare.in'); reset (f);
 assign (g,'infasuratoare.out'); rewrite (G);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,n);
 min:=0;
 p[0].y:=maxlongint; p[0].x:=maxlongint;
 for i:=1 to n do
 begin
  read (f,p[i].x,p[i].y);
  if p[i].y<p[min].y then
   min:=i
  else
   if p[i].y=p[min].y then
    if p[i].x<p[min].x then
     min:=i;
 end;
 for i:=1 to n do
 begin
  if i<>min then
  begin
   if p[i].x-p[min].x<>0 then
   begin
    p[i].unghi:=arctan ((p[i].y-p[min].y)/(p[i].x-p[min].x));
    p[i].unghi:=p[i].unghi*(180/pi);
   end
   else
    p[i].unghi:=90;
    if p[i].unghi<0 then p[i].unghi:=180+p[i].unghi;
  end;
 end;
 sort(1,n);
 vf:=0;
 adauga_stiva(p[1]);
 adauga_stiva(p[2]);
 for i:=3 to n do
 begin
  determinant:=calcul_determinant(st[vf-1],st[vf],p[i]);
  if determinant=0 then
  begin
   sterge_stiva;
   adauga_stiva(p[i]);
  end
  else
   if determinant>0 then
   begin
   adauga_stiva(p[i]);
   end
   else
    begin
     while (determinant<=0) and (vf>1) do
     begin
      sterge_stiva;
      determinant:=calcul_determinant(st[vf-1],st[vf],p[i]);
     end;
     adauga_stiva(p[i]);
    end;
 end;
 writeln (g,vf);
 for i:=1 to vf do
  writeln (g,st[i].x:10:6,' ',st[i].y:0:6);
 close (F); close (g);
end.