Cod sursa(job #564254)

Utilizator gicu_01porcescu gicu gicu_01 Data 26 martie 2011 23:25:17
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.93 kb
type vector=array[1..1000000]of real;
var x,y,h:vector; n:longint;
function polar(x,y:real):real;
begin
 if x>0 then
  begin
   if y>0 then polar:=arctan(y/x) else polar:=arctan(y/x)+pi*2;
  end else
 if x<0 then polar:=arctan(y/x)+pi else
 if x=0 then
  begin
   if y>0 then polar:=pi/2 else
    if y<0 then polar:=3*pi/2 else
     polar:=0;
  end;
end;

function det(x1,y1,x2,y2,x3,y3:real):real;
begin
 det:=(x1*y2+x2*y3+x3*y1)-(x1*y3+x2*y1+x3*y2);
end;

procedure init;
var i:longint; px,py:real; f:text;
begin
 assign(f,'infasuratoare.in');
 reset(f);
 readln(f,n);
 for i:=1 to n do readln(f,x[i],y[i]);
 close(f);
 px:=x[1]; py:=y[1];
 for i:=2 to n do
  if y[i]<py then begin px:=x[i]; py:=y[i]; end;
 for i:=1 to n do h[i]:=polar(x[i]-px,y[i]-py);
end;

procedure afis;
var i:longint;
begin
 for i:=1 to n do
  writeln(x[i],' ',y[i],' ',h[i]);
end;

procedure sw(var a,b:real);
var t:real;
begin
 t:=a;a:=b;b:=t;
end;

procedure qs(left,right:longint);
var i,j:longint; p:real;
begin
 i:=left;j:=right; p:=h[(i+j)div 2];
 while i<j do
  begin
   while h[i]<p do inc(i);
   while h[j]>p do dec(j);
   if i<=j then begin sw(x[i],x[j]);sw(y[i],y[j]);sw(h[i],h[j]);inc(i); dec(j);end;
  end;
 if i<right then qs(i,right);
 if j>left then qs(left,j);
end;

procedure hull;
var px,py:vector; pn,i:longint; f:text;
begin
 px[1]:=x[1]; py[1]:=y[1];
 px[2]:=x[2]; py[2]:=y[2];
 pn:=2;
 for i:=3 to n do
  begin
   inc(pn); px[pn]:=x[i]; py[pn]:=y[i];
   if (pn>2)and(det(px[pn-2],py[n-2],px[pn-1],py[pn-1],px[pn],py[pn])<0) then
    begin
     while (det(px[pn-2],py[pn-2],px[pn-1],py[pn-1],px[pn],py[pn])<0) do
      begin
       px[pn-1]:=px[pn];
       py[pn-1]:=py[pn];
       dec(pn);
      end;
    end;
  end;
 assign(f,'infasuratoare.out');
 rewrite(f);
 writeln(f,pn);
 for i:=1 to pn do writeln(f,px[i]:0:6,' ',py[i]:0:6);
 close(f);
end;

begin
 init;
 qs(1,n);
 hull;
end.