TopCoder

User's AC Ratio

44.4% (4/9)

Submission's AC Ratio

11.9% (8/67)

Tags

Description

妁艷倆走到了控制室門口, 這是一個鐵製的大門, 給人不少即將打boss的氣氛.

"裡面可能很危險, 在這裡等著, 我一定會回來的!", 妁艷對著楓音說.

打開了大門, 妁艷首先衝進裡面.

毫無意外地, 大門在妁艷進去之後自己關了起來.

為什麼說了那句話, 妁艷自己也不太清楚. 只是現在真的只剩下一個人了!

房間深處冒出了火光, 遠處出現了一支人影.

只見人影越走越近, 人影也越來越大.

"這根本不是人吧!!! 這是鋼彈啊!?", 妁艷發出悲鳴.

"呵呵! 葛格, 我等你很久了! 快來吧~快來吧~ 我站在這邊快忍不住了", 遠處的機器人駕駛說.

沒錯! 現在要和機器人戰鬥了! 接受天命的戰士呀!

魔力經過剛才的補充, 處於巔峰狀態, 隨時可能爆發(註).

妁艷決定用剛才學會的魔法戰鬥.

使用魔法時要畫一個魔法陣, 魔法陣是三角形.

控制室的內部是一個凸N邊形, 妁艷要在控制室中選3個點畫出三角的魔法陣.

魔法的威力取決於魔法陣的面積, 但不必擔心消耗的MP.

Input Format

第一行有一個數字N(1≤N≤100,000)意義如上文所述.

第二行開始, 第i+1行有兩個數字xi, yi (|xi|, |yi| ≤ 2,000,000,000), 為順時針方向, 每個頂點的平面坐標.

Output Format

輸出唯一的數字, 代表符合上述條件的最大三角形面積的兩倍.

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

1

Hints

頂點為整數點的多邊形, 其面積的兩倍必為整數.

註: 魔力爆發的時候畫面會閃幾下白光, 這是魔力轉化為光能的正常物理現象, 請見[Feynman and Hawking 1989].

Problem Source

原TIOJ1765 / problem setter: willyliu
2021/4/20 加強測資 rejudge

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16
8 7 20
9 8 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 1000 65536 65536 8
8 1000 65536 65536 9