POJ 1228 —— “穩定”凸包

POJ 1228?Grandpa's Estate

這是個好題目，同時也是個不和諧的題目（不和諧原因是題目出的存在漏洞，數據弱，而且有些條件沒給清楚，為了一個SB錯誤無限WA之后，終于AC）

?

題意就廢了我好長時間，唉……英語不好的鴨梨大……

大意就是爺爺留了塊土地給我，然而這塊土地是以一些釘子來界定的，題目要做的就是給你一堆釘子的坐標（也就是凸包上部分的點），然后問你能不能唯一確定這塊土地。

問了下度娘，這個問題叫做“穩定”凸包問題，那么首先就要了解下“穩定”凸包的性質：（在此感謝XDruid博主）

比方說有4個點：

這4個點可以圍成一個凸包，但是原始的凸包可能并不是這個樣子的

例如可能是這個樣子：

這樣我們則稱這4個點確定的凸包是”不穩定“的！

那么怎么樣才叫穩定呢？

是這個樣子：想一想，若像剛才一樣，在直線外面加一個點，那么線上的點必定不會屬于凸包，要刪掉，是吧？

如此以來，問題就很明確了，算法也隨之而來了：

我們已經知道了怎么求凸包了（前提），這樣一來，只要判斷是否有3點或N>=3點共線就可以了~~

表示用的是Graham的變種Andrew……感覺真的很好用：

下面貼代碼：

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;const double EPS = 1e-6;struct point{double x , y;
} p[1010] , chn[1010];bool cmp (point a , point b)
{return (a.y < b.y || (a.y == b.y && a.x < b.x));
}double xmult(point p1 , point p2 , point p3)
{return ((p1.x - p3.x) * (p2.y - p3.y) - (p1.y - p3.y) * (p2.x - p3.x));
}int andrew(int n)
{int len , top = 1;chn[0] = p[0];chn[1] = p[1];for (int i = 2 ; i < n ; i ++){while (top && xmult(p[i] , chn[top] , chn[top - 1]) > EPS) top --;chn[++ top] = p[i];}len = top;chn[++ top] = p[n - 2];for (int i = n - 3 ; i >= 0 ; i --){while (top != len && xmult(p[i] , chn[top] , chn[top - 1]) > EPS) top --;chn[++ top] = p[i];}return top;
}bool judge(int n)  //解釋請看下面
{for (int i = 1 ; i < n ; i ++){if ((xmult(chn[i - 1] , chn[i] , chn[i + 1]) != 0) && (xmult(chn[i] , chn[i + 1] , chn[i + 2]) != 0))return false;}return true;
}int main()
{int T , n;scanf("%d" , &T);while (T --){scanf("%d" , &n);for (int i = 0 ; i < n ; i ++) scanf("%lf%lf" , &p[i].x , &p[i].y);if (n < 6) printf("NO\n");else{sort(p , p + n , cmp);int top = andrew(n);if (judge(top)) printf("YES\n");else printf("NO\n");}}return 0;
}

寫了這個題后，對凸包的理解真是加深了。

同時，在被WA了N此后（主要是因為讀入數據要用double。但是題目上說是整點啊！不明白，如果沒看到別人的解題報告，估計要一直WA下去）

昨晚在無限WA后找了XxX師兄，開始以為思路錯了，經過他的問答，對這個題目的理解更是加深了！

下面說下代碼中【judge】函數的判斷原因：

理論支持：叉積 = 0 說明共線！

我們用Andrew算法求出凸包后（棧內不刪去共線的點）這些點已經是按一定順序排好了的~

然后之需要對棧內的點進行叉積判斷就可以了~~ 只有當向左與向中間擴展都不滿足是，才說明當前點不滿足！

所以只要有一個不滿足，則說明全部不滿足了。

?

做了這個題目，我對之前提出的疑問有了答案。哈哈~~