P9949 [USACO20FEB] Triangles B

Farmer John wants to build a triangular pasture for his cows. There are $N$ ($3 \le N \le 100$) fence posts located at distinct points $(X_1, Y_1) \ldots (X_N, Y_N)$ on the 2D plane of the farm. He can choose three of these points to form a triangular pasture, as long as one side of the triangle is parallel to the $x$-axis and another side is parallel to the $y$-axis. What is the maximum area of a pasture Farmer John can enclose? It is guaranteed that there is at least one valid triangular pasture.

The first line contains an integer $N$. The next $N$ lines each contain two integers $X_i$ and $Y_i$, both in the range $-10^4 \ldots 10^4$, describing the position of a fence post.

Since the area may not be an integer, output **twice** the maximum area of a valid triangle that can be formed by the fence posts.

### Sample Explanation 1 The posts at $(0,0)$, $(1,0)$, and $(1,2)$ form a triangle with area $1$. Therefore, the answer is $2 \cdot 1 = 2$. There is only one other triangle, with area $0.5$. Translated by ChatGPT 5