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 rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<int D,class point> struct kd_tree{
    point p;
    int axis;
    kd_tree<D,point>* left,*right;
    kd_tree(int axis_=0):left(NULL),right(NULL),axis(axis_){};
    kd_tree(vector<point> points,int axis_=0):left(NULL),right(NULL),axis(axis_){ assert(points.size()); build(points,0,points.size()); }
    ~kd_tree(){ delete left; delete right; }
    kd_tree<D,point>* build(vector<point> &points,int l,int r){
        int m=(l+r)/2;
        nth_element(points.begin()+l,points.begin()+m,points.begin()+r,[&](const point& p,const point& q){ return p[axis]<q[axis]; });
        p=points[m];
        if(l<m){
            left=new kd_tree<D,point>((axis+1)%D);
            left->build(points,l,m);
        }
        if(m+1<r){
            right=new kd_tree<D,point>((axis+1)%D);
            right->build(points,m+1,r);
        }
        return this;
    }
    kd_tree<D,point>* insert(const point& q){
        if(q[axis]<p[axis]){
            if(left==NULL){
                left=new kd_tree<D,point>({q},(axis+1)%D);
                return left;
            }else return left->insert(q);
        }else{
            if(right==NULL){
                right=new kd_tree<D,point>({q},(axis+1)%D);
                return right;
            }else return right->insert(q);
        }
    }
    //????????????(O(n))?????§erased?????°?????????????????????,erased???????????\????¢????????????¨??????build???????????????????????????????????????.
    void erase(const point& q){
        kd_tree<D,point>* tree=nearest_neighbor(q);
        vector<point> points=tree->collect();
        points.erase(points.rbegin());
        delete tree->left;
        delete tree->right;
        tree->build(points,0,points.size());
    }
    vector<point> collect()const{
        vector<point> points;
        if(left!=NULL){
            vector<point> left_points=left->collect();
            points.insert(points.end(),left_points.begin(),left_points.end());
        }
        if(right!=NULL){
            vector<point> right_points=right->collect();
            points.insert(points.end(),right_points.begin(),right_points.end());
        }
        points.push_back(p);
        return points;
    };
    const kd_tree<D,point>* nearest_neighbor(const point& q)const{ //const???????????????????????????
        const kd_tree<D,point>* res=this;
        long double mind=inf64;
        auto dist=[&](const point& p,const point& q){
            long double d=0;
            for(int i=0; i<D; ++i) d+=(p[i]-q[i])*(p[i]-q[i]);
            return d;
        };
        function<void(const kd_tree<D,point>*)> rec=[&](const kd_tree<D,point>* tree){
            auto d=dist(tree->p,q);
            if(d<mind){
                mind=d;
                res=tree;
            }
            if(q[tree->axis]<tree->p[tree->axis]){
                if(tree->left!=NULL) rec(tree->left);
                if(tree->right!=NULL and tree->p[tree->axis]-q[tree->axis]<=mind) rec(tree->right);
            }else{
                if(tree->right!=NULL) rec(tree->right);
                if(tree->left!=NULL and q[tree->axis]-tree->p[tree->axis]<=mind) rec(tree->left);
            }
        };
        rec(this);
        return res;
    }
    vector<point> range_search(const point& lb,const point& ub)const{
        vector<point> res;
        function<void(const kd_tree<D,point>*)> rec=[&](const kd_tree<D,point>* tree){
            bool in_range=true;
            for(int i=0; i<D; ++i) if(tree->p[i]<lb[i] or ub[i]<tree->p[i]){
                in_range=false;
                break;
            }
            if(in_range) res.push_back(tree->p);
            if(tree->left!=NULL and lb[tree->axis]<=tree->p[tree->axis]) rec(tree->left);
            if(tree->right!=NULL and ub[tree->axis]>=tree->p[tree->axis]) rec(tree->right);
        };
        rec(this);
        return res;
    }
};

void solve(){
    int n;
    cin >> n;

    using point=vector<long double>;
    vector<point> ps;
    rep(i,0,n){
        long double x,y;
        cin >> x >> y;
        ps.push_back(point({x,y}));
    }

    kd_tree<2,point> kt({ps[0]});
    long double ans=inf64;
    rep(i,1,n){
        point p=kt.nearest_neighbor(ps[i])->p;
        ans=min(ans,sqrtl((ps[i][0]-p[0])*(ps[i][0]-p[0])+(ps[i][1]-p[1])*(ps[i][1]-p[1])));
        kt.insert(ps[i]);
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}