POJ 2187 Beauty Contest (旋转卡壳最远点对)

本文主要是介绍POJ 2187 Beauty Contest (旋转卡壳最远点对)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2187
题意：给出二维平面上n个点的坐标，求距离最远的点对距离的平方。

显然距离最远的两个点在这些散点的凸包上，然后用旋转卡壳的算法找出最远点对，具体原理参见这位大佬的博客http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html
大概是利用凸包上的点依次与对应边产生的距离成单峰函数这条性质，逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。这样就可以在 $O(n)$ 的时间复杂度内完成。
虽然看起来很复杂，但利用叉积实现起来只有一个for循环枚举边的事，不过短短几行。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
struct node
{int x,y;
} a[50010],p[50010];
int top,n,ans;
int cross(node p0,node p1,node p2)//计算叉乘，p0p1 X p0p2 注意p0,p1,p2的位置，这个决定了方向
{return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
int dis(node a,node b)//计算距离，这个用在了当两个点在一条直线上
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);//因为这个题求的是距离的平方，所以没有开根号
}
bool cmp(node p1,node p2)//极角排序
{int z=cross(a[1],p1,p2);if(z>0||(z==0&&dis(a[1],p1)<dis(a[1],p2)))return 1;return 0;
}
void Graham()
{int k=1;for(int i=1;i<=n;i++)if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))k=i;swap(a[1],a[k]);//找p[0]，取最下，同最下取最左sort(a+2,a+n+1,cmp);top=2;p[1]=a[1];p[2]=a[2];for(int i=3;i<=n;i++)//控制进栈出栈{while(cross(p[top-1],p[top],a[i])<=0&&top>1)top--;top++;p[top]=a[i];}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}Graham();p[top+1]=p[1];int j=2;for(int i=1;i<=top;i++)//旋转卡壳{while(cross(p[i],p[i+1],p[j+1])>cross(p[i],p[i+1],p[j])){j++;if(j==top+1) j=1;}ans=max(ans,dis(p[i],p[j]));}printf("%d\n",ans);return 0;
}