Cod sursa(job #591128)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 22 mai 2011 15:22:36
Problema Rubarba Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 5.46 kb
var     x,y,p:array[1..200000] of extended;
        t:array[1..200000] of longint;
        n,i,j,l,poz,ppp: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
    begin
      if y>0 then
        polar:=arctan(y/x) else
      if y<0 then
        polar:=arctan(y/x)+2*pi else polar:=0;
    end else
  if x<0 then
    begin
        polar:=arctan(y/x)+pi;
    end else
  if y=0 then polar:=0 else
  if y<0 then polar:=3*pi/2 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:=0;
  yp:=0;
  for i:=1 to n do
    begin
      xp:=xp+x[i]/n;
      yp:=yp+y[i]/n;
    end;
    ///////////////////////////////////////////////////
   { writeln(xp:0:3,' ',yp:0:3);
    readln;}
    ///////////////////////////////////////////////////
  for i:=1 to n do
    p[i]:=polar(x[i]-xp,y[i]-yp);
  qs(1,n);
  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]; ppp:=i; end;
  for i:=1 to ppp do
    begin
      x[n+i]:=x[i];
      y[n+i]:=y[i];
      p[n+i]:=p[i];
    end;
  for i:=1 to n do
    begin
      x[i]:=x[i+ppp-1];
      y[i]:=y[i+ppp-1];
      p[i]:=p[i+ppp-1];
    end;
  ////////////////////////////////////////////////////////
 { 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;
  x[n+1]:=x[1];
  y[n+1]:=y[1];
  p[n+1]:=p[1];
  j:=3;
  while delta(x[t[poz-1]],y[t[poz-1]],x[t[poz]],y[t[poz]],x[j],y[j])<0 do
    begin
      t[poz]:=j;
      inc(j);
    end;
  for i:=j to n+1 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
      if delta(x[t[poz-1]],y[t[poz-1]],x[t[poz]],y[t[poz]],x[i],y[i])<0 then
        begin
          while delta(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
      else
      t[poz]:=i;
    end;
  dec(poz);
  ///////////////////////////////////////////////////////////
 { 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;
      x1:=x[t[i-1]];
      y1:=y[t[i-1]];
      x2:=x[t[i]];
      y2:=y[t[i]];
      if (x1<>x2)and(y1<>y2) then
      begin
      q:=0;
      w:=1;
      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;
      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;
      end else
      if x1=x2 then
      begin
        q:=0;
        w:=1;
        j:=i;
        while q<w do
          begin
            inc(j);
            q:=abs(x1-x[t[j]]);
            w:=abs(x1-x[t[j+1]]);
          end;
        lun:=q;
        q:=0;
        w:=1000000;
        for j:=1 to n do
          begin
            if y[t[j]]>q then q:=y[t[j]];
            if y[t[j]]<w then w:=y[t[j]];
          end;
        lat:=q-w;
      end else
      begin
        q:=0;
        w:=1;
        j:=i;
        while q<w do
          begin
            inc(j);
            q:=abs(y1-y[t[j]]);
            w:=abs(y1-y[t[j+1]]);
          end;
        lun:=q;
        q:=0;
        w:=1000000;
        for j:=1 to n do
          begin
            if x[t[j]]>q then q:=x[t[j]];
            if x[t[j]]<w then w:=x[t[j]];
          end;
        lat:=q-w;
      end;
      if ar>lun*lat then ar:=lun*lat;
    end;
  writeln(g,ar:0:2);
  close(g);
end.