POJ 2187 Beauty Contest（凸包+旋转卡壳）

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目：求出凸包的最大直径。

http://poj.org/problem?id=2187

先对多边形求凸包，以前的知识不多说。

然后用旋转卡壳求出最大直径。

其实就是两条平行线夹出凸包，旋转。

如果pa,pb为最远点对的话，那么过pa,pb的平行线经过旋转，肯定有一条与多边形的边重合。

利用这点，枚举每一条边，找到离边最远的点，看上去这还是N^2的，和枚举一样。

不过由于是凸多边形，对于某一条边，点到边的距离呈现单峰函数。

那么就可以利用上一条边的最远点依次后移得到。

这篇说得不错：http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<ctime>
#include<cassert>
#define LL long long
#define eps 1e-8
#define inf 999999.0
#define zero(a) abs(a)<eps
#define N 20
#define pi acos(-1.0)
using namespace std;
struct Point{
    int x,y;
}p[50005];
int n;
vector<Point >s;
int dist(Point p1,Point p2){
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int xmul(Point p0,Point p1,Point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//Graham_scan求凸包
bool cmp(Point p1,Point p2){
    if(xmul(p[0],p1,p2)>eps)  return true;
    else if(zero(xmul(p[0],p2,p1))&&dist(p[0],p1)<dist(p[0],p2))  return true;
    return false;
}
void Graham_scan(){
    for(int i=1;i<n;i++)
        if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
            swap(p[i],p[0]);
    sort(p+1,p+n,cmp);
    s.clear();
    s.push_back(p[0]);s.push_back(p[1]);
    for(int i=2;i<n;i++){
        while(s.size()>=2&&xmul(s[s.size()-2],s[s.size()-1],p[i])<eps) s.pop_back();
        s.push_back(p[i]);
    }
}
//旋转卡壳求凸包直径
void Rotating_Calipers(){
    int ans=0,len=s.size();
    int j=1;
    s.push_back(s[0]);
    for(int i=0;i<len;i++){
        //找到离直线最远的点
        while(abs(xmul(s[i],s[i+1],s[j+1]))>abs(xmul(s[i],s[i+1],s[j])))
            j=(j+1)%len;
        ans=max(ans,max(dist(s[i+1],s[j]),dist(s[i],s[j])));
    }
    printf("%d\n",ans);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        Graham_scan();
        Rotating_Calipers();
    }
    return 0;
}