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;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

using CP = complex<long double>;

const long double EPS = 1e-10;     // 許容する誤差ε
#define EQ(a, b) (abs((a)-(b)) < EPS)   // 2つのスカラーが等しいかどうか
#define EQV(a, b) (EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()))    // 2つのベクトルが等しいかどうか

// double length = abs(a);     // ベクトルaの絶対値
// double distance = abs(a-b);     // 2点a,b間の距離
// CP b = a/abs(a);    // ベクトルaの単位ベクトル
// CP n1 = a*CP(0,+1); CP n2 = a*CP(0,-1);  // ベクトルaの法線ベクトル
// CP un1 = (a*CP(0,+1)/abs(a)); CP un2 = (a*CP(0,-1)/abs(a));  // ベクトルaの単位法線ベクトル

// 内積(dot product) : a・b = |a||b|cosΘ
long double dot(CP a, CP b) {
    return (a.real()*b.real() + a.imag()*b.imag());
}

// 外積(cross product) : a×b = |a||b|sinΘ
long double cross(CP a, CP b) {
    return (a.real()*b.imag() - a.imag()*b.real());
}

// 2直線の直交判定 : a⊥b ⇔ dot(a,b) = 0
int is_orthogonal(CP a1, CP a2, CP b1, CP b2) {
    return EQ(dot(a1-a2, b1-b2), 0.0);
}

// 2直線の平行判定 : a//b ⇔ cross(a,b) = 0
int is_parallel(CP a1, CP a2, CP b1, CP b2) {
    return EQ(cross(a1-a2, b1-b2), 0.0);
}

// 点cが直線a,b上にあるかないか
int is_point_on_line(CP a, CP b, CP c) {
    return EQ(cross(b-a, c-a), 0.0);
}

// 点cが線分a,b上にあるかないか
int is_point_on_lines(CP a, CP b, CP c) {
    // |a-c|+|c-b| <= |a-b|なら線分上
    return (abs(a-c)+abs(c-b) < abs(a-b)+EPS);
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_lines(CP a1, CP a2, CP b1, CP b2) {
    if(is_parallel(a1, a2, b1, b2)) {
        // 平行なので線分の重なり判定
        return is_point_on_lines(a1, a2, b1) || is_point_on_lines(a1, a2, b2) ||
               is_point_on_lines(b1, b2, a1) || is_point_on_lines(b1, b2, a2);
    }
    return (cross(a2-a1, b1-a1)*cross(a2-a1, b2-a1) < EPS) &&
           (cross(b2-b1, a1-b1)*cross(b2-b1, a2-b1) < EPS);
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交点計算
CP intersection_lines(CP a1, CP a2, CP b1, CP b2) {
    CP b = b2-b1;
    long double d1 = abs(cross(b, a1-b1));
    long double d2 = abs(cross(b, a2-b1));
    long double t = d1/(d1+d2);
    return a1+(a2-a1)*t;
}

// a1,a2を通る直線とb1,b2を通る直線の交差判定
int is_intersected_line(CP a1, CP a2, CP b1, CP b2) {
    return !EQ(cross(a1-a2, b1-b2), 0.0);
}

// a1,a2を通る直線とb1,b2を通る直線の交点計算(平行ではない前提)
CP intersection_line(CP a1, CP a2, CP b1, CP b2) {
    CP a = a2-a1; CP b = b2-b1;
    return a1 + a*cross(b, b1-a1)/cross(b, a);
}

// 点a,bを通る直線と点cとの距離
long double distance_line_p(CP a, CP b, CP c) {
    return abs(cross(b-a, c-a))/abs(b-a);
}

// 点a,bを端点とする線分と点cとの距離
long double distance_lines_p(CP a, CP b, CP c) {
    if(dot(b-a, c-a) < EPS) return abs(c-a);
    if(dot(a-b, c-b) < EPS) return abs(c-b);
    return abs(cross(b-a, c-a))/abs(b-a);
}

// 点a1,a2を端点とする線分と点b1,b2を端点とする線分の最短距離
long double distance_lines_lines(CP a1, CP a2, CP b1, CP b2) {
    long double res = 1e18;
    if(is_intersected_lines(a1, a2, b1, b2)) return 0.0L;
    res = min(res, distance_lines_p(a1, a2, b1));
    res = min(res, distance_lines_p(a1, a2, b2));
    res = min(res, distance_lines_p(b1, b2, a1));
    res = min(res, distance_lines_p(b1, b2, a2));
    return res;
}

// s,tを通る直線に対する点pの射影
CP projection(CP s, CP t, CP p) {
    if(EQV(s, t)) return s;
    CP base = t-s;
    return s + base*(dot(p-s, base)/norm(base));
}

// s,tを通る直線に対する点pの反射
CP reflection(CP s, CP t, CP p) {
    CP tmp = projection(s, t, p) - p;
    return p + tmp*2.0L;
}

// n多角形の面積計算
long double polygon_area(const vector<CP> &v) {
    int n = v.size();
    long double res = 0;
    for(int i = 0; i < n; ++i) {
        res += cross(v[(i+n-1)%n], v[(i+n)%n]);
    }
    return fabsl(res)/2.0L;
}

// n多角形の凸性判定
int is_convex(const vector<CP> &v) {
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        if(cross(v[(i+1)%n]-v[i], v[(i+2)%n]-v[(i+1)%n]) < -EPS) return 0;
    }
    return 1;
}

// 凸包
vector<CP> convex_hull(vector<CP> &v) {
    // x座標→y座標で頂点をソート
    auto lmd = [&](const CP &l, const CP &r) {
        if(l.imag() != r.imag()) return l.imag() < r.imag();
        return l.real() < r.real();
        return l.imag() < r.imag();
    };
    vector<CP> res;     // 凸包を構成する頂点
    int n = v.size();
    sort(v.begin(), v.end(), lmd);
    int k = 0;
    res.resize(n*2);
    // 下側凸包
    for(int i = 0; i < n; ++i) {
        while(k > 1 && cross(res[k-1]-res[k-2], v[i]-res[k-1]) < 0) {
            --k;
        }
        res[k++] = v[i];
    }
    // 上側凸包
    for(int i = n-2, t = k; i >= 0; --i) {
        while(k > t && cross(res[k-1]-res[k-2], v[i]-res[k-1]) < 0) {
            --k;
        }
        res[k++] = v[i];
    }
    res.resize(k-1);
    return res;
}

// 凸多角形の直径
long double convex_diameter(vector<CP> &v) {
    vector<CP> cv = convex_hull(v);
    int n = cv.size();
    if(n == 2) return abs(cv[0]-cv[1]);     // 凸包が潰れている例外処理
    int i = 0, j = 0;   // x軸方向に最も遠い点対
    for(int k = 0; k < n; ++k) {
        if(cv[k].real() < cv[i].real()) i = k;
        if(cv[k].real() > cv[j].real()) j = k;
    }
    long double res = 0;
    int si = i, sj = j;
    while(i != sj || j != si) {     // 180度回転で終了
        res = max(res, abs(cv[i]-cv[j]));
        if(cross(cv[(i+1)%n]-cv[i], cv[(j+1)%n]-cv[j]) < 0) {
            (++i) %= n;
        }else {
            (++j) %= n;
        }
    }
    return res;
}

// 凸多角形を点s,tを通る直線で切断(左側が取得できる)
vector<CP> convex_cut(const vector<CP> &v, const CP &s, const CP &t) {
    vector<CP> res;
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        CP nows = v[i], nowt = v[(i+1)%n];
        if(cross(t-s, nows-s) >= -EPS) res.emplace_back(nows);
        if(cross(t-s, nows-s)*cross(t-s, nowt-s) < 0) {
            res.emplace_back(intersection_line(s, t, nows, nowt));
        }
    }
    return res;
}

// n多角形に対する点pの包含関係(自己交差多角形は例外)
int contain_polygon_point(const vector<CP> &v, CP p) {
    int contain = 0, on_segment = 0;
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        on_segment |= is_point_on_lines(v[i], v[(i+1)%n], p);   // 辺上判定
        CP s = v[i]-p, t = v[(i+1)%n]-p;
        if(s.imag() > t.imag()) swap(s, t);     // 下側を基準にする
        if(s.imag()*t.imag() <= 0 && t.imag() > 0 && cross(s, t) > 0) {
            contain = !contain;     // 交差回数が奇数なら内側
        }
    }
    if(on_segment) return 1;    // 辺上
    if(contain) return 2;       // 内側
    return 0;       // 外側
}

// 最近点対距離
long double closest_pair(vector<CP> &v, int l = -1, 
                         int r = -1, bool reqsqrt = 0) {
    if(l == r && l == -1) {
        l = 0; r = v.size(); reqsqrt = 1;
        // x座標→y座標で昇順ソート
        auto lmd = [&](const CP &l, const CP &r) {
            if(l.real() != r.real()) return l.real() < r.real();
            return l.imag() < r.imag();
        };
        sort(v.begin(), v.end(), lmd);
    }
    if(r-l < 2) return 1e18;
    if(r-l == 2) {
        if(v[l].imag() > v[l+1].imag()) swap(v[l], v[l+1]);
        if(reqsqrt) return abs(v[l]-v[l+1]);
        return norm(v[l]-v[l+1]);
    }
    int mid = (l+r)/2;
    long double x = v[mid].real();
    long double res = min(closest_pair(v, l, mid), closest_pair(v, mid, r));
    auto f = [](CP pl, CP pr) { return pl.imag() < pr.imag(); };
    inplace_merge(v.begin()+l, v.begin()+mid, v.begin()+r, f);
    vector<CP> tmp;
    for(int i = l; i < r; ++i) {
        long double dx = abs(v[i].real()-x);
        int tsize = tmp.size();
        if(dx*dx >= res) continue;
        for(int j = 0; j < tsize; ++j) {
            CP delta = v[i]-tmp[tsize-1-j];
            if(delta.imag()*delta.imag() >= res) break;
            res = min(res, norm(delta));
        }
        tmp.emplace_back(v[i]);
    }
    if(reqsqrt) res = sqrtl(res);
    return res;
}

// 3点の位置関係を判定
int calc_clockwise(CP p0, CP p1, CP p2) {
    CP x = p1-p0, y = p2-p0;
    if(cross(x, y) > EPS) return 1;     // "COUNTER_CLOCKWISE"
    if(cross(x, y) < -EPS) return -1;   // "CLOCKWISE"
    if(dot(x, y) < 0) return 2;         // "ONLINE_BACK"
    if(norm(x) < norm(y)) return -2;    // "ONLINE_FRONT"
    return 0;                           // "ON_SEGMENT" 
}

int main() {
    int n; cin >> n;
    vector<CP> point;
    for(int i = 0; i < n; ++i) {
        long double a, b; cin >> a >> b;
        point.emplace_back(CP(a, b));
    }
    cout << fixed << setprecision(10);
    cout << closest_pair(point) << endl;
}