判斷穩定凸包，求凸包代碼（poj1228）

#include 
#include 
#include 
#include 
using namespace std;

const double eps = 1e-8;
struct Point {
    double x, y;
} pnt[1005];

int stk[1005], top;

int dblcmp(double k) {
    if (fabs(k) < eps) return 0;
    return k > 0 ? 1 : -1;
}

double multi(Point p0, Point p1, Point p2) {
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}

double getDis(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool cmp(const Point& a, const Point& b) {
    int d = dblcmp(multi(pnt[0], a, b));
    if (!d) return getDis(pnt[0], a) < getDis(pnt[0], b);
    return d > 0;
}

int main()
{
    int t, n, i, k;
    double tx, ty;

    scanf ("%d", &t);
    while (t--) {
        scanf ("%d", &n);
        //先要找到最左下角的點
        scanf ("%lf%lf", &pnt[0].x, &pnt[0].y);
        tx = pnt[0].x; ty = pnt[0].y;
        k = 0;
        for (i = 1; i < n; i++) {
            scanf ("%lf%lf", &pnt[i].x, &pnt[i].y);
            int d = dblcmp(ty-pnt[i].y);
            if (d > 0) {
                k = i;
                tx = pnt[i].x;
                ty = pnt[i].y;
            }
            else if (!d && dblcmp(tx-pnt[i].x) > 0) {
                k = i;
                tx = pnt[i].x;
            }
        }
        pnt[k].x = pnt[0].x;
        pnt[k].y = pnt[0].y;
        pnt[0].x = tx;
        pnt[0].y = ty;
        //極角排序
        sort(pnt+1, pnt+n, cmp);
        //以下是求凸包的代碼，stk數組中存的是凸包角上的點集
        stk[0] = 0;
        stk[1] = 1;
        top = 1;
        for (i = 2; i < n; i++) {
            while (top >= 1 && dblcmp(multi(pnt[stk[top-1]], pnt[i], pnt[stk[top]])) >= 0) top--;
            stk[++top] = i;
        }
        
        if (top <= 1) {
            printf ("NO\n");
            continue;
        }
        bool flag = false;
        for (i = 1; i <= top; i++)
            if (stk[i]-stk[i-1] == 1) {
                flag = true;
                break;
            }
        for (i = 1; i < n-1; i++)
            if (!dblcmp(multi(pnt[0], pnt[i], pnt[n-1]))) break;//說明首尾連線之間至少有1個點
        if (!flag && i < n-1) printf ("YES\n");
        else printf ("NO\n");
    }
    return 0;
}

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

得到一個更大的凸包，並且這個凸包包含原有凸包上的所有點。

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

思路：直接求凸包，得到原來凸包頂點，去掉凸包邊上的點，由於求凸包的過程中要對點集pnt[]極角排序，最後只需判斷求得的凸包上的點在排序後的pnt[]中是否相鄰，

凸包中第一個和最後一個點還需特別判斷一下它們之間是否有點，若求得凸包中的點個數為2，則輸入的所有點都在一條線上，這時需輸出NO