題目連結:
題目大意:
輸入第一列給定一正整數 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
解題思維:
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。