ZOJ1453 (Pascal)

zoj1453.pas

type
  point=record
          x,y:longint;
        end;

const
  maxn=1000;

var
  a:array [0..maxn] of point;
  ans:double;
  n:longint;

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

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

function dis(p,q:point):longint;
begin
  exit(sqr(p.x-q.x)+sqr(p.y-q.y));
end;

function cross(a,p,q:point):longint;
begin
  exit((p.x-a.x)*(q.y-a.y)-(p.y-a.y)*(q.x-a.x));
end;

function cmp(p,q:point):boolean;
var
  t:longint;

begin
  t:=cross(a[1],p,q);
  exit((t>0) or ((t=0) and (dis(a[1],p)>dis(a[1],q))));
end;

procedure qsort(l,r:longint);
var
  i,j:longint;
  m:point;

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

procedure main;
var
  i,k,top:longint;
  stack:array [0..maxn] of point;

begin
  readln(n);
  if n=0 then halt;
  fillchar(stack,sizeof(stack),0);
  fillchar(a,sizeof(a),0);
  k:=1;
  for i:=1 to n do
    begin
      readln(a[i].x,a[i].y);
      if (a[i].x<a[k].x) or ((a[i].x=a[k].x) and (a[i].y<a[k].y)) then k:=i;
    end;
  if n=1 then
    begin
      writeln('0.00');
      exit;
    end
  else if n=2 then
    begin
      writeln(2*sqrt(dis(a[1],a[2])):0:2);
      exit;
    end;
  swap(a[1],a[k]);
  qsort(2,n);
  stack[1]:=a[1];
  stack[2]:=a[2];
  stack[3]:=a[3];
  top:=3;
  inc(n);
  a[n]:=a[1];
  for i:=4 to n do
    begin
      while (cross(stack[top-1],stack[top],a[i])<0) and (top>2) do dec(top);
      inc(top);
      stack[top]:=a[i];
    end;
  ans:=sqrt(dis(stack[1],stack[top]));
  for i:=1 to top-1 do ans:=ans+sqrt(dis(stack[i],stack[i+1]));
  writeln(ans:0:2);
end;

begin
  while true do main;
end.