POJ 2187凸包の最も遠いユークリッド距離:回転シェルアルゴリズム

G - Beauty Contest
Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit 
Status 
Practice 
POJ 2187
Description
Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates. 
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms. 
Input
* Line 1: A single integer, N 
* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm 
Output
* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other. 
Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

Hint
Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2) 
この問題は私が1本穴をあけたのですね......距離はルート番号をつけた後ではありませんて、それからずっとサンプル例を考えて1ではありませんて、fuck......提出したテンプレートに向かって叩いてまた叩いて、サンプルの答えが得られなくて、それから何発かしてやっと出力したのがルート番号をつけていないことを知って、dist関数のsqrtを取り除けばいいです、ほほほ......

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define eps 1e-8
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d
",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 100005
#define MN 505
#define INF 10000007
using namespace std;
typedef long long ll;
int sgn(const double &x){ return x < -eps? -1 : (x > eps);}
inline double sqr(const double &x){ return x * x;}
inline int gcd(int a, int b){ return !b? a: gcd(b, a % b);}
struct Point
{
    double x, y;
    Point(const double &x = 0, const double &y = 0):x(x), y(y){}
    Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);}
    Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);}
    Point operator *(const double &a)const{ return Point(x * a, y * a);}
    Point operator /(const double &a)const{ return Point(x / a, y / a);}
    bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);}
    bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);}
    friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;}
    friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;}
    friend double dist(const Point &a, const Point &b){ return sqr(a.x - b.x) + sqr(a.y - b.y);}
    void in(){ scanf("%lf %lf", &x, &y); }
    void out()const{ printf("%lf %lf
", x, y); }
};
struct Poly //    
{
    vector<Point>p; //     
    vector<Point>tb;//      
    void in(const int &r)
    {
        p.resize(r);  //          p  a
        for(int i = 0; i < r; i++) p[i].in();
    }
    //         (  m-1==n),            tb(    )
    void isCanHull()
    {
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        int n = p.size();
        tb.resize(n * 2 + 5);
        int m = 0;
        for(int i = 0; i < n; i++)
        {
            while(m > 1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        int k = m;
        for(int i = n - 2; i >= 0; i--)
        {
            while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        tb.resize(m);
        if(m > 1)tb.resize(m - 1);
        //for(int i = 0; i < m - 1; i++) tb[i].out();
    }
    //      ：    ，               
    int maxdist()//int &first,int &second,         
    {
        int n=tb.size(),first,second;
        int Max=-INF;
        if(n==1) return Max;//first=second=0;
        for(int i=0,j=1;i<n;i++)
        {
            while(sgn(det(tb[(i+1)%n]-tb[i],tb[j]-tb[i])-det(tb[(i+1)%n]-tb[i],tb[(j+1)%n]-tb[i]))<0)
                j=(j+1)%n;
            int d=dist(tb[i],tb[j]);
            if(d>Max) Max=d;//first=i,second=j;
            d=dist(tb[(i+1)%n],tb[(j+1)%n]);
            if(d>Max) Max=d;//first=i,second=j;
        }
        return Max;
    }
}poly;

int main()
{
    int n;
    sca(n);
    poly.in(n);
    poly.isCanHull();
    cout<<poly.maxdist()<<endl;;
    return 0;
}