The Oldest Ruins

Long ago there was a settlement here where many people lived. They built structures of all shapes and sizes. Those structures are long gone, and the only clues to where they once stood are the surviving records and the pillars unearthed at the site.

The records describe a temple. Seen from above, the temple was a perfect square with a pillar at each of its four corners. Which way the temple faced is unknown, and whether there were pillars along its edges or inside it is also unknown. The archaeologists reasoned that, among the pillars found at the site, the four that form a square of the largest area must mark the temple.

Given the coordinates of the pillars, write a program that finds the square of the largest area that can be formed by four pillars and outputs that area. Note that the sides of the square are not necessarily parallel to the coordinate axes.

The first line contains $n$, the number of pillars found at the site.

Each of the next $n$ lines (from line $2$ through line $n+1$) contains the $x$-coordinate and $y$-coordinate of one pillar, separated by a space.

No pillar appears more than once.

$n$ is an integer with $1 \le n \le 3000$, and each pillar's $x$- and $y$-coordinates are integers between $0$ and $5000$ inclusive.

Output a single integer. If a square formed by four pillars exists, output the area of the largest such square; otherwise output $0$.

In the example shown below there are 10 pillars. The four at $(4, 2), (5, 2), (5, 3), (4, 3)$ form one square, and the four at $(1, 1), (4, 0), (5, 3), (2, 4)$ form another. The larger square is the latter, whose area is $10$.