求最远点对，这是一道经典的旋转卡壳的题目

话说由于是前年写的，之后就没怎么研究过计算几何了……

感觉都不大记得清了，来稍微回忆一下……

首先最远点对一定出现在凸包上显然，然后穷举肯定不行，这时候就需要旋转卡壳了

http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html 这里面介绍的非常详细

1 var q,x,y:array[0..50010] of longint; 2     p,ans,i,j,h,r,k,t,n:longint; 3  4 function cross(i,j,k,r:longint):longint; 5   begin 6     exit((x[i]-x[j])*(y[k]-y[r])-(x[k]-x[r])*(y[i]-y[j])); 7   end; 8  9 function dis(i,j:longint):longint;10   begin11     exit(sqr(x[i]-x[j])+sqr(y[i]-y[j]));12   end;13 14 function max(a,b:longint):longint;15   begin16     if a>b then exit(a) else exit(b);17   end;18 19 procedure swap(var a,b:longint);20   var c:longint;21   begin22     c:=a;23     a:=b;24     b:=c;25   end;26 27 procedure sort(l,r: longint);28   var i,j,p,q: longint;29   begin30     i:=l;31     j:=r;32     p:=x[(l+r) shr 1];33     q:=y[(l+r) shr 1];34     repeat35       while (x[i]
      
       j) then38       begin39         swap(x[i],x[j]);40         swap(y[i],y[j]);41         inc(i);42         j:=j-1;43       end;44     until i>j;45     if l
       
        1) and (cross(q[t],q[t-1],i,q[t-1])>=0) do dec(t);58     inc(t);59     q[t]:=i;60   end;61   k:=t;62   for i:=n-1 downto 1 do63   begin64     while (t>k) and (cross(q[t],q[t-1],i,q[t-1])>=0) do dec(t);65     inc(t);66     q[t]:=i;67   end;68   h:=1;69   r:=k;70   ans:=dis(h,r);71   while (h<=k) and (r<=t) do72   begin73     p:=cross(q[h],q[h+1],q[r+1],q[r]);  //两条直线谁先贴住凸包，这个可以用叉积解决，具体画个图就明白了74     if p<=0 then inc(h) else inc(r);75     ans:=max(ans,dis(q[h],q[r]));76   end;77   writeln(ans);78 end.79 80