357 . 最小凸多邊形
TopCoder
Description
在計算幾何中，多邊形是十分常出現在題目中的元素，舉凡描述物體、空間等。而要描述多邊形，最簡單容易的就是順時針（或逆時針）描述該多邊形的所有端點，便可清楚且唯一的表示某個多邊形。
而如果一個多邊形的所有內角皆不超過 $180^{\circ}$ ，則稱爲凸多邊形。而凸多邊形也滿足，任意兩個頂點相連的線段，必定落在該凸多邊形內部。
好奇的你，想知道給定二維平面上 $N$ 個點，能包住所有 $N$ 個點的凸多邊形中，面積最小的凸多邊形有多小。
特別的是，如果所有的點可以被一條線段蓋住，則我們可以把該線段視爲一條退化的凸多邊形，此時面積定義爲零。
Input Format
第一行包含一個正整數 $T$，代表總共有 $T$ 筆測資。
對於每筆測資，第一行包含一個正整數 $N$ ，代表給定二維平面上 $N$ 個點。
接下來 $N$ 行，每行包含兩個整數 $x_i,y_i$，表示第 $i$ 個點的 $x$ 座標以及 $y$ 座標。
- $3 \le N \le 10^ 5$
- $\sum N \le 10^ 6$ ($T$ 筆測資中的 $N$ 加起來不會超過 $10^ 6$)
- $0 \le |x_i|,|y_i| \le 10^ 9$ ，(座標範圍的絕對值不會超過 $10^ 9$)
Output Format
輸出可包住所有點且面積最小的凸多邊形的面積，$\textbf{答案恰輸出至小數點後第一位}$。
Sample Input 1
3
3
0 0
1 1
2 2
3
0 0
1 0
0 1
4
0 0
1 1
0 1
1 0
3
0 0
1 1
2 2
3
0 0
1 0
0 1
4
0 0
1 1
0 1
1 0
Sample Output 1
0.0
0.5
1.0
0.5
1.0
Hints
Problem Source
NEOJ Problem 402
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | 100 |