User's AC Ratio

96.3% (26/27)

Submission's AC Ratio

38.2% (63/165)

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) Output Limit (KiB)
0 5000 524288 262144
1 5000 524288 262144
2 5000 524288 262144
3 5000 524288 262144
4 5000 524288 262144
5 5000 524288 262144
6 5000 524288 262144
7 5000 524288 262144
8 5000 524288 262144
9 5000 524288 262144
10 5000 524288 262144
11 5000 524288 262144
12 5000 524288 262144
13 5000 524288 262144
14 5000 524288 262144
15 5000 524288 262144
16 5000 524288 262144