OpenKattis
Lund University

# 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