题链：
http://poj.org/problem?id=2187
题解：
计算几何，凸包，旋转卡壳
一个求凸包直径的裸题，旋转卡壳入门用的。
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 50050
using namespace std;
const double eps=1e-8;
int sign(double x){
if(fabs(x)<=eps) return 0;
return x<0?-1:1;
}
struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
void Read(){scanf("%lf%lf",&x,&y);}
};
typedef Point Vector;
bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}
bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}
Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}
Point D[MAXN],C[MAXN];
double GL2(Vector A){//Get_Length^2
return A*A;
}
double DA(Point P,Point P1,Point P2){//Directed_Area
return (P-P1)^(P-P2);
}
int Andrew(int dnt){
int cnt=0,k;
sort(D,D+dnt);
dnt=unique(D,D+dnt)-D;
for(int i=0;i<dnt;i++){
while(cnt>1&&sign((C[cnt-1]-C[cnt-2])^(D[i]-C[cnt-2]))<=0) cnt--;
C[cnt++]=D[i];
} k=cnt;
for(int i=dnt-2;i>=0;i--){
while(cnt>k&&sign((C[cnt-1]-C[cnt-2])^(D[i]-C[cnt-2]))<=0) cnt--;
C[cnt++]=D[i];
}
return cnt-(dnt>1?1:0);
}
double RC_GD(int hnt){//Rotating_Calipers_Get_Diameter
if(hnt==1) return 0;
if(hnt==2) return GL2(C[1]-C[0]);
double Di=0; int j=0; C[hnt]=C[0];
for(int i=0;i<hnt;i++){
while(sign(DA(C[j],C[i],C[i+1])-DA(C[j+1],C[i],C[i+1])<=0)) j=(j+1)%hnt;
Di=max(Di,GL2(C[j]-C[i])); Di=max(Di,GL2(C[j]-C[i+1]));
}
return Di;
}
int main(){
int N; scanf("%d",&N);
for(int i=0;i<N;i++)
D[i].Read();
printf("%d",(int)RC_GD(Andrew(N)));
return 0;
}