很久以前的凸包模版题，又被翻了出来验证旋转卡壳法。。求凸包后枚举2点求距离也可以的。
//Memory: 548K
//Time: 110MS
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 50001
int top;
int max(int a,int b)
{
return a>b?a:b;
}
struct point
{
int x;
int y;
}p[N],stack[N];
int dist(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int multiply(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int cmp(point a,point b)
{
if(multiply(a,b,p[0])>0)
return 1;
if(multiply(a,b,p[0])==0 && dist(a,p[0])<dist(b,p[0]))
return 1;
return 0;
}
void graham(point p[],point stack[],int n) //求凸包
{
int i,k=0;
top=2;
point temp;
for(i=1;i<n;i++)
if(p[i].y<p[k].y || ((p[i].y==p[k].y) && (p[i].x<p[k].x)))
k=i;
temp=p[k];
p[k]=p[0];
p[0]=temp;
sort(p+1,p+n,cmp);
stack[0]=p[0];
stack[1]=p[1];
stack[2]=p[2];
for(i=3;i<n;i++)
{
while(top>1 && multiply( p[i],stack[top],stack[top-1] )>=0 )
top--;
stack[++top]=p[i];
}
stack[++top]=p[0];
}
int rotating_calipers() //旋转卡壳求凸包直径
{
int q=1;
int ans=0;
for(int p=0;p<top;p++)
{
while(multiply(stack[p+1],stack[q+1],stack[p]) > multiply(stack[p+1], stack[q], stack[p]))
q=(q+1)%top;
ans=max(ans, max(dist(stack[p], stack[q]), dist(stack[p+1], stack[q+1])));
}
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i;
int ans=0;
for(i=0;i<n;i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
}
graham(p,stack,n);
ans=rotating_calipers();
printf("%d\n",ans);
}
}