程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2187 凸包的最遠歐幾裡得距離：旋轉卡殼算法

POJ 2187 凸包的最遠歐幾裡得距離：旋轉卡殼算法

編輯：C++入門知識

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

Sample Output

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

這題坑了我一把啊……距離算的不是開根號的後的，然後一直在想樣例為咐是2而不是1，fuck……對著上交的模板敲了又敲，就是得不出樣例答案，然後搞了幾發才知道輸出的是沒開根號的，把dist函數的sqrt去掉就行了，呵呵……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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\n",a)
#define f(i,a,n) for(i=a;i 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\n", x, y); }
};
struct Poly //多邊形類
{
    vectorp; //順時針凸包
    vectortb;// 逆時針凸包
    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;iMax) 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<