凸包+旋转卡壳--POJ 2187

题意：求平面点集上的最远点对

思路：先求出凸包，最远的对肯定在凸包上面，但是下面暴力的话时间复杂度o(n^2)，旋转卡壳也是遍历，不过遍历的时候把复杂度降下来啦！

旋转卡壳见：http://blog.csdn.net/hitfanyu/article/details/5522589

#include <iostream>#include<algorithm>#include<cmath>#include<cstdio>#include<cstdlib>#define eps 1e-8using namespace std;struct point{    int x,y;} p[50005],res[50005];int cross(point p0, point p1, point p2){    return(p1.x- p0.x) * (p2.y- p0.y) - (p1.y- p0.y) * (p2.x- p0.x);}int   dist(point a,point b){    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}bool cmp(point  a, point  b){    return(a.y< b.y|| (a.y== b.y&& a.x< b.x));}int Graham(int n){    int len, top=1;    sort(p, p+ n, cmp);    res[0] = p[0];    res[1] = p[1];    for(int i=2; i< n; i++)    {        while(top&& cross(res[top], res[top-1], p[i])<=eps)top--;        res[++ top] = p[i];    }    len= top;    res[++ top] = p[n-2];    for(int i= n-3; i>=0; i--)    {        while(top!= len&& cross(res[top], res[top-1], p[i])<=eps)top--;        res[++ top] = p[i];    }    return top;}int diameter(int n){    int i,j=1,ans=-1;    res[n]=res[0];    for(i=0; i<n; i++)    {        while(fabs(cross(res[i+1],res[j+1],res[i]))>fabs(cross(res[i+1],res[j],res[i]) ))            j=(j+1)%n;        ans=max(ans,max(dist(res[i],res[j]),dist(res[i+1],res[j+1])));    }    return ans;}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        for(int i=0; i<n; i++)            cin  >> p[i].x >> p[i].y;        int top=Graham(n);        cout << diameter(top) << endl;    }    return 0;}