题目链接：http://poj.org/problem?id=2187
这个题目做过，不过上次是直接枚举的结果，这次换一种方法，旋转卡壳来计算凸包直径，这个方法比以前的要快好多
主要思想就是用两条平行线来夹住凸包，那么不断旋转这两条平行线，可想而知凸包的直径一定就是两条平行线和凸包
顶点的交点的长度，这时候再枚举就可以了！
具体解说推荐一篇博客：http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html
这个图片就是那篇博客上的图片，可以很好的解说下面的卡壳部分的代码
for(i=0;i<k;i++)
{
while(across(po[i],po[i+1],po[q]) < across(po[i],po[i+1],po[q+1]))
q=(q+1)%k;
ans=MAX(ans,MAX(dis(po[i],po[q]),dis(po[i+1],po[q+1])));
}
就是这一点代码，其实还是很好理解的，按照相当于按照逆时针旋转卡壳，这里是按照一条边对应一个点来的，所以这里枚举的时候
是一条边和一个点，通过凸包的面积单调性来求对踵点
有读者可能会认为上面的算法不是线性的，其实是线性的，即使里面有个while循环，但是这个循环不会绕凸包两圈以上的
因为下一次的对踵点一定是在上一个之后，所以就在原来的基础上去找就OK 了，其实仔细想想还是比较好理解的！
其实下面的代码是求多边形的长，直径，那么取的是对踵点之间的最长距离，如果是求宽度，那么就是求多边形的
对踵点之间的最小距离，那么直接把下面的函数MAX改成MIN就OK 了，因为最大和最小都一定是产生在对踵点之
间的！
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
#define eps 1e-8
#define PI 3.14159265
#define MAX(a,b) (a>b?a:b)
struct point
{
int x;
int y;
}po[55500],temp;
int n,pos;
bool zero(double a)
{
return fabs(a) < eps;
}
int dis(point &a,point &b)//返回两点之间距离的平方
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int across(point &a,point &b,point &c)//求a b and a c 的X积
{
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
int cmp(const void *a,const void *b)
{
return across(po[0],*(point*)a,*(point*)b) > 0 ? -1 : 1;
}
int select()
{
int i,j,k=1;
for(i=2;i<n;i++)
{
if(across(po[0],po[k],po[i])==0)
{
if(dis(po[0],po[k]) < dis(po[0],po[i]))
po[k]=po[i];
}
else
po[++k]=po[i];
}
return k+1;
}
int graham(int num)
{
int i,j,k=2;
//////////////////////////////////////////
po[num]=po[0];//fangbian
num++;
int p,q;
int ans=0;
int t;
if(num<20)
{
for(i=0;i<num;i++)
for(j=0;j<num;j++)
{
t=dis(po[i],po[j]);
if(t > ans)
ans=t;
}
printf("%d\n",ans);
return 0;
}
for(i=3;i<num;i++)
{
while(across(po[k-1],po[k],po[i]) < -eps)
{k--;}
po[++k]=po[i];//就这个循环结束，不需要了！
}
/*
for(i=0;i<k;i++)
printf("%lf %lf\n",po[i].x,po[i].y);
*/
//for(i=0;i<k;i++)
//for(j=0;j<k;j++)
//{
//t=dis(po[i],po[j]);
//if(t > ans)
//ans=t;
//}
ans=0;
p=1,q=2;
for(i=0;i<k;i++)
{
while(across(po[i],po[i+1],po[q]) < across(po[i],po[i+1],po[q+1]))
q=(q+1)%k;
ans=MAX(ans,MAX(dis(po[i],po[q]),dis(po[i+1],po[q+1])));
}
printf("%d\n",ans);
return 0;
}
int main()
{
int i,j,k;
point my_temp;
int ans;
int t;
while(scanf("%d",&n)!=EOF)
{
ans=0;
scanf("%d%d",&po[0].x,&po[0].y);
temp=po[0];
pos=0;
for(i=1;i<n;i++)
{
scanf("%d%d",&po[i].x,&po[i].y);
if(po[i].y < temp.y)
temp=po[i],pos=i;
}
if(n<100)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
t=dis(po[i],po[j]);
if(t > ans)
ans=t;
}
printf("%d\n",ans);
continue;
}
my_temp=po[0];
po[0]=po[pos];
po[pos]=my_temp;
qsort(po+1,n-1,sizeof(po[0]),cmp);
graham(select());
}
return 0;
}