P7883 Closest Pair of Points on a Plane (Super Super Enhanced Version).

The highest-upvoted solution for [P1429 Closest Pair of Points on a Plane (Enhanced Version)](https://www.luogu.com.cn/problem/P1429) 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.

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.

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 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.

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 $