這天,小明在造圍欄。
他提前在地上 (二維平面) 打好了 n 個洞,這 n 個洞的位置形成了一個凸多邊形。當他準備把固定圍欄的木桿插進去的時候,突然發(fā)現(xiàn)自己少準備了兩根木桿。
如圖,他現(xiàn)在只能在這 n 個洞中選出 n ? 2 個來放置木桿,他想知道用這 n ? 2 個木桿能圍成的凸多邊形的最大的面積是多少。
輸入共 n + 1 行,第一行為一個正整數(shù) n。
后面 n 行,每行兩個整數(shù) xi , yi 表示第 i 個洞的坐標。
保證按照逆時針的順序輸入這 n 個點的坐標。
一行,一個正整數(shù),表示答案。
為了避免小數(shù),請輸出面積的兩倍。
5 0 0 1 0 2 1 0 3 -1 1
6
選擇 (?1, 1) (2, 1) (0, 3) 這三個點構(gòu)成的多邊形面積最大,為 3,所以輸出 6。
對于 100% 的數(shù)據(jù),保證 5 ≤ n ≤ 100;|xi |, |yi | ≤ 106。