TopCoder

User's AC Ratio

100.0% (23/23)

Submission's AC Ratio

44.4% (52/117)

Description

  領土為一個國家最重要的資源。因此一個國家經常會在國土內的各個地方設置安全哨,以確保領土內的治安及安全。為了簡易丈量領土大小及領域邊界,在群雄割據的古代諸侯國之間訂定了簡易的領土界定標準。此標準的規定為將國家中的所有安全哨彼此兩兩以直線相連,並從這些直線所圍出的面積中找出最大的區域來定為該國的領土,而在領土邊界上的點稱為邊界安全哨。例如,下面圖中某一諸侯國共有五個安全哨,其中由位於 (10, 10)、(20, 30)、(40, 30) 及 (40, 10) 等四個點為邊界安全哨,其所圍出來的面積為最大區域,也就是該國的領土,因此該國的領土大小為 500 平方公里。給定某國所設定的安全哨,請寫一個程式來計算該國領土面積。

Input Format

  輸入檔第一行有一個整數 n,代表該國家有 n 個安全哨。接下來有 n 行,每行有兩個整數 x 及 y,以一個空白隔開,用以代表一個安全哨在座標軸上的位置,其中整數 x 代表該安全哨在橫軸上的座標值,整數 y 代表該安全哨在縱軸上的座標。

本題共有四組測試資料。

第一組測試資料 0≤ n ≤10,且所有安全哨皆為邊界安全哨,並且所圍出來的最大領土必為長方形,共 10 分。
第二組測試資料 0≤ n ≤10,且所有安全哨皆為邊界安全哨,共 20 分。
第三組測試資料 0≤ n ≤100,並非所有安全哨皆為邊界安全哨,共 30 分。
第四組測試資料 0≤ n ≤10000,並非所有安全哨皆為邊界安全哨,共 40 分。

Output Format

輸出該國安全哨所能圍出的最大領土,輸出資料四捨五入取到整數位。

Sample Input

5
10 10
20 20
20 30
40 10
40 30

Sample Output

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

For Testdata: 0 ~ 2, Score: 10
For Testdata: 0 ~ 6, Score: 20
For Testdata: 0 ~ 10, Score: 30
For Testdata: 0 ~ 16, Score: 40
No. Time Limit (ms) Memory Limit (KiB)
0 5000 524288
1 5000 524288
2 5000 524288
3 5000 524288
4 5000 524288
5 5000 524288
6 5000 524288
7 5000 524288
8 5000 524288
9 5000 524288
10 5000 524288
11 5000 524288
12 5000 524288
13 5000 524288
14 5000 524288
15 5000 524288
16 5000 524288