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<bits/stdc++.h>

using namespace std;

typedef complex<double> Point;
const double eps = 1e-9;
const int N = 1e5+10;
const double inf = 1e6;

bool eq(const double &a,const double &b)
{
    return abs(a-b)<eps;
}

bool cmp(const Point &a,const Point &b)
{
    if(eq(a.real(),b.real()))
    {
        return a.imag()<b.imag();
    }else
    {
        return a.real()<b.real();
    }
}

bool cmp1(const Point &a,const Point &b)
{
    if(eq(a.imag(),b.imag()))
    {
        return a.real()<b.real();
    }else
    {
        return a.imag()<b.imag();
    }
}

int get_low(const vector<Point> &arr,double x)
{
    int sz = arr.size();
    int l=0,r=sz-1;
    while(l<r)
    {
        int mid = (l+r)/2;
        if(arr[mid].imag()<x)
        {
            l = mid+1;
        }else
        {
            r = mid;
        }
    }
    if(arr[l].imag()<x) return sz;
    return l;
}

double closest_pair(Point *points,int sz)
{
    if(sz<4)
    {
        double ans = inf;
        for(int i=0;i<sz;i++)
        {
            for(int j=0;j<i;j++)
            {
                double tmp = abs(points[i]-points[j]);
                if(tmp < ans)
                {
                    ans = tmp;
                }
            }
        }
        return ans;
    }
    int mid =  sz/2;
    double x = points[mid].real();
    double d = min(closest_pair(points,mid),closest_pair(points+mid,sz-mid));
    vector<Point> arr;
    for(int i = mid;i<sz;i++)
    {
        if(points[i].real()-x < d+eps) arr.push_back(points[i]);
    }
    sort(arr.begin(),arr.end(),cmp1);
    double ans = d;
    for(int i=0;i<mid;i++)
    {
        if(x-points[i].real()<d+eps)
        {
            int low = get_low(arr,points[i].imag()-d-eps);
            int high = get_low(arr,points[i].imag()+d+eps);
            for(int j=low;j<high;j++)
            {
                double dist = abs(points[i]-arr[j]);
                if(dist<ans)
                {
                    ans = dist;
                }
            }
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    Point points[N];

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        double x,y;
        cin>>x>>y;
        points[i] = Point(x,y);
    }
    sort(points,points+n,cmp);

    cout<<fixed<<setprecision(10)<<closest_pair(points,n)<<endl;

    return 0;
}