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;

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

template <i64 p>
class fp {
public:
    i64 x;
    fp() : x(0) {}
    fp(i64 x_) : x((x_ % p + p) % p) {}
    fp operator+() const { return fp(x); }
    fp operator-() const { return fp(-x); }
    fp& operator+=(const fp& y) {
        x += y.x;
        if (x >= p) x -= p;
        return *this;
    }
    fp& operator-=(const fp& y) { return *this += -y; }
    fp& operator*=(const fp& y) {
        x = x * y.x % p;
        return *this;
    }
    fp& operator/=(const fp& y) { return *this *= fp(inverse(y.x)); }
    fp operator+(const fp& y) const { return fp(x) += y; }
    fp operator-(const fp& y) const { return fp(x) -= y; }
    fp operator*(const fp& y) const { return fp(x) *= y; }
    fp operator/(const fp& y) const { return fp(x) /= y; }
    bool operator==(const fp& y) const { return x == y.x; }
    bool operator!=(const fp& y) const { return !(*this == y); }
    i64 extgcd(i64 a, i64 b, i64& x, i64& y) {
        i64 d = a;
        if (b != 0) {
            d = extgcd(b, a % b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1;
            y = 0;
        }
        return d;
    }
    i64 inverse(i64 a) {
        i64 x, y;
        extgcd(a, p, x, y);
        return (x % p + p) % p;
    }
};

template <i64 p>
i64 abs(const fp<p>& x) { return x.x; }

template <i64 p>
istream& operator>>(istream& is, fp<p>& x) {
    is >> x.x;
    return is;
}

template <i64 p>
ostream& operator<<(ostream& os, const fp<p>& x) {
    os << x.x;
    return os;
}

template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "[";
    for (const auto& v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

template <typename T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename A, typename T, size_t size>
void fill(A (&ary)[size], const T& val) {
    fill((T*)ary, (T*)(ary + size), val);
}

// x未満の要素の個数を返す
template <typename T>
i64 count_less(const vector<T>& v, T x) {
    return lower_bound(begin(v), end(v), x) - begin(v);
}

// x以下の要素の個数を返す
template <typename T>
i64 count_less_or_equal(const vector<T>& v, T x) {
    return upper_bound(begin(v), end(v), x) - begin(v);
}

// xより大きい要素の個数を返す
template <typename T>
i64 count_greater(const vector<T>& v, T x) {
    return end(v) - upper_bound(begin(v), end(v), x);
}

// x以上の要素の個数を返す
template <typename T>
i64 count_greater_or_equal(const vector<T>& v, T x) {
    return end(v) - lower_bound(begin(v), end(v), x);
}

// x未満の要素のうち最大のものを返す
template <typename T>
T max_less(const vector<T>& v, T x) {
    return *(lower_bound(begin(v), end(v), x) - 1);
}

// x以下の要素のうち最大のものを返す
template <typename T>
T max_less_or_equal(const vector<T>& v, T x) {
    return *(upper_bound(begin(v), end(v), x) - 1);
}

// xより大きい要素のうち最小のものを返す
template <typename T>
T min_greater(const vector<T>& v, T x) {
    return *upper_bound(begin(v), end(v), x);
}

// x以上の要素のうち最小のものを返す
template <typename T>
T min_greater_or_equal(const vector<T>& v, T x) {
    return *lower_bound(begin(v), end(v), x);
}

constexpr int inf = 1.01e9;
constexpr i64 inf64 = 4.01e18;
constexpr long double eps = 1e-9;

// 実数値のn分探索のループ回数の上限(2分探索なら50でも十分かもしれない)
constexpr i64 max_loop = 100;

long double tolerance(const long double& a, const long double& b, const long double& epsilon = eps) {
    return epsilon * max({1.l, abs(a), abs(b)});
}

// a<0なら-1, a==0なら0, a>0なら1
int sgn(const long double a, const long double& epsilon = eps) {
    return (a > epsilon) - (a < -epsilon);
}

// a<bなら-1, a==bなら0, a>bなら1
int compare(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return sgn(a - b, is_relative ? tolerance(a, b, epsilon) : epsilon);
}

// a==bか?
bool is_equal(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return compare(a, b, epsilon, is_relative) == 0;
}

// a<bか?
bool is_less(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return compare(a, b, epsilon, is_relative) == -1;
}

// a<=bか?
bool is_less_or_equal(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return compare(a, b, epsilon, is_relative) <= 0;
}

// a>bか?
bool is_greater(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return compare(a, b, epsilon, is_relative) == 1;
}

// a>=bか?
bool is_greater_or_equal(const long double& a, const long double& b, const long double& epsilon = eps, bool is_relative = true) {
    return compare(a, b, epsilon, is_relative) >= 0;
}

template <int D, class point /* =  array<long double,2>*/>
struct kd_tree {
    point p;
    int axis;
    kd_tree<D, point>*left, *right;
    kd_tree(int axis_ = 0) : left(NULL), right(NULL), axis(axis_){};
    kd_tree(vector<point> points, int axis_ = 0) : left(NULL), right(NULL), axis(axis_) {
        assert(points.size());
        build(points, 0, points.size());
    }
    ~kd_tree() {
        delete left;
        delete right;
    }
    kd_tree<D, point>* build(vector<point>& points, int l, int r) {
        int m = (l + r) / 2;
        nth_element(points.begin() + l, points.begin() + m, points.begin() + r, [&](const point& p, const point& q) { return p[axis] < q[axis]; });
        p = points[m];
        if (l < m) {
            left = new kd_tree<D, point>((axis + 1) % D);
            left->build(points, l, m);
        }
        if (m + 1 < r) {
            right = new kd_tree<D, point>((axis + 1) % D);
            right->build(points, m + 1, r);
        }
        return this;
    }
    //例えば,同じ点が大量にinsertされると右の子ばかり増えてしまう.そのようなときは適当なタイミングで全体をリビルドしたほうがよいかも.
    kd_tree<D, point>* insert(const point& q) {
        if (q[axis] < p[axis]) {
            if (left == NULL) {
                left = new kd_tree<D, point>({q}, (axis + 1) % D);
                return left;
            } else
                return left->insert(q);
        } else {
            if (right == NULL) {
                right = new kd_tree<D, point>({q}, (axis + 1) % D);
                return right;
            } else
                return right->insert(q);
        }
    }
    //未検証.多分遅い(O(n))のでerasedタグを付けて置いて,erasedが一定以上増えたら全体をbuildするようにした方が良いかも.
    void erase(const point& q) {
        kd_tree<D, point>* tree = nearest_neighbor(q);
        vector<point> points = tree->collect();
        points.erase(points.rbegin());
        delete tree->left;
        delete tree->right;
        tree->build(points, 0, points.size());
    }
    //未検証
    vector<point> collect() const {
        vector<point> points;
        if (left != NULL) {
            vector<point> left_points = left->collect();
            points.insert(points.end(), left_points.begin(), left_points.end());
        }
        if (right != NULL) {
            vector<point> right_points = right->collect();
            points.insert(points.end(), right_points.begin(), right_points.end());
        }
        points.push_back(p);
        return points;
    };
    const kd_tree<D, point>* nearest_neighbor(const point& q) const {  //const外した方が良いかも
        const kd_tree<D, point>* res = this;
        long double mind = 1e130;
        auto dist = [&](const point& p, const point& q) {
            long double d = 0;
            for (int i = 0; i < D; ++i) d += (p[i] - q[i]) * (p[i] - q[i]);
            return d;
        };
        function<void(const kd_tree<D, point>*)> rec = [&](const kd_tree<D, point>* tree) {
            auto d = dist(tree->p, q);
            if (d < mind) {
                mind = d;
                res = tree;
            }
            if (q[tree->axis] < tree->p[tree->axis]) {
                if (tree->left != NULL) rec(tree->left);
                if (tree->right != NULL and tree->p[tree->axis] - q[tree->axis] <= mind) rec(tree->right);
            } else {
                if (tree->right != NULL) rec(tree->right);
                if (tree->left != NULL and q[tree->axis] - tree->p[tree->axis] <= mind) rec(tree->left);
            }
        };
        rec(this);
        return res;
    }
    vector<point> range_search(const point& lb, const point& ub) const {
        vector<point> res;
        function<void(const kd_tree<D, point>*)> rec = [&](const kd_tree<D, point>* tree) {
            bool in_range = true;
            for (int i = 0; i < D; ++i)
                if (tree->p[i] < lb[i] or ub[i] < tree->p[i]) {
                    in_range = false;
                    break;
                }
            if (in_range) res.push_back(tree->p);
            if (tree->left != NULL and lb[tree->axis] <= tree->p[tree->axis]) rec(tree->left);
            if (tree->right != NULL and ub[tree->axis] >= tree->p[tree->axis]) rec(tree->right);
        };
        rec(this);
        return res;
    }
};

using point=array<long double,2>;

tuple<long double, point, point> search_closest_pair(const vector<point>& ps){
    kd_tree<2,point> kt({ps[0]});
    tuple<long double, point, point> res{inf64, point{}, point{}};
    rep(i,1,ps.size()){
        const auto p=kt.nearest_neighbor(ps[i])->p;
        const auto dx=ps[i][0]-p[0],dy=ps[i][1]-p[1];
        const auto d=sqrtl(dx*dx+dy*dy);

        if(d<get<0>(res)){
            res=make_tuple(d,ps[i],p);
        }

        kt.insert(ps[i]);
    }
    return res;
}

void solve() {
    //constexpr i64 mod = 1'000'000'007;

    i64 n;
    cin >> n;
    vector<long double> x(n),y(n);
    rep(i,0,n){
        cin >> x[i] >> y[i];
    }

    vector<point> ps(n);
    rep(i,0,n){
        ps[i]={x[i],y[i]};
    }

    cout << get<0>(search_closest_pair(ps)) << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}