Hide
Problem A
Closest Points
Given a set of points in the plane, find the minimal distance between a pair of points in the set.
Input
The first line contains an integer $N$, such that $2 \leq N \leq 200\, 000$. Then follow $N$ lines which each describe a point in the plane.
A description of a point contains two integers $x_ i \ y_ i$. These integers are the coordinates of the point, such that $-10\, 000\, 000 \leq x_ i, y_ i \leq 10\, 000\, 000$.
Output
Output the distance between the two closest points. The distance needs only to be within an absolute or relative margin of $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 0 0 1 1 |
1.414213562 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 -10000000 -10000000 -10000000 10000000 10000000 10000000 |
20000000 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 -10 0 1 -12 -1 12 -3 20 2 0 3 -20 |
8.246211251235321 |