#M1006. 三角形面积

三角形面积

题目描述

小 Z 学了平面直角坐标系,突然想在平面直角坐标系中建立一些三角形。

具体来说,在二维平面上不同的NN 个点 (X1,Y1)(XN,YN)(X_1,Y_1)…(X_N,Y_N)。他可以选择其中三个点组成三角形,只要三角形有一条边与 xx 轴平行,且有另一条边与 yy 轴平行。

小 Z 能够组成的三角形的最大面积是多少?保证存在至少一个合法的三角形。

输入格式

输入的第一行包含整数 NN。以下 NN 行每行包含两个整数 XiX_iYiY_i,描述点的位置。

输出格式

由于面积不一定为整数,输出可以组成的合法三角形的最大面积的两倍。

样例 #1

样例输入 #1

4
0 0
0 1
1 0
1 2

样例输出 #1

2

提示

【样例解释】

位于点 (0,0)(0,0)(1,0)(1,0)(1,2)(1,2) 的点组成了一个面积为 1 的三角形。所以,答案为 2×1=22\times 1=2。只有一个其他的三角形,面积为 0.50.5

【数据范围】

3n1003\le n\le 10010000Xi,Yi10000-10000 \le X_i,Y_i \le 10000