93. 最大面積三角形

0 Judge

Code: 0


最大面積三角形

題目敘述

平面上給定 $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