93. 最大面積三角形

最大面積三角形

題目敘述

平面上給定 $n$ 個整數點，求最大面積三角形的兩倍面積，若有三點共線該面積為 $0$

輸入

每筆測資只有一個輸入 第一行有一個數字 $n$ 接下來有 $n$ 行，每行有兩個數字代表一個平面點 $(x_i, y_i)$

$$ 3 \leq n \leq 2000 $$

$$ |x_i|, |y_i| \leq 10^6 $$

輸出

輸出兩倍面積當作答案，根據鞋帶公式（Shoelace formula）可以知道這一定是整數

Sample Input

3
0 0 
1 1
2 2

Sample Output

0

Sample Input

3
0 0 
1 1
1 0

Sample Output

1

Note

20% Partial credit for $N\leq 100$.

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 9