網際網路程式設計全國大賽

決賽題目

所謂「凸多邊形」(convex polygon) 就是具有下列特性的多邊形：任何在多邊形之內的兩個點所連成的線段一定落於此多邊形之內。試寫一個程式，已知在平面上的一組點中 (共 N 個點)，找出一個點數最少的點組，形成一個凸多邊形，並使所有 N 個點都在這個凸多邊形之中。
下圖是一個例子：

輸入檔說明

輸入檔中可以包含多個測試資料。每個測試資料的第一行是點的個數（N <= 20000），接下來則是點的座標資料。每一行有兩個數字表示一個點的 x、y 座標，兩個數字均為整數，且以一個以上的空格分開。當點的個數為 0 時，則測試資料結束。輸入檔中不會有兩個以上的相同之點。

輸出檔說明

輸出檔中輸出每個測試資料中，凸多邊形的邊數。即，最少需要幾個頂點，才能以凸多邊形將所有的點包住。注意：凸多邊形上不可以有三點共線的情形，如圖中之 M 將被忽略。

範例

5
0 0
0 10
10 10
10 0
5 5
4
0 0
1 1
2 2
2 0
0

4
3

Update

輸出結果可能是一條線段的二個端點。
例如輸入資料 (0,0), (1,1), (2,2) 的答案為 2。