fc.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 100 行

{
ID:maigoak1
PROG:fc
}

program fc;
const
  maxn=10000;
type
  coord=record
    x,y:real;
  end;
var
  fin,fout:text;
  dot,hull:array[1..maxn]of coord;
  n,i,p:integer;
  len:real;
  tdot:coord;
function dist(a,b:coord):real;
  begin
    dist:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
  end;
function cross(a,b,c,d:coord):integer;
  var
    m,n:coord;
    pro:real;
  begin
    m.x:=b.x-a.x;m.y:=b.y-a.y;
    n.x:=d.x-c.x;n.y:=d.y-c.y;
    pro:=m.x*n.y-n.x*m.y;
    if abs(pro)<0.001 then
      cross:=0
    else if pro>0 then
      cross:=1
    else
      cross:=-1;
  end;
procedure qsort(s,t:integer);
  var
    p,i,j:integer;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tdot:=dot[p];
    dot[p]:=dot[s];
    i:=s;j:=t;
    repeat
      while (i<j) and
        ((cross(dot[1],tdot,dot[1],dot[j])>0) or
         (cross(dot[1],tdot,dot[1],dot[j])=0) and
         (dist(dot[1],dot[j])<dist(dot[1],tdot))) do
         dec(j);
      dot[i]:=dot[j];
      if i=j then break;inc(i);
      while (i<j) and
        ((cross(dot[1],tdot,dot[1],dot[i])<0) or
         (cross(dot[1],tdot,dot[1],dot[i])=0) and
         (dist(dot[1],dot[i])>dist(dot[1],tdot))) do
         inc(i);
      dot[j]:=dot[i];
      if i=j then break;dec(j);
    until i=j;
    dot[i]:=tdot;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
begin
  assign(fin,'fc.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do begin
    readln(fin,dot[i].x,dot[i].y);
    if (dot[i].y<dot[1].y) or
      ((dot[i].y=dot[1].y) and (dot[i].x<dot[1].x)) then begin
        tdot:=dot[1];dot[1]:=dot[i];dot[i]:=tdot;
      end;
  end;
  close(fin);

  qsort(2,n);

  hull[1]:=dot[1];hull[2]:=dot[2];p:=2;
  for i:=3 to n do
    if cross(dot[1],dot[i-1],dot[1],dot[i])<>0 then begin
      while (p>1) and (cross(hull[p-1],hull[p],hull[p],dot[i])<=0) do
        dec(p);
      inc(p);
      hull[p]:=dot[i];
    end;

  len:=dist(hull[1],hull[p]);
  for i:=2 to p do
    len:=len+dist(hull[i-1],hull[i]);

  assign(fout,'fc.out');
  rewrite(fout);
  writeln(fout,len:0:2);
  close(fout);
end.