【poj2187】 Beauty Contest

http://poj.org/problem?id=2187 (题目链接)

题意

　　求点集上两点间最长距离

Solution

　　凸包+旋转卡壳。

　　旋转卡壳是看起来很难，但是很好意会也很好实现的算法，但是要真正的搞懂搞透还是有点难度，有篇博客写得很好，也就不再赘述了。

代码

// poj2187

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#define inf 2147483640

#define LL long long

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=50010;

struct point {int x,y;}p[maxn];

int n,top,ans,s[maxn];

int dis(point a,point b) {

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

int cross(point p0,point p1,point p2) {

    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

bool cmp(point a,point b) {

    int t=cross(p[1],a,b);

    if (t>0) return 1;

    if (t<0) return 0;

    return dis(p[1],a)<dis(p[1],b);

}

void Graham() {

    top=0;

    if (n==1) s[++top]=1;

    else if (n==2) {s[++top]=1;s[++top]=2;}

    else {

        s[++top]=1;s[++top]=2;

        for (int i=3;i<=n;i++) {

            while (top>1 && cross(p[s[top-1]],p[s[top]],p[i])<=0) top--;

            s[++top]=i;

        }

    }

}

void RC() {

    int q=2;

    ans=dis(p[s[1]],p[s[2]]);

    for (int i=1;i<=top;i++) {

        while (abs(cross(p[s[i%top+1]],p[s[i]],p[s[q%top+1]]))>abs(cross(p[s[i%top+1]],p[s[i]],p[s[(q-1)%top+1]]))) q=q%top+1;

        ans=max(ans,max(dis(p[s[i%top+1]],p[s[q]]),dis(p[s[i]],p[s[q]])));

    }

}

int main() {

    while (scanf("%d",&n)!=EOF) {

        int k=1;

        for (int i=1;i<=n;i++) {

            scanf("%d%d",&p[i].x,&p[i].y);

            if (p[i].x==p[k].x ? p[i].y<p[k].y : p[i].x<p[k].x) k=i;

        }

        point p0=p[1];p[1]=p[k];p[k]=p0;

        sort(p+2,p+1+n,cmp);

        Graham();

        RC();

        printf("%d\n",ans);

    }

    return 0;

}