Background

The highest-upvoted solution for P1429 Closest Pair of Points on a Plane (Enhanced Version) says:

We fully carry forward human wisdom:
Rotate all points by the same angle around the origin, then sort by the $x$ coordinate.
By mathematical intuition, after a random rotation, the two points in the answer will surely not be too far apart in the array.
So we only take the next $5$ points for each point to compute the answer.
This becomes extremely fast; even for $n = 1000000$ it can pass within 1 second.

Of course, this is wrong.

Problem Description

Given $n$ points $p_1, p_2, \dots, p_n$ in a 2D Euclidean plane, output the squared distance between the closest pair of points.

Input Format

The first line contains a positive integer $n$, the number of points.

The next $n$ lines each contain two integers $x_i, y_i$ separated by spaces, representing $p_i = (x_i, y_i)$.

The input guarantees that no two points have exactly the same coordinates.

Output Format

Output one line containing an integer $D^2$, the square of the distance between the closest pair of points.

Since all input points have integer coordinates, this value must be an integer.

2
-10000000 -10000000
10000000 10000000

800000000000000

5
1 1
1 9
9 1
9 9
0 10

2

Hint

For the second sample, the points $(1, 9)$ and $(0, 10)$ are the closest, with distance $\sqrt 2$, so you should output $2$.

Constraints

For $100\%$ of the testdata, $2 \leq n \leq 4 \times 10^5$, $-10^7 \leq x_i, y_i \leq 10^7$.

The target complexity of this problem is $O(n \log ^2 n)$. The reason for setting the time limit to 350 ms is:

1. A reference implementation of $O(n \log ^2 n)$ will not TLE even when using cin. The fastest standard solution can be $<$ 100 ms.
2. @wlzhouzhuan's program can run exactly $1000n$ checks within 350 ms.
3. There are 150 test cases, to prevent people from exploiting the judge.

On 2025.2.6, three hack test cases were added (Credit to

Translated by ChatGPT 5