Closest Pair of Points

You are given a collection of points on a 2D plane, represented as an array points where each element is a pair [$x_{i}$, $y_{i}$]. Your objective is to determine the smallest Euclidean distance that exists between any two different points in the set.

The Euclidean distance separating two points [$x_{1}$, $y_{1}$] and [$x_{2}$, $y_{2}$] is defined as $\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}$.

You must devise an algorithm whose time complexity is no worse than O(N log N).

Constraints:

• 2 ≤ points.length ≤ 10⁴
• points[i].length = 2

Example 1:

Example 2:

Example 3:

Examples

Example 1

Input:
3
0 0
1 1
2 2
Output: 1.414214

Example 2

Input:
2
0 0
3 4
Output: 5.000000