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 <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <stdbool.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class Point {
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) { return Point(x+p.x, y+p.y); }
    Point operator - (Point p) { return Point(x-p.x, y-p.y); }
    Point operator * (double a) { return Point(a*x, a*y); }
    Point operator / (double a) { return Point(x/a, y/a); }

    double abs() {return sqrt(norm()); }
    double norm() {return x*x + y*y; }
};

double getMinLR(vector<Point>&, int m0, int m1, int m, double delta);
double getClosestPair(vector<Point>& v, int m0, int m1, bool isSorted);

int main(){
    #if 0
    std::ifstream in("test.txt");
    std::cin.rdbuf(in.rdbuf());
    #endif

    int n;
    cin >> n;
    vector<Point> zPoints(n);

    for (int i=0; i<n; i++){
        cin >> zPoints[i].x >> zPoints[i].y;
    }

    cout << fixed << setprecision(10) << getClosestPair(zPoints, 0, n-1, false) << endl;

    return 0;
}

bool xComp(Point p1, Point p2){   
    return  (p1.x < p2.x);
}

bool yComp(Point p1, Point p2){   
    return  (p1.y < p2.y);
}

double getMinLR(vector<Point>& v, int m0, int m1, int m, double delta){
    vector<Point> zMargin; //点mからx座標が+-deltaの範囲にいる点の集合
    zMargin.push_back(v[m]);
    for (int i=m-1; i>=m0; i--){
        if ( (v[m].x - v[i].x) > delta ) break;
        zMargin.push_back(v[i]);
    }
    for (int i=m+1; i<=m1; i++){
        if ( (v[i].x - v[m].x) > delta ) break;
        zMargin.push_back(v[i]);
    }

    sort(zMargin.begin(), zMargin.end(), *yComp); //y方向にsort
    int n = zMargin.size();
    Point buffer(zMargin[n-1].x, zMargin[n-1].y + 2*delta );
    for (int i=0; i<4; i++){
        zMargin.push_back(buffer);
    }

    double minLR = delta;

    for (int i=0; i<n-1; i++){
        for (int j=i+1; j<=i+5; j++){
            double distance = (zMargin[j] - zMargin[i]).abs();
            minLR = (distance < minLR)? distance : minLR;
        }
    }
    
    return minLR;
}

double getClosestPair(vector<Point>& v, int m0, int m1, bool isSorted=true){
    if (m0 == m1){ //１点の場合はInfinityを返す
        return __DBL_MAX__;
    }
    if (m0 + 1 == m1){ //２点の場合は２点間の距離を返す。後にdeltaの有限性を保証
        return (v[m0] - v[m1]).abs();
    }

    if(!isSorted) sort(v.begin(), v.end(), *xComp); //最初だけx座標で昇順にsort
    int m = (m0 + m1) / 2;
    double minL = getClosestPair(v, m0, m);
    double minR = getClosestPair(v, m+1, m1);
    double delta = min(minL, minR);
    double minLR = getMinLR(v, m0, m1, m, delta);

    return min(delta, minLR);
}