Triangles

题目描述

Farmer John 想为他的奶牛建造一个三角形牧场。 农场的二维地图上有 $N$ 根栅栏柱（$3\le N\le 100$），位于互不相同的点 $(X_1, Y_1) \ldots (X_N, Y_N)$。他可以从中选择三根作为三角形牧场的顶点，要求该三角形的一条边平行于 $x$ 轴，另一条边平行于 $y$ 轴。 Farmer John 能构造出的牧场最大面积是多少？保证至少存在一个合法的三角形牧场。

输入格式

输入格式（文件 triangles.in）： 输入第一行包含整数 $N$。接下来的 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，每个都在范围 $-10^4 \ldots 10^4$（含端点）内，描述一根栅栏柱的位置。

输出格式

输出格式（文件 triangles.out）： 由于面积本身不一定是整数，请输出由栅栏柱构成的合法三角形的最大面积的 两倍。

4
0 0
0 1
1 0
1 2

2

提示

位于 $(0,0)$、$(1,0)$ 和 $(1,2)$ 的柱子构成一个面积为 $1$ 的三角形。因此答案是 $2\cdot 1=2$。只有另一个三角形，面积为 $0.5$。 题目来源：Travis Hance

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze