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 <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 200000 + 10;
const double EPS = 1e-7;
const double INF = 1e12;
int sgn(double x) {
    if (x < -EPS) return -1;
    if (x > +EPS) return +1;
    return 0;
}
struct Vec {
    double x,y;
    Vec() {}
    Vec(double x, double y) { 
        this->x = x, this->y = y; 
    }
    void read() { 
        scanf("%lf %lf", &x, &y); 
    }
    void prt() {
        printf("%.8f %.8f\n", x, y); 
    }
    double len() { 
        return sqrt(x * x + y * y); 
    }
    double len2() { 
        return x * x + y * y; 
    }
    bool operator <(const Vec& o)const {
        if(x == o.x)
            return y < o.y;
        return x < o.x;
    }
    Vec operator +(const Vec& o)const { 
        return Vec(x + o.x, y + o.y); 
    }
    Vec operator -(const Vec& o)const { 
        return Vec(x - o.x, y - o.y); 
    }
    Vec operator *(const double& k)const { 
        return Vec(k * x, k * y); 
    }
    double operator *(const Vec& o)const {
        return x * o.x + y * o.y; 
    }
    double operator ^(const Vec& o)const {
        return x * o.y - y * o.x; 
    }
    Vec rotate(double ang){ 
        return Vec(x * cos(ang) - y * sin(ang), x * sin(ang) + y * cos(ang)); 
    }
    Vec change(double l) { 
        if(len() < EPS) return *this; 
        return (*this) * (l/len()); 
    }
};


struct Line {
    Vec A1, A2;
    Line() {}
    Line(Vec A1, Vec A2) {
        this->A1 = A1, this->A2 = A2;
    }
    double len() {
        return (A2-A1).len();
    }
    double Len2() {
        return (A2-A1).len2();
    }
};

// P to L
double disToLine(Vec P, Line L) {
    return abs((P-L.A1)^(L.A2-L.A1)) / L.len();
}
Vec projection(Vec P, Line L) {
    double shadowLen = (P - L.A1) * (L.A2 - L.A1);
    return L.A1 + (L.A2-L.A1).change(shadowLen);
}
Vec rejection(Vec P, Line L) {
    return projection(P,L) * 2 - P;
}
bool onseg(Vec P, Line L) {
    if(disToLine(P, L) > EPS) return 0;
    return (P-L.A1) * (P-L.A2) <= 0;
}
Vec Lineintersect(Line L1, Line L2) {
    // 0 ~ (L2.A1 - L1.A1) ^ (L2.A2 - L1.A1);
    // 1 ~ (L2.A1 - L1.A2) ^ (L2.A2 - L1.A2);
    double F0 = (L2.A1 - L1.A1) ^ (L2.A2 - L1.A1);
    double F1 = (L2.A1 - L1.A2) ^ (L2.A2 - L1.A2);
    if (abs(F1 - F0) < EPS) return Vec(INF, INF);
    return L1.A1 + (L1.A2 - L1.A1) * (- F0 / (F1 - F0));
}
Vec Segintersect(Line L1, Line L2) {
    Vec P = Lineintersect(L1, L2);
    if (P.x == INF) return P;
    if (onseg(P, L1) && onseg(P, L2)) return P;
    return Vec(INF, INF);
}
bool disToSeg(Vec P, Line L) {
    double ans = min((P-L.A1).len(), (P-L.A2).len());
    ans = min(ans, (P - projection(P,L)).len());
    return ans;
}
// 

vector<Vec> convexHull(vector<Vec> v) {
    sort(v.begin(), v.end());
    vector<Vec> ans; ans.resize(2*v.size());
    int top = 0, n = v.size();
    if(n <= 1) return v;

    for(int i = 0; i < n; ans[top++] = v[i++]) {
        while (top > 1 && ((ans[top-1] - ans[top-2]) ^ (v[i] - ans[top-1])) < EPS) -- top;
    }
    for(int i = n-2, t = top; i >= 0; ans[top++] = v[i--]) {
        while (top > t && ((ans[top-1] - ans[top-2]) ^ (v[i] - ans[top-1])) < EPS) -- top;
    } 
    while(ans.size() >= top) ans.pop_back();
    return ans;
}

double PolyArea(vector<Vec> v) {
    double ans = 0;
    int n = v.size();
    //printf("n = %d\n", n);
    for(int i = 0; i < v.size(); i ++) {
        ans = ans + (v[i] ^ v[(i+1)%n]);
    }
    return abs(ans) / 2;
}

vector<Vec> convexCut(vector<Vec> v, Vec P1, Vec P2) {
    vector<Vec> ans;
    for(int i=0;i<v.size();i++) {
        int d1 = sgn((P2-P1)^(v[i]-P1));
        int d2 = sgn((P2-P1)^(v[(i+1)%v.size()]-P1));
        if (d1 >= 0) ans.push_back(v[i]);
        if (d1 * d2 < 0) ans.push_back(Lineintersect(Line(P1,P2), Line(v[i],v[(i+1)%v.size()])));
    }
    return ans;
}

double cloestPair(vector<Vec> v) {
    if (v.size() <= 1) return INF;

    sort(v.begin(), v.end());
    vector<Vec> vL, vR;
    int mid = v.size() / 2;
    for (int i = 0; i < v.size(); i ++) {
        if (i < mid)
            vL.push_back(v[i]);
        else
            vR.push_back(v[i]);
    }
    double d = min(cloestPair(vL), cloestPair(vR));
    
    vector<Vec> strip;
    for (int i = 0; i < v.size(); i ++) {
        if (abs(v[mid].x - v[i].x) <= d + EPS) 
            strip.push_back(v[i]);
    }

    for (int i = 0; i < strip.size(); i ++) swap(strip[i].x, strip[i].y);
    sort(strip.begin(), strip.end());
    for (int i = 0; i < strip.size(); i ++) swap(strip[i].x, strip[i].y);

    for (int i = 0; i < strip.size(); i ++) {
        for (int j = i + 1; j < strip.size(); j ++) {
            if (strip[j].y - strip[i].y > d + EPS) break;
            d = min(d, (strip[j]-strip[i]).len());
        }
    }

    return d;
}

int n; vector<Vec> v;
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        Vec P; P.read(); v.push_back(P);
    }
    printf("%.8f\n", cloestPair(v));
}