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 <iostream>
#include <iomanip>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
#define INF (1000)

class Point {
public:
    double x, y;
    Point(double _x = 0.f, double _y = 0.f) : x(_x), y(_y) {}
};

inline bool operator < (const Point& P, const Point& Q)
{
    return (P.x < Q.x) || (P.x == Q.x && P.y < Q.y);
}

inline bool CompY(const Point& P, const Point& Q)
{
    return P.y < Q.y || (P.y == Q.y && P.x < Q.x);
}

istream& operator >> (istream& in, Point& P)
{
    in >> P.x >> P.y;
    return in;
}

double Dist(const Point& P, const Point& Q)
{
    double dx = P.x - Q.x;
    double dy = P.y - Q.y;
    return sqrt(dx * dx + dy * dy);
}

double ClosestDist(const vector<Point>& vP)
{
    int n = (int) vP.size();

    if (n == 1) {
        return INF;
    } else if (n == 2) {
        return Dist(vP[0], vP[1]);
    }

    double dL, dR, dLR;
    vector<Point> vPL, vPR, vPLR;
    auto itM = vP.begin() + n / 2;

    copy(vP.begin(), itM, back_inserter(vPL));
    copy(itM, vP.end(), back_inserter(vPR));
    
    dL = ClosestDist(vPL);
    dR = ClosestDist(vPR);
    double dRet = min(dL, dR);

    Point Left((*itM).x - dRet, -INF);
    Point Right((*itM).x + dRet, INF);
    auto LeftIt = lower_bound(vP.begin(), vP.end(), Left);
    auto RightIt = lower_bound(LeftIt, vP.end(), Right);
    copy(LeftIt, RightIt, back_inserter(vPLR));
    sort(vPLR.begin(), vPLR.end(), CompY);

    int k = (int) vPLR.size();
    dLR = INF;
    for (int l = 0; l < k; ++l) {
        for (int r = l + 1; r < k; ++r) {
            dLR = min(dLR, Dist(vPLR[l], vPLR[r]));
            if (vPLR[r].y - vPLR[l].y > dLR) {
                break;
            }
        }
    }

    dRet = min(dRet, dLR);
    return dRet;
}

int main()
{
    int n;
    cin >> n;
    vector<Point> vP(n);
    for (int i = 0; i < n; ++i) {
        cin >> vP[i];
    }

    sort(vP.begin(), vP.end());
    cout << fixed << setprecision(10);
    cout << ClosestDist(vP) << endl;

    return 0;
}