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;

typedef long long ll;

// 最近点対問題を解く(O(nlogn))
/*
点を x 座標, y 座標によって左半分と右半分に分けるとする。
最近点対の距離は、1), 2) の最小値
1) 2点 p, q が共に左半分または右半分に含まれるような組(p, q)の距離

2) 2点 p, q が異なる領域に含まれるような組(p, q)の距離
点を左半分と右半分に分ける直線を l として、その直線の x 座標を l として、
x_0 - d < x < x_0 + d を満たす(x_p, y_p) に対して y_p - d < y <= y_p を満たす点との
距離を考えればよい
*/

// first を x 座標, second を y 座標とする
typedef pair<double, double> PD;

const double INF = 1000000000;
const int MAX_N = 100010;

pair<double, double> A[MAX_N];

// y 座標の昇順で merge するための比較関数
bool compare_y(PD a, PD b){
    return a.second < b.second;
}

// a は x 座標の昇順
double closest_pair(PD *a, int n){
    if(n <= 1) return INF;
    int m = n / 2;
    double x = a[m].first;
    // 1) にあたる
    double d = min(closest_pair(a, m), closest_pair(a + m, n - m));
    inplace_merge(a, a + m, a + n, compare_y); // sorted な 2 つの範囲を merge
    // ここで a は　y 座標の昇順

    // 2) にあたる
    vector<PD> b; // 直線から距離 d 未満の頂点
    for(int i=0;i<n;i++){
        if(fabs(a[i].first - x) >= d) continue;

        // b に入っている頂点を、末尾から y 座標の差が d 以上になるまで見ていく
        for(int j=0;j<b.size();j++){
            double dx = a[i].first - b[b.size() - j - 1].first;
            double dy = a[i].second - b[b.size() - j - 1].second;
            if(dy >= d) break;
            d = min(d, sqrt(dx * dx + dy * dy));
        }
        b.push_back(a[i]);
    }
    return d;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N; cin >> N;
    for(int i=0;i<N;i++){
        double x, y; cin >> x >> y;
        A[i] = make_pair(x, y);
    }
    sort(A, A + N);
    cout << fixed << setprecision(15) << closest_pair(A, N) << endl;
}