题目背景

P1429 平面最近点对（加强版）里最高赞题解写道：

我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 $x$ 坐标排序
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起，在 $n=1000000$ 时都可以在 1 s 内卡过

当然，这是错的。

题目描述

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

输入格式

输入第一行为一个正整数 $n$，表示点数。

接下来 $n$ 行，第 $i$ 行为用空格隔开的整数 $x_i, y_i$，表示 $p_i = (x_i, y_i)$。

输入保证：没有两个坐标完全相同的点。

输出格式

输出一行，包含一个整数 $D^2$，表示距离最近的两个点的距离的平方。

由于输入的点为整点，因此这个值一定是整数。

2
-10000000 -10000000
10000000 10000000

800000000000000

5
1 1
1 9
9 1
9 9
0 10

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$。

本题目标复杂度是 $O(n \log ^2 n)$。设置 350ms 时限的原因是：

1. $O(n \log ^2 n)$ 参考代码使用 cin 不会 TLE。最快的 std 能 $<$ 100ms。
2. @wlzhouzhuan 的程序能恰好在 350ms 内跑 $1000n$ 次检查。
3. 150 组测试数据，为了防止卡评测。