POJ 1228 凸包惟一性判斷（多邊形模板）

E - Grandpa's Estate Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1228

Description

Being the only living descendant of his grandfather, Kamran the Believer inherited all of the grandpa's belongings. The most valuable one was a piece of convex polygon shaped farm in the grandpa's birth village. The farm was originally separated from the neighboring farms by a thick rope hooked to some spikes (big nails) placed on the boundary of the polygon. But, when Kamran went to visit his farm, he noticed that the rope and some spikes are missing. Your task is to write a program to help Kamran decide whether the boundary of his farm can be exactly determined only by the remaining spikes.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains an integer n (1 <= n <= 1000) which is the number of remaining spikes. Next, there are n lines, one line per spike, each containing a pair of integers which are x and y coordinates of the spike.

Output

There should be one output line per test case containing YES or NO depending on whether the boundary of the farm can be uniquely determined from the input.

Sample Input

1
6 
0 0
1 2
3 4
2 0
2 4 
5 0

Sample Output

NO

題意：判斷凸包是否惟一。

思路：把凸包的結點先變成頂點，然後再判斷兩個頂點之間是否還有結點，如果有頂點，說明兩個頂點之間的邊是惟一的。如果頂點之間沒有結點，所以這兩個頂點之間可以有其他加入的結點讓這個凸包不惟一。

#include 
#include 
#include 
#include 
#include 
#define MAX 111116
#define eps 1e-7
using namespace std;
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 sqrt(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 Line //線段類
{
    Point s, t;
    Line() {}
    Line(const Point &s, const Point &t):s(s), t(t) {}
    void in() { s.in(),t.in(); }
    double pointDistLine(const Point &p)
    {
        if(sgn(dot(t - s, p - s)) < 0)return dist(p, s);
        if(sgn(dot( s - t, p - t)) < 0)return dist(p, t);
        return fabs(det(t - s, p - s)) / dist(s, t);
    }
    bool pointOnLine(const Point &p)
    {
        return sgn(det(s - p, t - p)) == 0 && sgn(dot(s - p, t - p)) < 0;
    }
};
struct Poly //多邊形類
{
    vectora;
    vectorp; //順時針凸包
    vectortb;// 逆時針凸包
    void in(const int &r)
    {
        p.resize(r);  //不早凸包的時候可以把p改為a
        for(int i = 0; i < r; i++) p[i].in();
    }

    //計算多邊形的周長
    double perimeter()
    {
        double sum=0;
        int n=a.size();
        for(int i=0;i0&&d1<=0&&d2>0) num++;
            if(k<0&&d2<=0&&d1>0) num--;
        }
        return num!=0;
    }

    //計算多邊形邊界的格點數
    int border()
    {
        int num=0,i,n=a.size();
        for(i=0;i 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();
    }

    //判斷點t(圓心)是否在凸包內部，這個是O(logn)的算法
    bool isContainOlogn(const Point &t)
    {
        int n = tb.size();
        if(n < 3)return 0;
        Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0;
        int l = 0, r = n;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1;
            int k = sgn(det(tb[l] - g, tb[mid] - g) );
            int dl = sgn(det(tb[l] - g, t - g) );
            int dr = sgn(det(tb[mid] - g, t - g) );
            if(k > 0)
            {
                if(dl >= 0 && dr < 0) r = mid;
                else l = mid;
            }
            else
            {
                if(dl < 0 && dr >= 0) l = mid;
                else r = mid;
            }
        }
        r %= n;
        int res = sgn(det(tb[l] - t, tb[r] - t));
        if(res >= 0) return true;
        return false;
    }

    //判斷凸包是否惟一,若頂點之間有點說明惟一
    bool isUnique()
    {
        if(sgn(getArea()) == 0) return false;
        int n = tb.size();
        int np = p.size();
        for(int i = 0; i < n; i++)
        {
            Line line(tb[i], tb[(i + 1) % n]);
            bool isFind = false;
            for(int j = 0; j < np; j++)
            {
                if(line.pointOnLine(p[j]))
                {
                    isFind = true;
                    break;
                }
            }
            if(!isFind) return false;
        }
        return true;
    }
}poly;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        poly.in(n);
        poly.isCanHull();
        if(poly.isUnique()) puts("YES");
        else puts("NO");
    }
    return 0;
}