#XXSY26JAT2. 红军的三角防线
红军的三角防线
红军的三角防线
题目描述
在红军长征途中,为了保障部队的安全和通讯畅通,指挥部决定在广袤的草地上建立一个临时的三角形防线。侦察兵已经在地图上标出了 N 个可以作为通讯哨所的候选坐标点,需要从中选取 3 个点作为三角形的顶点。为了方便快速定向通讯,这个三角形防线必须满足:有一条边与 x 轴(纬线)平行,且有另一条边与 y 轴(经线)平行。
请你帮红军指挥员计算出,在所有合法的部署方案中,三角形防线的最大面积是多少?(保证数据中至少存在一个合法的方案)。
输入格式
第一行包含一个整数 N(3 <= N <= 100)。
接下来 N 行,每行包含两个整数和,均在 -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