TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

97.7% (42/43)

Submission's AC Ratio

39.4% (74/188)

Tags

Description

給定平面上N個點,請計算出凸包上的頂點數。所謂的凸包,就是指一個包含所有點的最小凸多邊形。
所謂凸包上的頂點,指的是轉折處(邊上的點不算)。

Input Format

第一列有一個正整數N (1<=N<=100,000)
第2~N+1列開始每列有兩個整數代表一個點的座標位置(X,Y)。
所有數字都在int範圍內。

Output Format

請輸出凸包上的頂點數。

Sample Input

5
0 0
0 2
2 0
1 1
2 2

Sample Output

4

Hints

※在額外的測試中:
  總共至少有30%的測試資料 N<=100。
  總共至少有60%的測試資料 N<=1,000。

Problem Source

原TIOJ1178 / TIOJ Contest #1020。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536