#5132. 平面世界III

平面世界III

题目描述

小胡在平面世界探索时遇到了难题。

他打算在平面世界修建一个三角形的基地,他散布出去了 NN 个自动探索机器人,它们分布在这个平面世界不同的坐标点上。他可以选择其中的三个点来构成这个三角形基地的三个顶点,要求这个三角形基地的两条边分别与坐标系的 xx 轴和 yy 轴平行。

小胡希望基地的面积尽可能的大,请问最大的面积是多少?保证至少存在一个合法的三角形可供选择。

输入格式

一个整数 NN

接下来有 NN 行,每行包含两个整数,表示机器人所在点的 xxyy 坐标。

输出格式

由于面积不一定为整数,所以输出这个最大基地面积的两倍即可。

样例

4
0 0
0 1
1 0
1 2
2
4
-1 0
0 0
1 0
0 2
2

提示

样例 1 解释:选择 (1,2)(1,2)(1,0)(1,0)(0,0)(0,0) 这三个点构成的三角形是最大的合法三角形,答案是 2×1=22 \times 1 = 2

数据范围

  • 1N1001 \le N \le 100
  • 1000x,y1000-1000 \le x, y \le 1000