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<vector>
#include<cmath>
#include<algorithm>

const double INF = 1e9;
const double EPS = 1e-9;

struct Point {
    Point() :x(INF), y(INF) {}
    Point(double x, double y) :x(x), y(y) {}
    double x, y;
};
struct Compare {
    bool f;
    Compare(bool f = false) :f(f) {}
    bool operator()(const Point& lhs, const Point& rhs) const {return f ? lhs.y < rhs.y : lhs.x < rhs.x;}
};
double distance(const Point& lhs, const Point& rhs) {return std::hypot(lhs.x - rhs.x, lhs.y - rhs.y);}

struct Result {
    double d;
    Point p1, p2;
    Result() :d(INF) {}
    Result(double d, const Point p1, const Point p2) :d(d), p1(p1), p2(p2) {}
};
bool operator<(const Result& lhs, const Result& rhs) {return lhs.d < rhs.d;}

Result closest_pair_recursion(const std::vector<Point>::const_iterator& begin, const std::vector<Point>::const_iterator& end) {
    int size = end - begin;
    if(size <= 1) return Result();

    auto mid = begin + size / 2;
    Result r = std::min(closest_pair_recursion(begin, mid), closest_pair_recursion(mid, end));

    auto left = std::lower_bound(begin, end, Point(mid->x - r.d - EPS, mid->y), Compare());
    auto right = std::upper_bound(left, end, Point(mid->x + r.d + EPS, mid->y), Compare());
    std::vector<Point> y_sorted(left, right);
    std::sort(y_sorted.begin(), y_sorted.end(), Compare(true));

    for(auto i = y_sorted.begin(); i != y_sorted.end(); ++i) {
        for(auto j = i + 1; j != y_sorted.end(); ++j) {
            if(j->y - i->y >= r.d) break;
            if(distance(*i, *j) >= r.d) continue;
            r = Result(distance(*i, *j), *i, *j);
        }
    }
//     // y 座標の差が r.d 以上になる点を予め計算：微妙に遅い
//     for(auto i = y_sorted.begin(); i != y_sorted.end(); ++i) {
//         auto top = std::upper_bound(i + 1, y_sorted.end(), Point(i->x, i->y + r.d + EPS), Compare(true));
//         for(auto j = i + 1; j != top; ++j) {
//             if(distance(*i, *j) >= r.d) continue;
//             r = Result(distance(*i, *j), *i, *j);
//         }
//     }

    return r;
}
Result closest_pair(std::vector<Point> point) {
    std::sort(point.begin(), point.end(), Compare());
    return closest_pair_recursion(point.begin(), point.end());
}

////////////////////////////////////////////////////////////////////////////////
#include<iostream>
#include<iomanip>
using namespace std;

int main() {
    int n;
    vector<Point> v;
    for(cin >> n; n > 0; --n) {
        double x, y;
        cin >> x >> y;
        v.push_back(Point(x, y));
    }
    auto res = closest_pair(v);
    cout <<setprecision(12) << fixed << res.d << endl;
}