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>
using namespace std;
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<utility>
 
typedef pair<double, double> point;
typedef point* data;
 
double dist(const point &p1, const point &p2)
{
    double dx = p1.first - p2.first;
    double dy = p1.second - p2.second;
    return sqrt(dx * dx + dy * dy);
}
 
bool sort_y(const point &p1, const point &p2){ return p1.second < p2.second; }
 
double closest(data X, data Y, int n)
{
    if(n <= 3){
        double d = dist(X[0], X[1]);
        for(int i = 0; i < n; i++){ Y[i] = X[i]; }
        sort(Y, Y + n, sort_y);
 
        if(n < 3){ return d; }
        else{ return min(d, min(dist(X[0], X[2]), dist(X[1], X[2]))); }
    }
    int m = (n >> 1);
    double median = X[m].first;
    double d = min(closest(X, Y, m), closest(X + m, Y + m, n - m));
 
    data Z; int size = 0;
    Z = new point [n];
    int i = 0, j = m;
    while(i < m || j < n){
        if(i < m && j < n){
            if(Y[i].second < Y[j].second){
                Z[size] = Y[i]; size++; i++;
            }else{
                Z[size] = Y[j]; size++; j++;
            }
        }
        if(i == m){ while(j < n){ Z[size] = Y[j]; size++; j++; }; }
        if(j == n){ while(i < m){ Z[size] = Y[i]; size++; i++; }; }
    };

	for(i = 0; i < n; i++){ Y[i] = Z[i]; } // merge.

    int resize = 0;
    for(i = 0; i < size; i++){
        if(fabs(Z[i].first - median) <= d){ Z[resize] = Z[i]; resize++; }
    }
 
    int a = 0;
    for(i = 1; i < resize; i++){
        for(j = a; j < i; j++){
            if(Z[i].second - Z[j].second > d){ a++; }
            else{
                d = min(d, dist(Z[i], Z[j]));
            }
        }
    }
    delete [] Z;
    return d;
}
 
int main()
{
    data X, Y;
    int i, n;
    scanf("%d", &n);
    X = new point [n];
    Y = new point [n];
 
    double co_x, co_y;
    for(i = 0; i < n; i++){
        scanf("%lf %lf", &co_x, &co_y);
        X[i] = make_pair(co_x, co_y);
    }
    sort(X, X + n);
 
    double d = closest(X, Y, n);
    printf("%.12f\n", d);
 
    cin >> n;
    delete [] X;
    delete [] Y;
 
    return 0;
}