题目描述

书库前庭的地面可以看作一个笛卡尔坐标系，上面坐落了 $n$ 个「星界碑针」，编号 $1\sim n$，其中 $n$ 为偶数。第 $i$ 个「星界碑针」的坐标为 $(x_i, y_i)$。保证所有「星界碑针」的坐标两两不同，且不存在三点共线。

芙莉莲已经破解了「星界碑针」的明暗变化，具体的，对于任意角度 $\theta\in[0,\pi)$，定义方向向量 $u_\theta=(\cos\theta,\sin\theta)$，则对每个「星界碑针」 $P_i=(x_i,y_i)$，定义它在该方向上的投影值为 $p_i(\theta)=x_i\cos\theta+y_i\sin\theta$，如果在该角度下所有 $p_i(\theta)$ 两两不同，则称该角度为「星界角」。

对于一个「星界角」 $\theta$，将所有「星界碑针」的坐标按投影后的结果 $p_i(\theta)$ 从小到大排序，则前 $\frac{n}{2}$ 个「星界碑针」将会亮起，记这些「星界碑针」的凸包面积为 $A_\theta$。

芙莉莲需要知道最大的「星界碑针」凸包面积的两倍，也就是

由于坐标均为整数，因此可以保证该答案为整数。

输入格式

输入第一行包含整数 $n(2\leq n\leq 2\times 10^3)$，代表「星界碑针」的数量。

第 $i$ 行包含两个整数 $x_i, y_i(-10^6\leq x_i, y_i\leq 10^6)$，代表第 $i$ 个「星界碑针」的坐标。

输出格式

输出一个整数，代表最大的「星界碑针」凸包面积的两倍

输入输出样例 #1

输入 #1

6
9 -1
-11 -10
-2 10
-6 -7
-13 -10
-6 -9

输出 #1

253

输入输出样例 #2

输入 #2

6
0 0
4 0
6 2
4 4
0 4
-2 2

输出 #2

8