poj 2187 Beauty Contest

poj 2187 Beauty Contest

#include <cstdio>#include <cmath>#include <algorithm>#define vector pointusing std::sort;using std::swap;using std::max;const double PI = acos(-1.00);struct point{    int x,y;    point(int xx = 0,int yy = 0)    {        x = xx;        y = yy;    }    point operator - (point s)    {        return point(x - s.x, y - s.y);    }    double len()    {        return sqrt(x * x + y * y + 0.0);    }    int len2()    {        return x * x + y * y;    }};point p[50010];int n,l,hull_list[50010];int cross_product(vector v1,vector v2){    return v1.x * v2.y - v1.y * v2.x;}bool cmp(point& a,point& b){    int cp = cross_product(vector(a - p[0]),vector(b - p[0]));    if(cp > 0 || (cp == 0 && vector((a - p[0])).len2() < vector((b - p[0])).len2() ) )        return true;    else        return false;}//基点取p[0]，逆时针扫描，返回凸包上的点数int Graham_scan(){    int top = 1;    sort(p + 1,p + n,cmp);    hull_list[0] = 0;    hull_list[1] = 1;    for(int i = 2;i < n;i++)    {        while(top >= 1 && cross_product(vector(p[hull_list[top]] - p[hull_list[top - 1]]),vector(p[i] - p[hull_list[top]])) <= 0)//<=为一条边上只留两个顶点，<则为一条边上可以留多个顶点 top--;        hull_list[++top] = i;    }    return top + 1;}//旋转卡壳求最远点对的距离的平方，p[]的大小要比n的最大值多2,凸包点集的顺序为逆时针int rotating_caliper(point p[],int& n){    int counter = 0,dis = 0;    p[n] = p[0];    p[n + 1] = p[1];    int j = 2;    for(int i = 0;i < n;i++)    {        while(cross_product(p[i + 1] - p[i],p[j] - p[i]) < cross_product(p[i + 1] - p[i],p[j + 1] - p[i])) j = (j + 1) % n;        dis = max(max((p[i] - p[j]).len2(),(p[i + 1] - p[j]).len2()),dis);    }    return dis;}int main(){    while(~scanf("%d",&n))    {        int lowest = 0;        for(int i = 0;i < n;i++)        { scanf("%d%d",&p[i].x,&p[i].y); if(p[lowest].y > p[i].y || (p[lowest].y == p[i].y && p[lowest].x > p[i].x))     lowest = i;        }        swap(p[lowest],p[0]);        l = Graham_scan();        for(int i = 0;i < l;i++) p[i] = p[hull_list[i]];        printf("%dn",rotating_caliper(p,l));    }    return 0;}