(POJ) 2187 -- Beauty Contest [凸包]

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

to_bou : 凸包

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 5e4 + 6;
const double eps = 1e-9;
const int INF = 1e9 + 7;

#define double int

double add(double a,double b) {
    /*if (a+b <= eps*(abs(a) + abs(b))) return 0;
    else */return a+b;
}

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {
    }
};

P operator+(const P p1,const P p2) {
    return P(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P p1,const P p2) {
    return P(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const double d,const P p) {
    return P(d*p.x,d*p.y);
}

double dot(const P p1,const P p2) {
    return add(p1.x*p2.x,p1.y*p2.y);
}

double cross(const P p1,const P p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

bool operator<(const P &p1,const P &p2) {
    return p1.x<p2.x || p1.x==p2.x && p1.y<p2.y;
}

P p[MAX_N];
P to_bou[MAX_N];

int dis(P p1,P p2) {
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            int a,b;
            scanf("%d %d",&a,&b);
            p[x] = P(a,b);
        }
        sort(p,p+n);
        //cout<<"P : \n";
//        for (int x=0;n>x;x++) {
//            cout<<p[x].x <<' ' << p[x].y<<endl;
//        }
        int sz=0;
        for (int x=0;n>x;x++) {  //down to_bou
            while (sz > 1 && cross(to_bou[sz-2]-to_bou[sz-1],to_bou[sz-1]-p[x])<=0) {
                sz--;
            }
            to_bou[sz++]=p[x];
        }
        //cout<<"TO BOU : \n";
//        for (int x=0;sz>x;x++) {
//            cout << to_bou[x].x<<' '<<to_bou[x].y<<endl;
//        }
        int tmp=sz;
        for (int x=n-2;x>=0;x--) {
            while (sz > tmp && cross(to_bou[sz-2]-to_bou[sz-1],to_bou[sz-1]-p[x])<=0) {
                sz--;
            }
            to_bou[sz++]=p[x];
        }
        int ans=0;
//        cout<<"TO BOU : \n";
        for (int x=0;sz>x;x++) {
//            cout << to_bou[x].x<<' '<<to_bou[x].y<<endl;
            for (int y=0;sz>y;y++) {
                ans = max(ans,dis(to_bou[x],to_bou[y]));
            }
        }
        printf("%d\n",ans);
    }
}