Grandpa‘s Estate POJ - 1228（稳定凸包--德黑兰赛区）

迷南。 2021-07-17 00:36 271阅读 0赞

## **Grandpa’s Estate 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**

**思路**  
稳定凸包：一个凸包上每一条边都有至少三个点，这样改凸包不能由另一个凸包减去一个点得来，也即该凸包不能加一个点得到一个更大的凸包。

如下一个不稳定凸包

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70_pic_center]  
所以我们只需判断题目所给的点构成的凸包是不是一个稳定凸包即可，即判断每条线是不是都至少有三个点。细节见代码。

AC code

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<math.h>
    #include<stdio.h>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    
    const int maxn = 2e3 + 5;
    const double pi = acos(-1.0);
    const double eps = 1e-6;
    struct Point { 
        double x, y;
        Point(double x = 0, double y = 0) :x(x), y(y) { }
    };
    typedef Point Vector;
    Point lst[maxn];
    int stk[maxn], top;
    Vector operator - (Point A, Point B) { 
        return Vector(A.x - B.x, A.y - B.y);
    }
    int sgn(double x) { 
        if (fabs(x) < eps)
            return 0;
        if (x < 0)
            return -1;
        return 1;
    }
    bool operator == (const Point& a, const Point& b) { 
        if (sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0)
            return true;
        return false;
    }
    double Cross(Vector v0, Vector v1) { 
        return v0.x * v1.y - v1.x * v0.y;
    }
    double Dis(Point p1, Point p2) { 
        return sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
    }
    bool cmp(Point p1, Point p2) {  //极角排序函数 ，角度相同则距离小的在前面
        int tmp = sgn(Cross(p1 - lst[0], p2 - lst[0]));
        if (tmp > 0)
            return true;
        if (tmp == 0 && Dis(lst[0], p1) < Dis(lst[0], p2))
            return true;
        return false;
    }
    
    //kfj
    typedef Point Vector;
    bool operator < (const Point& a, const Point& b) { 
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
    
    double Dot(Vector A, Vector B) { 
        return A.x * B.x + A.y * B.y;
    }
    double Length(Vector A) { 
        return sqrt(Dot(A, A));
    }
    
    int dcmp(double x) { 
        if (fabs(x) < eps)
            return 0;
        if (x < 0)
            return -1;
        return 1;
    }
    
    //点的编号0 ~ n - 1
    //返回凸包结果stk[0 ~ top - 1]为凸包的编号
    void Graham(int n) { 
        int k = 0;
        Point p0;
        p0.x = lst[0].x;
        p0.y = lst[0].y;
        for (int i = 1; i < n; ++i) { 
            if ((p0.y > lst[i].y) || ((p0.y == lst[i].y) && (p0.x > lst[i].x))) { 
                p0.x = lst[i].x;
                p0.y = lst[i].y;
                k = i;
            }
        }
        lst[k] = lst[0];
        lst[0] = p0;
        sort(lst + 1, lst + n, cmp);
        if (n == 1) { 
            top = 1;
            stk[0] = 0;
            return;
        }
        if (n == 2) { 
            top = 2;
            stk[0] = 0;
            stk[1] = 1;
            return;
        }
        stk[0] = 0;
        stk[1] = 1;
        top = 2;
        for (int i = 2; i < n; ++i) { 
            while (top > 1 && Cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) < 0)
                --top;
            stk[top] = i;
            ++top;
        }
        return;
    }
    
    int main()
    { 
        FAST;
        int t;cin >> t;
        while (t--)
        { 
            int n;cin >> n;
            int x, y;
            for (int i = 0;i < n;i++)
            { 
                cin >> x >> y;
                lst[i].x = x, lst[i].y = y;
            }
    if(n<6){ cout<<"NO"<<endl;continue;}
            Graham(n);int ans = 1;Vector a = lst[stk[0]], b = lst[stk[1]];
            int i = 1;
            while (1)
            { 
                Vector c = lst[stk[++i]];
                int f = 0;
                while (dcmp(Cross(a - b, a - c)) == 0)//当Cross==0时a b c共线，一条线上至少三点。
                                                      //a b为凸包新的一条边的前两个点c为所看第三点是否共线
                                                      //当三点不共线时此时c已经移动到新的一条边的第二个点，枚举完所有边
                { 
                    f = 1;
                    c = lst[stk[++i]];
                }
                a = lst[stk[i - 1]], b = c;
                if (f == 0)
                { 
                    ans = 0;break;
                }
                if (i >= top)break;
            }
            if (ans)cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70_pic_center]: /images/20210716/84dfc36bc3d649dbb7216fb4c2f838a8.png