U531951 平面最近点对（加强加强加强版）

[P7883 平面最近点对（加强加强版）](/problem/P7883)里最高赞题解写道： > 我们充分发扬人类智慧：\ > 将所有点全部绕原点旋转同一个角度，然后按 $x \times y$ 排序\ > 根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远\ > 所以我们只取每个点向前的 $50$ 个点来计算答案\ > 这样速度快得飞起，在 $n=400000$ 时都可以在 124ms 内卡过 当然，这是错的。 ### update0501：更新一个点密度更大的数据（#1） （事实上这个点是以前造的，当时觉得数据够强了，就没有放上去）

给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$，请输出距离最近的两个点的距离。

输入第一行为一个正整数 $n$，表示点数。 接下来 $n$ 行，第 $i$ 行为用空格隔开的整数 $x_i, y_i$，表示 $p_i = (x_i, y_i)$。 输入保证：没有两个坐标完全相同的点。

输出一行，包含一个整数 $D^2$，表示距离最近的两个点的距离的**平方**。 由于输入的点为整点，因此这个值一定是整数。

对于第二组样例，$(1, 9)$、$(0, 10)$ 两个点最近，距离为 $\sqrt 2$，因此你需要输出 $2$。 ### 数据范围 对于 $100 \%$ 的数据，$2 \leq n \leq 4 \times 10^5$，$-10^7 \leq x_i, y_i \leq 10^7$。 四个点，分别是：超级网格图、随机数据、卡按照 $x^2+y^2$ 排序、卡按照 $x+y$ 排序 期望算法 $O(n \log n)$