Description

A long time ago, there was a temple. Viewed from above, the temple was a square, built by circular columns erected at its four corners. Now all the columns have fallen, leaving circular marks on the ground. However, there are many such marks on the ground, and experts say the temple must correspond to the largest one.

Write a program that, given the coordinates of the columns, finds the largest square formed by $4$ columns (i.e., four points as its vertices), which indicates the temple’s location, and compute its maximum area. Note that the sides of the square are not necessarily parallel to the coordinate axes.

For example, in the figure there are $10$ columns. Among them, $(4,2),\allowbreak(5,2),\allowbreak(5,3),\allowbreak(4,3)$ can form a square, and $(1,1),\allowbreak(4,0),\allowbreak(5,3),\allowbreak(2,4)$ can as well. The latter is the largest among them, with area $10$.

Input Format

The first line contains an integer $N$ ($1 \leq N \leq 3000$), the number of columns.

The next $N$ lines each contain two space-separated integers, giving the coordinates of a column (each coordinate is in the range $0$ to $5000$). All column positions are pairwise distinct.

Output Format

If at least one square exists, output the maximum area; otherwise, output $0$.

10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2

10

Hint

Constraints

• $30\%$: $1 \leq N \leq 100$.
• $60\%$: $1 \leq N \leq 500$.
• $100\%$: $1 \leq N \leq 3000$.

Translated by ChatGPT 5