主題

ZeroJudge - b596: Less is better 解題心得

Not In My Back Yard | 2020-12-16 00:00:07 | 巴幣 0 | 人氣 82

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列給定一正整數 n (1 ≦ n ≦ 1000,當 n = 0 時代表輸入結束),代表有 n 個座標平面上的點。接著的一列給定 2n 個整數,每兩個一組,每一組代表著一個點在座標平面上的 x 、 y 座標(-10000 ≦ x 、 y ≦ 10000)。

請找到可以包覆住這 n 個點的最小凸多邊形,即凸包(Convex Hull),其頂點之個數為多少?



範例輸入:
5
0 0 2 0 0 2 2 2 1 1
6
0 0 2 1 0 2 2 4 0 7 2 8
0


範例輸出:
4
4


解題思維:
凸包的求法參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作