Problem: For given n points in metric space, find the distance of the closest points.

Constraints

* 2 ≤ n ≤ 100,000
* -100 ≤ x, y ≤ 100

Input


n
x0 y0
x1 y1
:
xn-1 yn-1


The first integer n is the number of points.

In the following n lines, the coordinate of the i-th point is given by two real numbers xi and yi. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the distance in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

2
0.0 0.0
1.0 0.0


Output

1.000000


Input

3
0.0 0.0
2.0 0.0
1.0 1.0


Output

1.41421356237

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <cmath>

using namespace std;

using point = pair<float, float>;

inline float distance(point &a, point &b) { return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2)); }

float closestSplit(point x[], int n, float sigma)
{
    float xbar = x[n/2].first, d = sigma;
    point sy[n];
    int j = 0;
    for (int i = 0; i < n; ++i)
        if (abs(xbar - x[i].first) <= sigma)
            sy[j++] = x[i];
    sort(sy, sy+j, [] (point &a, point &b)
    {
        return a.second < b.second;
    });
    for (int i = 0; i < j; ++i)
        for (int k = 1; k < 8 && i+k < j; ++k)
            d = min(d, distance(sy[i], sy[i+k]));
    return d;
}

float closestPairDistance(point x[], int n)
{
    if (n < 4)
    {
        float d = numeric_limits<float>::max();
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                d = min(d, distance(x[i], x[j]));
        return d;
    }
    float sigma = min(closestPairDistance(x, n/2), closestPairDistance(x + n/2, n - n/2));
    return closestSplit(x, n, sigma);
}

int main()
{
    int n;
    scanf("%d", &n);
    point x[n];
    for (int i = 0; i < n; ++i)
        scanf("%f %f", &x[i].first, &x[i].second);
    sort(x, x+n, [] (point &a, point &b)
    {
        return a.first < b.first;
    });
    cout << setprecision(8) << showpoint << fixed << closestPairDistance(x, n) << endl;
}