(POJ) 2187 -- Beauty Contest [最遠對點，旋轉卡尺]

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

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

const double eps = 1e-9;
const int MAX_N = 50006;

#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*(double d,const P p1) {
                   return P(p1.x*d,p1.y*d);
}

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

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

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

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 u[MAX_N],d[MAX_N];

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<<"These points : \n";
          //for (int x=0;n>x;x++) cout<<p[x].x<<' '<<p[x].y<<endl;
          
          int ans=0;
          int szu=0,szd=0; //上凸包，下凸包 
          for (int x=0;n>x;x++) {
              while (szd>1 && cross(d[szd-2]-d[szd-1],d[szd-1]-p[x]) <= 0) szd--;
              while (szu>1 && cross(u[szu-2]-u[szu-1],u[szu-1]-p[x]) >= 0) szu--;
              u[szu++]=p[x];
              d[szd++]=p[x];
          }
          
          //cout<<"down to_bou\n";
          //for (int x=0;szd>x;x++) cout<<d[x].x<<' '<<d[x].y<<endl;
          
          //cout<<"up to_bou\n";
          //for (int x=0;szu>x;x++) cout<<u[x].x<<' '<<u[x].y<<endl;
          
          if (szu>=2) d[szd]=u[szu-2];
          
          for (int i=0,j=szu-1;i<szu && j>0;) {
              ans = max(ans,dis(d[i],u[j]));
              
              if (cross(d[i]-d[i+1],u[j]-u[j-1]) <= 0) i++;
              else j--;
          }
          
          printf("%d\n",ans);
    }
}