1719 測資加強 已 rejudge
1178 . Convex Hull
Description
給定平面上N個點，請計算出凸包上的頂點數。所謂的凸包，就是指一個包含所有點的最小凸多邊形。
所謂凸包上的頂點，指的是轉折處(邊上的點不算)。
Input Format
第一列有一個正整數N (1<=N<=100,000)
第2～N+1列開始每列有兩個整數代表一個點的座標位置(X,Y)。
所有數字都在int範圍內。
Output Format
請輸出凸包上的頂點數。
Sample Input 1
5
0 0
0 2
2 0
1 1
2 2
0 0
0 2
2 0
1 1
2 2
Sample Output 1
4
Hints
※在額外的測試中：
總共至少有30%的測試資料 N<=100。
總共至少有60%的測試資料 N<=1,000。
Problem Source
原TIOJ1178 / TIOJ Contest #1020。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |