poj 2187 Beauty Contest （旋转卡壳之平面最远点对）

题目链接：http://poj.org/problem?id=2187
题目意思很明了，就是给出点集，求平面最远两点的距离的平方


第一次接触了旋转卡壳，让我注意到了我自已整理的凸包模版的可靠性，那就是还不可靠。。。
用了自己写的卷包裹法->wa，用浙大的模版->wa，用两个半凸多边形也有好多不同的写法，有的写法会出现各种问题，比如所有的点共线的问题。最终，以Graham2这个求凸包函数没wa。
旋转卡壳，可参考：http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html，里面讲的不错。还需要注意的是旋转卡壳的方向与凸包的方向要对应。

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cstdlib>
#define eps 1e-8
#define maxn 100000
#define PI acos(-1.0)
using namespace std;
struct point {int x,y;}points[maxn],temp[maxn],save[maxn];
int n,nsave;
int xmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int max(int a,int b){return a>b? a:b;}
bool zero(int x){return x>0? x<eps:x>-eps;}
bool cmp(const point &a,const point &b)
{
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
int dist2(point p1,point p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
point dir;
void Graham2()
{
	
	sort(temp,temp+n,cmp);
	save[0]=temp[0];
	save[1]=temp[1];
	if(n<=2){nsave=n;return ;}
	int i,top=1;
	for(i=2;i<n;i++)
	{//??ê±??
		while(top>0&& xmult(temp[i],save[top],save[top-1])<=0)top--;
		save[++top]=temp[i];
	}
	// save[++top]=temp[n-2];
	int mid=top;
	for(i=n-2;i>=0;i--)
	{
		while(top>=mid+1 && xmult(temp[i],save[top],save[top-1])<=0)top--;
		save[++top]=temp[i];
	}
	nsave=top;
	
}

int ratat()//Dy×a?¨??
{
	int j=1;
	int ans=0;
	int i;
	save[nsave]=save[0];
	for(i=0;i<nsave;i++)
	{
		while(xmult(save[j+1],save[i+1],save[i])>xmult(save[j],save[i+1],save[i]))
			j=(j+1)%nsave;

		ans=max(ans,max(dist2(save[i],save[j]),
			dist2(save[i+1],save[j+1])
				)
			);
	}
	return ans;
}
void pri()
{
	int i;
	printf("nsave:  %d\n",nsave);
	for(i=0;i<nsave;i++)
		printf("save: %d  %d\n",save[i].x,save[i].y);
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		int i;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&points[i].x,&points[i].y);
			temp[i].x=points[i].x;
			temp[i].y=points[i].y;
		}
		int st=n;
		// n=unique(temp,temp+n,equal_p)-temp;
		Graham2();
		// pri();
		printf("%d\n",ratat());
	}
	return 0;
}