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;


#define EPS (1e-10)
const double inf=1e20;

struct Point{
    double x,y;

    Point(double x=0,double y=0):x(x),y(y){}

    Point operator + (Point p) { return Point(x+p.x,y+p.y); }
    Point operator - (Point p) { return Point(x-p.x,y-p.y); }
    Point operator * (double k) { return Point(k*x,k*y); }
    Point operator / (double k) { return Point(x/k,y/k); }

    //向量的大小
    inline double abs(){ return sqrt(norm()); }
    inline double norm() { return x*x+y*y; }

    bool operator < (const Point & p) const{
        return x!=p.x?x<p.x:y<p.y;
    }

    bool operator == (const Point & p) const {
        return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
    }
};

Point a[100005],b[100005];

inline bool CmpY(Point a,Point b){
    return a.y<b.y;
}
inline double Distance(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double Divide_Conquer(int l,int r){
    if(l==r) return inf;
    if(l+1==r) return Distance(a[l],a[r]);
    int mid=l+r>>1;
    double ans=min(Divide_Conquer(l,mid),Divide_Conquer(mid+1,r));
    int len=0;
    for(int i=l;i<=r;i++){
        if(fabs(a[mid].x-a[i].x)<=ans) b[len++]=a[i];
    }
    sort(b,b+len,CmpY);
    for(int i=0;i<len;i++){
        for(int j=i+1;j<len&&(b[j].y-b[i].y<ans);j++){
            ans=min(ans,Distance(b[i],b[j]));
        }
    }
    return ans;
}

inline void solve(int n){
    sort(a,a+n);
    printf("%.10f\n",Divide_Conquer(0,n-1));
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    solve(n);

}