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 <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int inf = 1e9 + 10;

struct vec {
    double x, y;
    double p;
    vec()
    {
    }
    vec(double a, double b)
    {
        x = a, y = b;
    }
    bool operator>(const vec a) const
    {
        return x == a.x ? y > a.y : x > a.x;
    }
    vec operator-(const vec a) const
    {
        return vec(x - a.x, y - a.y);
    }
    vec operator+(const vec a) const
    {
        return vec(x + a.x, y + a.y);
    }
    bool operator<(const vec a) const
    {
        return x == a.x ? y < a.y : x < a.x;
    }
    friend ostream& operator<<(ostream& out, vec& a)
    {
        cout << a.x << ' ' << a.y;
        return out;
    }
    friend istream& operator>>(istream& in, vec& a)
    {
        in >> a.x >> a.y;
        return in;
    }

} p[MAXN];
int n;
double changdu(vec a)
{
    return sqrt(a.x * a.x + a.y * a.y);
}
bool cmp(vec a, vec b)
{
    return a.y < b.y;
}

vec temp[MAXN];
double cdq(int l, int r)
{
    if (l == r)
        return inf;
    int mid = (l + r) >> 1;

    double ans = cdq(l, mid);
    ans = min(ans, cdq(mid + 1, r));

    int tot = 0;
    for (int i = l; i <= r; i++)
        if (fabs(p[mid].x - p[i].x) <= ans)
            temp[tot++] = p[i];

    sort(temp,temp+tot, cmp);

    for (int i = 0; i < tot; i++)
        for (int j = i + 1; j <tot; j++) {
            if (temp[j].y - temp[i].y > ans)
                break;
            ans = min(ans, changdu(temp[j] - temp[i]));
        }
    return ans;
}
int main()
{
    // freopen("txt.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    sort(p + 1, p + n + 1);
    double ans = cdq(1, n);
    printf("%.8f\n", ans);
    return 0;
}