Problem Description

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.

Input Format

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.

Output Format

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.

4
0 0
0 1
1 0
1 2

2

Hint

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