POJ1228(穩定凸包問題)

題意：輸入一個凸包上的點（沒有凸包內部的點，要麼是凸包頂點，要麼是凸包邊上的點），判斷這個凸包是否穩定。所謂穩

定就是判斷能不能在原有凸包上加點，得到一個更大的凸包，並且這個凸包包含原有凸包上的所有點。

分析：容易知道，當一個凸包穩定時，凸包的每條邊上都要有至少三個點，若只有兩個點，則可以增加一個點，得到更大的凸

包。這樣我們可以求出凸包，在求凸包時把共線的點也加進來，這樣我們就判斷是否有連續的三點共線即可，具體參見代碼。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

const int N = 40005;

typedef double DIY;

struct Point
{
    DIY x,y;
};

Point p[N];
Point stack[N];
Point MinA;

int top;

DIY dist(Point A,Point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

DIY cross(Point A,Point B,Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

bool cmp(Point a,Point b)
{
    DIY k=cross(MinA,a,b);
    if(k>0) return 1;
    if(k<0) return 0;
    return dist(MinA,a)<dist(MinA,b);  //這裡共線的點按距離從小到大排序
}

void Graham(int n)
{
    int i;
    for(i=1; i<n; i++)
        if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
            swap(p[i],p[0]);
    MinA=p[0];
    sort(p+1,p+n,cmp);
    stack[0]=p[0];
    stack[1]=p[1];
    top=1;
    for(i=2; i<n; i++)
    {
        //注意這裡我們把共線的點也壓入凸包裡
        while(cross(stack[top-1],stack[top],p[i])<0&&top>=1) --top;
        stack[++top]=p[i];
    }
}

bool Judge()
{
    for(int i=1;i<top;i++)
    {
        //判斷凸包的一條邊上是否至少有3點
        if((cross(stack[i-1],stack[i+1],stack[i]))!=0&&(cross(stack[i],stack[i+2],stack[i+1]))!=0)
            return false;
    }
    return true;
}

int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        if(n<6)
        {
            puts("NO");
            continue;
        }
        Graham(n);
        cout<<endl;
        for(i=0;i<n;i++)
          cout<<p[i].x<<" "<<p[i].y<<endl;
        cout<<endl;
        for(i=0;i<=top;i++)
          cout<<stack[i].x<<" "<<stack[i].y<<endl;
        if(Judge()) puts("YES");
        else        puts("NO");
    }
    return 0;
}