POJ 1228 /// 稳定凸包

题目大意：

t个测试用例

每次给定一个n

接下来给定n个点

判断这n个点组成的多边形是不是一个稳定凸包

稳定凸包就是一条边上有至少三个点 这样但凡多出一个点 都会形成凹多边形

可以看下这个讲解https://www.cnblogs.com/xdruid/archive/2012/06/20/2555536.html

那这道题就是求完凸包后 判断凸包的一条边上是否存在三个以上的点

#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;

const double eps=1e-10;
double add(double a,double b) {
    if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct P {
    double x,y;
    P(){};
    P(double _x,double _y):x(_x),y(_y){};
    P operator - (P p) {
        return P(add(x,-p.x),add(y,-p.y)); }
    P operator + (P p) {
        return P(add(x,p.x),add(y,p.y)); }
    P operator * (double d) {
        return P(x*d,y*d); }
    double dot(P p) {
        return add(x*p.x,y*p.y); }
    double det(P p) {
        return add(x*p.y,-y*p.x); }
}p2[1005], p3[1005];
int n, k;
bool cmp(P a,P b) {
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
void andrew()
{
    sort(p2,p2+n,cmp);
    k=0;
    // 求凸包时 <= 应改成 <，将同一条边上的也加入
    for(int i=0;i<n;i++) {
        while(k>1 && (p3[k-1]-p3[k-2]).det(p2[i]-p3[k-1])<0)
            k--;
        p3[k++]=p2[i];
    }
    for(int i=n-2,t=k;i>=0;i--) {
        while(k>t && (p3[k-1]-p3[k-2]).det(p2[i]-p3[k-1])<0)
            k--;
        p3[k++]=p2[i];
    }
    if(n>1) k--;
}
bool judge()
{
    for(int i=0;i<k;i++) {
        int j=i; // 起点为 j
        while((p3[(j+1)%n]-p3[j]).det(p3[(j+2)%n]-p3[(j+1)%n])==0)
            j++; // 判断点j+1是否在j到j+2的边上
        if(j>i) i=j; // 只要有一点在边上 就满足至少三个 i转到下一条边的起点
        else return 0; // 否则不满三个 返回0
    }
    return 1;
}

int main()
{
    int t; scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p2[i].x,&p2[i].y);

        if(n<6) {
            printf("NO
"); continue;
        } // 稳定的三角形凸包至少6个点
        andrew();
        if(judge()) printf("YES
");
        else printf("NO
");
    }

    return 0;
}