1280 . 領土 (Territory)
TopCoder
Description
領土為一個國家最重要的資源。因此一個國家經常會在國土內的各個地方設置安全哨，以確保領土內的治安及安全。為了簡易丈量領土大小及領域邊界，在群雄割據的古代諸侯國之間訂定了簡易的領土界定標準。此標準的規定為將國家中的所有安全哨彼此兩兩以直線相連，並從這些直線所圍出的面積中找出最大的區域來定為該國的領土，而在領土邊界上的點稱為邊界安全哨。例如，下面圖中某一諸侯國共有五個安全哨，其中由位於 (10, 10)、(20, 30)、(40, 30) 及 (40, 10) 等四個點為邊界安全哨，其所圍出來的面積為最大區域，也就是該國的領土，因此該國的領土大小為 500 平方公里。給定某國所設定的安全哨，請寫一個程式來計算該國領土面積。
Input Format
輸入檔第一行有一個整數 n，代表該國家有 n 個安全哨。接下來有 n 行，每行有兩個整數 x 及 y，以一個空白隔開，用以代表一個安全哨在座標軸上的位置，其中整數 x 代表該安全哨在橫軸上的座標值，整數 y 代表該安全哨在縱軸上的座標。
Output Format
輸出該國安全哨所能圍出的最大領土，輸出資料四捨五入取到整數位。
Sample Input 1
5
10 10
20 20
20 30
40 10
40 30
10 10
20 20
20 30
40 10
40 30
Sample Output 1
500
Hints
三角形面積公式：假設三角形的三個邊長為 $a$、$b$、$c$ 。$s = \frac{a+b+c}{2}$，則三角形的面積 = $\frac{1}{2}\sqrt{s(s-a)(s-b)(s-c)}$。
Problem Source
臺北市103 學年度高級中學資訊學科能力競賽程式設計試題第二題
Set by Yihda Yol
若測資有誤請儘快聯絡管管(?
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 0≤ n ≤10，且所有安全哨皆為邊界安全哨，並且所圍出來的最大領土必為長方形 | 10 |
| 2 | 0~6 | 0≤ n ≤10，且所有安全哨皆為邊界安全哨 | 20 |
| 3 | 0~10 | 0≤ n ≤100，並非所有安全哨皆為邊界安全哨 | 30 |
| 4 | 0~16 | 0≤ n ≤10000，並非所有安全哨皆為邊界安全哨 | 40 |