P3217 [HNOI2011] Counting Rectangles

A certain singer is planning a world tour. He represents each city he likes as a point on the plane and plans to select $4$ cities as the tour stops. To be unique, he requires that there exists a rectangle such that the selected $4$ points are exactly the $4$ vertices of this rectangle, and he wants the area of this rectangle to be as large as possible. This worries his agent, so he asks fans worldwide for solutions. Of course, you will not miss this opportunity.

The first line contains a positive integer $N$, the number of points on the plane (i.e., the number of cities the singer likes). The next $N$ lines each contain two integers $X_i$ and $Y_i$, separated by a space, representing the coordinates of a city.

Output a single non-negative integer, the maximum area of such a rectangle.

- 20% of the testdata satisfies $N \leq 500$. - 100% of the testdata satisfies $N \leq 1500$, $-10^8 \leq X_i, Y_i \leq 10^8$. - The input guarantees that an answer exists. Translated by ChatGPT 5