#XXSY26JAT2. 红军的三角防线

红军的三角防线

红军的三角防线

题目描述

​ 在红军长征途中,为了保障部队的安全和通讯畅通,指挥部决定在广袤的草地上建立一个临时的三角形防线。侦察兵已经在地图上标出了 N 个可以作为通讯哨所的候选坐标点,需要从中选取 3 个点作为三角形的顶点。为了方便快速定向通讯,这个三角形防线必须满足:有一条边与 x 轴(纬线)平行,且有另一条边与 y 轴(经线)平行。

​ 请你帮红军指挥员计算出,在所有合法的部署方案中,三角形防线的最大面积是多少?(保证数据中至少存在一个合法的方案)。

输入格式

第一行包含一个整数 N(3 <= N <= 100)。

接下来 N 行,每行包含两个整数xix_i和yiy_i,均在 -10000 ~ 10000 范围之内,描述候选坐标点。

输出格式

​ 由于面积不一定为整数,输出三角形防线的最大面积的两倍。

输入输出样例

4
0 0
0 1
1 0
1 2
2

6
-7 3
-4 -1
-3 6
2 5
3 1
-4 5
36

说明提示

样例1解释

样例1,位于点 (0,0)、(1,0) 和 (1,2) 的木桩组成了一个面积为 1 的三角形。所以,答案为 2⋅1=2。只有一个其他的三角形,面积为 0.5。

数据规模与约定

3≤N≤100