平面最近点对

题目描述

给定平面上 $n$ 个点，你需要求出其中最近的一对点的欧几里得距离。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个数 $x_i, y_i$， 表示一个点的坐标。

输出格式

输出一行一个数表示答案，相对误差或绝对误差在 $10^{−6}$ 内即为正确。

样例输入

3
1.0 2.0
1.0 3.0
1.0 5.0

样例输出

1.00000000

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 2 \times 10 ^ 5, 0\leq x_i, y_i\leq 10^9$。