S. 平面最近点对

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

平面最近点对

给定 $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

对于 $50\%$ 的数据，保证 $2 \leq n \leq 10^4$ ， $0 \leq x, y \leq 10^9$ 。

对于 $80\%$ 的数据，保证 $2 \leq n \leq 10^5$ ， $0 \leq x, y \leq 10^9$ 。

对于另外 $20\%$ 的数据，保证 $2 \leq n \leq 10^6$ ， $-10^9 \leq x, y \leq 10^9$ 。