前往
大廳
主題

ZeroJudge - h225: Convex Hull(模板題) 解題心得

Not In My Back Yard | 2022-02-27 00:00:04 | 巴幣 2 | 人氣 223

題目連結:


題目大意:
輸入第一列給定一正整數 n (3 ≦ n ≦ 2 × 10 ^ 5),代表座標平面上有 n 個點。接下來有 n 列輸入,每列給定兩整數 x 、 y(-10 ^ 9 ≦ x 、 y ≦ 10 ^ 9),代表平面上有一個點 (x, y)。

假設所有點相異,且這 n 個點的凸包(Convex Hull,定義見維基)面積 > 0(即沒有退化成線段甚至是一個點)。試問平面上哪些點座落於凸包上?請將所有點先按 x 座標由小到大排序,x 座標值一樣則按 y 座標由小到大排序。將這些點排序後,先輸出點數,再依序輸出這些點的座標,參見範例輸出。



範例輸入:
6
2 1
2 5
3 3
4 3
4 4
6 3


範例輸出:
4
2 1
2 5
4 4
6 3


解題思維:
基本上與這題相同。




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

創作回應

相關創作

更多創作