TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

97.9% (46/47)

Submission's AC Ratio

32.4% (101/312)

Description

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

Input Format

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

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1 2 3 4
1 5000 524288 262144 1 2 3 4
2 5000 524288 262144 1 2 3 4
3 5000 524288 262144 2 3 4
4 5000 524288 262144 2 3 4
5 5000 524288 262144 2 3 4
6 5000 524288 262144 2 3 4
7 5000 524288 262144 3 4
8 5000 524288 262144 3 4
9 5000 524288 262144 3 4
10 5000 524288 262144 3 4
11 5000 524288 262144 4
12 5000 524288 262144 4
13 5000 524288 262144 4
14 5000 524288 262144 4
15 5000 524288 262144 4
16 5000 524288 262144 4