POJ3348 (Pascal)

poj3348.pas

type
  pq=record
       p,q:longint;
     end;

var
  n,i,k,ans,temp,top:longint;
  x,y:array [0..10000] of longint;
  stack:array [0..10000] of pq;
  t:pq;

function dis(p,q:longint):longint;
begin
  exit(sqr(p)+sqr(q));
end;

function cmp(a,b,c,d:longint):boolean;
var
  cross:longint;

begin
  cross:=a*d-b*c;
  exit((cross>0) or ((cross=0) and (dis(a,b)>dis(c,d))));
end;

function cross(b,a,c:pq):longint; // BA x BC
begin
  dec(a.p,b.p);
  dec(a.q,b.q);
  dec(c.p,b.p);
  dec(c.q,b.q);
  exit(a.p*c.q-a.q*c.p);
end;

procedure swap(var x,y:longint);
var
  t:longint;

begin
  t:=x;
  x:=y;
  y:=t;
end;

procedure qsort(l,r:longint);
var
  i,j,p,q:longint;

begin
  i:=l;
  j:=r;
  p:=x[(l+r) shr 1];
  q:=y[(l+r) shr 1];
  repeat
    while cmp(x[i],y[i],p,q) do inc(i);
    while cmp(p,q,x[j],y[j]) do dec(j);
    if i<=j then
      begin
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        inc(i);
        dec(j);
      end;
  until i>j;
  if l<j then qsort(l,j);
  if r>i then qsort(i,r);
end;

begin
  readln(n);
  k:=1;
  for i:=1 to n do
    begin
      readln(x[i],y[i]);
      if (x[i]<x[k]) or ((x[i]=x[k]) and (y[i]<y[k])) then k:=i;
    end;
  swap(x[1],x[k]);
  swap(y[1],y[k]);
  for i:=2 to n do
    begin
      dec(x[i],x[1]);
      dec(y[i],y[1]);
    end;
  x[1]:=0;
  y[1]:=0;
  qsort(2,n);
  inc(n);
  stack[1].p:=x[1];
  stack[1].q:=y[1];
  stack[2].p:=x[2];
  stack[2].q:=y[2];
  stack[3].p:=x[3];
  stack[3].q:=y[3];
  top:=3;
  for i:=4 to n+1 do
    begin
      t.p:=x[i];
      t.q:=y[i];
      while (cross(stack[top-1],stack[top],t)<=0) and (top>2) do dec(top);
      inc(top);
      stack[top]:=t;
    end;
  for i:=1 to top do inc(ans,cross(stack[0],stack[i-1],stack[i]));
  writeln(trunc(ans/100));
end.