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;
const double inf = 30000;
const double eps = 1e-8;
const int N = 2e5 + 100;
int sgn (double x) {
    if (fabs (x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
struct point {
    double x, y;
    point () {}
    point (double _x, double _y) {
        x = _x, y = _y;
    }
    void input () {
        scanf ("%lf %lf", &x, &y);
    }
    point operator - (const point &b) const {
        return point (x - b.x, y - b.y);
    }
    bool operator == (const point &b) const {
        return sgn (x - b.x) == 0 && sgn (y - b.y) == 0;
    }
    bool operator < (const point &b) const {
        if (sgn (y - b.y) == 0) return x < b.x;
        return y < b.y;
    }
    double operator * (const point &b) const {
        return x * b.x + y * b.y;
    }
    double operator ^ (const point &b) const {
        return x * b.y - y * b.x;
    }
    point operator / (const double &b) const {
        return point (x / b, y / b);
    }
    point operator * (const double &b) const {
        return point (x * b, y * b);
    }
    point operator + (const point &b) const {
        return point (x + b.x, y + b.y);
    }
    double cross (point a, point b) {
        return (point (a - *this) ^ point (b - *this));
    }
    double dot (point a, point b) {
        return (point (a - *this) * point (b - *this));
    }
    double len () {
        return hypot (x, y);
    }
    bool on_seg (point a, point b) {///点是否在线段ab上
        return sgn (cross (a, b)) == 0 && dot (a, b) <= 0;
    }
} ps[N], num[N];
///两线段的交点
point spp (point s1, point e1, point s, point e) {
    if (s.dot (e, s1) > s.dot (e, e1)) swap (s1, e1);
    point p = e - s;
    double len = p.len ();
    double a = fabs (s.cross (e, s1)) / len;
    double b = fabs (s.cross (e, e1)) / len;
    double a1 = s.dot (e, s1) / len;
    double b1 = s.dot (e, e1) / len;
    double k = a1 + fabs(a1 - b1) / (a + b) * a;
    p = p / len, p = p * k, p = p + s;
    return p;
}
///两线段是否相交
bool seg (point a, point b, point c, point d) {
    if (a.on_seg (c, d)) return true;
    if (a.cross (b, d) * a.cross (b, c) < 0 && c.cross (d, b) * c.cross (d, a) < 0) return true;
    return false;
}
/// 点的投影是否在线段ab上
//bool check (point p, point a, point b) {
//    point x = b - a;
//    double k = x.len ();
//    double u = a.dot (p, b) / k;
//    x = (x / k) * u;
//    x = x + a;
//    if (x.on_seg (a, b)) return true;
//    return false;
//}
//struct polygon {
//    int n;
//    point ps[N];
//    void input () {
//        cin >> n;
//        for (int i = 0; i < n; i++) ps[i].input ();
//    }
//    ///排序规则
//    struct cmp {
//        point p;
//        cmp (point _p) {
//            p = _p;
//        }
//        bool operator () (const point &aa, const point &bb) {
//            point a = aa, b = bb;
//            int d = sgn (p.cross (a, b));
//            if (d == 0) return point (a - p).len () < point (b - p).len ();
//            else return d > 0;
//        }
//    };
//    ///排序
//    void norm () {
//        point mi = ps[0];
//        for (int i = 0; i < n; i++) mi = min (mi, ps[i]);
//        sort (ps, ps + n, cmp (mi));
//    }
//    ///求凸包
////    void getconvex (polygon &convex) {
////        sort (ps, ps + n);
////        int &top = convex.n;
////        top = 0;
////        convex.ps[top++] = ps[0];
////        for (int i = 1; i < n; i++) {
////            while (top >= 2 && convex.ps[top - 2].cross (convex.ps[top - 1], ps[i]) < 0) top--;
////            convex.ps[top++] = ps[i];
////        }
////        int t = 0;
////        for (int i = n - 2; i >= 0; i--) {
////            while (t && convex.ps[top - 2].cross (convex.ps[top - 1], ps[i]) < 0) top--, t--;
////            if (!i) break;
////            convex.ps[top++] = ps[i];
////            t++;
////        }
////    }
//    ///几何面积
//    double mianji () {
//        if (n < 2) return 0;
//        double ans = 0;
//        ps[n] = ps[0];
//        for (int i = 1; i <= n; i++) ans += point (0, 0).cross (ps[i - 1], ps[i]);
//        return ans;
//    }
//} dd, ans;
int cmp1 (point a, point b) {
    return a.x < b.x;
}
int cmp2 (point a, point b) {
    return a.y < b.y;
}
double dfs (int l, int r) {
    if (r - l == 1)
        return point (ps[l] - ps[r]).len ();
    if (r - l == 2) {
        double a = point (ps[l] - ps[l + 1]).len ();
        double b = point (ps[l] - ps[l + 2]).len ();
        double c = point (ps[l + 1] - ps[l + 2]).len ();
        return min (a, min (b, c));
    }
    int mid = l + r >> 1, v = 0;
    double ans = min (dfs (l, mid), dfs (mid, r));
    for (int i = l; i <= r; i++) if (fabs (ps[i].x - ps[mid].x) < ans) num[v++] = ps[i];
    sort (num, num + v, cmp2);
    for (int i = 0; i < v; i++) {
        for (int j = i + 1; j < v; j++) {
            if (sgn (num[j].y - num[i].y - ans) >= 0) break;
            ans = min (ans, point (num[j] - num[i]).len ());
        }
    }
    return ans;
}
int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) ps[i].input ();
    sort (ps + 1, ps + 1 + n, cmp1);
    printf ("%.12f\n", dfs (1, n));
    return 0;
}