Cod sursa(job #591107)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 22 mai 2011 13:37:33
Problema Rubarba Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.37 kb
var     x,y,p:array[1..100000] of extended;
        t:array[1..200000] of longint;
        n,i,j,l,poz:longint;
        xp,yp,lun,lat,q,w,d,a,b,c,x1,x2,y1,y2,x3,y3,x0,y0,m,ar: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(x[i],x[j]);
          sw(y[i],y[j]);
          sw(p[i],p[j]);
          inc(i);
          dec(j);
        end;
    end;
  if i<right then qs(i,right);
  if j>left then qs(left,j);
end;

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

begin
  assign(f,'rubarba.in');
  assign(g,'rubarba.out');
  reset(f);
  rewrite(g);
  readln(f,n);
  for i:=1 to n do
    readln(f,x[i],y[i]);
  xp:=x[1];
  yp:=y[1];
  for i:=2 to n do
    if (y[i]<yp)or((y[i]=yp)and(x[i]>xp)) then begin xp:=x[i]; yp:=y[i]; end;
  for i:=1 to n do
    p[i]:=polar(x[i]-xp,y[i]-yp);
  qs(1,n);
  {for i:=1 to n do
    writeln(x[i]:0:0,' ',y[i]:0:0,' ',p[i]:0:3);
  readln;}
  t[1]:=1;
  t[2]:=2;
  poz:=2;
  for i:=3 to n do
    begin
      if delta(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
      while delta(x[t[poz-1]],y[t[poz-1]],x[t[poz]],y[t[poz]],x[i],y[i])<0 do
        dec(poz);
    end;
  {for i:=1 to poz do
    writeln(x[t[i]]:0:0,' ',y[t[i]]:0:0);
  readln;}

  for i:=poz+1 to poz*2 do
    t[i]:=t[i-poz];
  ar:=1000000000000;
  for i:=2 to poz+1 do
    begin
      lun:=0;
      lat:=0;
      q:=0;
      w:=1;
      x1:=x[t[i-1]];
      y1:=y[t[i-1]];
      x2:=x[t[i]];
      y2:=y[t[i]];
      a:=y2-y1;
      b:=x1-x2;
      c:=y1*(x2-x1)-x1*(y2-y1);
      j:=i;
      while q<w do
        begin
          inc(j);
          x3:=x[t[j]];
          y3:=y[t[j]];
          q:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
          x3:=x[t[j+1]];
          y3:=y[t[j+1]];
          w:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
        end;
     { writeln(x[t[i-1]]:0:0,' ',y[t[i-1]]:0:0,' ',x[t[i]]:0:0,' ',y[t[i]]:0:0);
      writeln(x[t[j]]:0:0,' ',y[t[j]]:0:0);}
      lat:=q;
      m:=-1/((y2-y1)/(x2-x1));
      x0:=x[t[j]];
      y0:=y[t[j]];
      a:=m;
      b:=-1;
      c:=y0-m*x0;
      l:=j;
      q:=0;
      w:=1;
      while q<w do
        begin
          inc(j);
          x3:=x[t[j]];
          y3:=y[t[j]];
          q:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
          x3:=x[t[j+1]];
          y3:=y[t[j+1]];
          w:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
        end;
      lun:=q;
      q:=0;
      w:=1;
      while q<w do
        begin
          dec(j);
          x3:=x[t[j]];
          y3:=y[t[j]];
          q:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
          x3:=x[t[j-1]];
          y3:=y[t[j-1]];
          w:=abs(a*x3+b*y3+c)/sqrt(a*a+b*b);
        end;
      lun:=lun+q;
      if ar>lun*lat then ar:=lun*lat;
    end;
  writeln(g,ar:0:2);
  close(g);
end.