平面最近点对

【题目描述】

给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。

【输入格式】

第一行：一个正整数 $n$，表示点个数。

接下来 $n$ 行，每行两个实数 $x$ 和 $y$，表示一个点的横坐标和纵坐标，中间用一个空格隔开。

【输出格式】

仅一行，一个实数，表示最短距离，精确到小数点后面 $4$ 位。

【样例输入1】

3
1 1
1 2
2 2

【样例输出1】

1.0000

【样例输入输出2】

点击下载样例2

【提示】

$(a,b)$ 和 $(c,d)$ 间的距离为 $\sqrt{(a-b)^2+(c-d)^2}$。

【数据规模与约定】

对于 $100\%$ 的数据，$10^5 \le n \le 2\times 10^5,0 \le x,y \le 10^9$。

【来源】

$lgc$