求最远点对，这是一道经典的旋转卡壳的题目
话说由于是前年写的，之后就没怎么研究过计算几何了……
感觉都不大记得清了，来稍微回忆一下……
首先最远点对一定出现在凸包上显然，然后穷举肯定不行，这时候就需要旋转卡壳了
http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html 这里面介绍的非常详细
var q,x,y:array[..] of longint;
p,ans,i,j,h,r,k,t,n:longint; function cross(i,j,k,r:longint):longint;
begin
exit((x[i]-x[j])*(y[k]-y[r])-(x[k]-x[r])*(y[i]-y[j]));
end; function dis(i,j:longint):longint;
begin
exit(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r: longint);
var i,j,p,q: longint;
begin
i:=l;
j:=r;
p:=x[(l+r) shr ];
q:=y[(l+r) shr ];
repeat
while (x[i]<p) or (x[i]=p) and (y[i]<q) do inc(i);
while (p<x[j]) or (p=x[j]) and (q<y[j]) do dec(j);
if not(i>j) then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
readln(n);
for i:= to n do
readln(x[i],y[i]);
sort(,n);
q[]:=;
t:=;
for i:= to n do
begin
while (t>) and (cross(q[t],q[t-],i,q[t-])>=) do dec(t);
inc(t);
q[t]:=i;
end;
k:=t;
for i:=n- downto do
begin
while (t>k) and (cross(q[t],q[t-],i,q[t-])>=) do dec(t);
inc(t);
q[t]:=i;
end;
h:=;
r:=k;
ans:=dis(h,r);
while (h<=k) and (r<=t) do
begin
p:=cross(q[h],q[h+],q[r+],q[r]); //两条直线谁先贴住凸包，这个可以用叉积解决，具体画个图就明白了
if p<= then inc(h) else inc(r);
ans:=max(ans,dis(q[h],q[r]));
end;
writeln(ans);
end.