ac1082.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1082;
const
  maxn=30000;
  zero=1e-6;
type
  dot=record x,y:longint;end;
var
  d:array[1..maxn]of dot;
  n,i,j,l,m:longint;
  td:dot;
  ans:extended;
function cross(a,b,c,d:dot):shortint;
  var
    x1,x2,y1,y2:extended;
  begin
    x1:=b.x*1.0-a.x;y1:=b.y*1.0-a.y;
    x2:=d.x*1.0-c.x;y2:=d.y*1.0-c.y;
    x1:=x1*y2-x2*y1;
    if abs(x1)<zero then
      cross:=0
    else if x1>0 then
      cross:=1
    else
      cross:=-1;
  end;
procedure qsort(s,t:word);
  var
    p,i,j:word;
    td:dot;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    td:=d[p];d[p]:=d[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (cross(d[1],d[j],d[1],td)<=0) do dec(j);
      if i=j then break;d[i]:=d[j];inc(i);
      while (i<j) and (cross(d[1],d[i],d[1],td)>=0) do inc(i);
      if i=j then break;d[j]:=d[i];dec(j);
    until i=j;
    d[i]:=td;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function next(x:word):word;
  begin
    if x=l then next:=1 else next:=x+1;
  end;
procedure update(a,b:integer);
  var
    dist:real;
  begin
    dist:=sqr(d[a].x*1.0-d[b].x)+sqr(d[a].y*1.0-d[b].y);
    if dist>ans then ans:=dist;
  end;
begin
  repeat
    read(n);
    if n<2 then begin
      if n=1 then read(j,j);
      writeln('0.00');
      continue;
    end
    else if n=2 then begin
      read(i,j,l,m);
      writeln(sqrt(sqr(i*1.0-l)+sqr(j*1.0-m)):0:2);
      continue;
    end;

    for i:=1 to n do begin
      read(d[i].x,d[i].y);
      if (d[i].y<d[1].y) or (d[i].y=d[1].y) and (d[i].x<d[1].x) then begin
        td:=d[1];d[1]:=d[i];d[i]:=td;
      end;
    end;

    qsort(2,n);

    j:=2;
    for i:=3 to n do
      if cross(d[1],d[j],d[1],d[i])>0 then
        inc(j)
      else if (d[i].y>d[j].y) or (d[i].y=d[j].y) and (d[i].x>d[j].x) then
        d[j]:=d[i];
    l:=2;
    for i:=3 to j do begin
      while cross(d[l-1],d[l],d[l-1],d[i])<=0 do dec(l);
      inc(l);d[l]:=d[i];
    end;

    ans:=0;m:=3;
    for i:=1 to l do begin
      j:=next(i);
      while cross(d[i],d[j],d[m],d[next(m)])>0 do begin
        m:=next(m);
      end;
      update(i,m);update(j,m);
    end;
    writeln(sqrt(ans):0:2);
  until seekeof;
end.