旋转卡壳

例题：POJ 2187

旋转卡壳一般用来求平面中最远的两点的距离。

我们很明显的可以发现，最远的两个点必然在凸包上，于是我们求出凸包之后，扫对踵点。利用凸包上的点依次与对应边产生的距离成单峰函数,面积上升到最高点后，又会下降。(具体证明可以从凸包定义入手 用反证法解决)

然后就可以O(n) 得到最远的距离了，但是求Graham求凸包是 O(n*logn) 的。

AC代码：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10;
int n,res,top;
struct node{int x,y;}t[N],st[N];

inline int dis(node a,node b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline int corss(node a,node b,node c){
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int cmp(node a,node b){
	double a1=atan2(a.y-t[1].y,a.x-t[1].x),a2=atan2(b.y-t[1].y,b.x-t[1].x);
	return a1==a2?a.x<b.x:a1<a2;
}
void Graham(){
	int id=1;
	for(int i=2;i<=n;i++)	
		if(t[id].y>t[i].y||(t[id].y==t[i].y&&t[id].x>t[i].x))	id=i;
	swap(t[1],t[id]);	sort(t+2,t+1+n,cmp);	st[++top]=t[1];
	for(int i=2;i<=n;i++){
		while(top>=2&&corss(st[top-1],t[i],st[top])>=0)	top--;
		st[++top]=t[i];
	}
}
int main(){
	while(cin>>n){
		res=top=0;
		for(int i=1;i<=n;i++)	scanf("%d %d",&t[i].x,&t[i].y);
		Graham();	st[top+1]=t[1]; int j=2;
		for(int i=1;i<=top;i++){
			while((corss(st[i],st[i+1],st[j+1]))>(corss(st[i],st[i+1],st[j]))){
				j++;	if(j>top)	j=1;
			}
			res=max(res,max(dis(st[i],st[j]),dis(st[(i+1)%top],st[(j+1)%top])));
		}
		cout<<res<<endl;
	}
	return 0;
}