Cod sursa(job #590826)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 20 mai 2011 13:05:36
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.84 kb
var x,y,p:array[1..120000] of extended;
    t:array[1..120000] of longint;
    n,i,j,poz:longint;
    px,py:extended;
    f,g:text;

function polar(x,y:extended):extended;
begin
  if x>0 then polar:=arctan(y/x) else
  if x<0 then polar:=arctan(y/x)+pi else if y=0 then polar:=0 else polar:=pi/2;
end;

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

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

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

begin
  assign(f,'infasuratoare.in');
  assign(g,'infasuratoare.out');
  reset(f);
  rewrite(g);
  readln(f,n);
  for i:=1 to n do
    readln(f,x[i],y[i]);
  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
    p[i]:=polar(x[i]-px,y[i]-py);
  qs(1,n);
  
 //  for i:=1 to n do
 // writeln(x[i]:0:0,' ',y[i]:0:0,' ',p[i]:0:4);
 // readln;
  
  t[1]:=1;
  t[2]:=2;
  poz:=2;
  for i:=3 to n do
    begin
      if det(x[t[poz-1]],y[t[poz-1]],x[t[poz]],y[t[poz]],x[i],y[i])>0 then
        begin
          inc(poz);
          t[poz]:=i;
        end else
        begin
          while det(x[t[poz-1]],y[t[poz-1]],x[t[poz]],y[t[poz]],x[i],y[i])<0 do
            dec(poz);
          inc(poz);
          t[poz]:=i;
        end;
    end;
  writeln(g,poz);
  for i:=1 to poz do
    writeln(g,x[t[i]]:0:6,' ',y[t[i]]:0:6);
  close(g);
end.