h225.
Convex Hull(模板題)
Content
凸包問題是個經典問題，定義是包覆這群點的所有外殼當中，面積最小的一個外殼，至於凸代表它是凸多邊形，它常被應用在圖像處理及地理信息系統等方面。
阿祁今天給你一個位於二維坐標系的n個點，請找出所有凸包上的點。
Input
首先第一行有正整數n代表點的數量，再來有n行每個兩個數x、y代表點座標。
你可以視為所有點都是唯一，且凸包面積>0。
3≤n≤2e5
−1e9≤x,y≤1e9
Output
首先輸出正整數k，代表凸包有k個點，接著輸出k行他們的x、y座標，x、y中間以空格隔開，為了方便請先把x座標從小到大排序再輸出(如果x座標一樣大則照y座標)
Sample Input
#1
6 2 1 2 5 3 3 4 3 4 4 6 3
Sample Output
#1
4 2 1 2 5 4 4 6 3
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint ：
Tags:
出處:
CSES2195
[管理者：
linlincaleb@
...
(臨末之頌)
]
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||