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

typedef pair<double, double> point;
typedef point* data;

inline double dist(const point &a, const point &b)
{
    double dx = a.first - b.first, dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

bool sort_y(const point &P1, const point &P2){ return P1.second < P2.second; }

double closest(data P, int n)
{
    if(n <= 1) return 1000;
    if(n == 2) return dist(P[0], P[1]);
    int m = n / 2;
    sort(P, P + n, sort_y); // y_sort, down to up.
	double median = P[m].second;
    double d = min(closest(P, m), closest(P + m, n - m));

    sort(P, P + n);
    vector<point> V;
	
    int i, k, a = 0, size = 0;
    for(i = 0; i < n; i++){
        if(fabs(P[i].second - median) > d) continue;
        V.push_back(P[i]);
        size++;
        for(k = a; k < size - 1; k++){
            if(V[size - 1].first - V[k].first > d){ a++; }
            else{
                d = min(d, dist(V[size - 1], V[k]));
            }
        }
    }
    return d;
}

int main()
{
	int i, n;
	double x, y;
	scanf("%d", &n);
	data P;
	P = new point [n];

	for(i = 0; i < n; i++){
		scanf("%lf %lf", &x, &y);
		P[i] = make_pair(x, y);
	}
	printf("%.12f\n", closest(P, n));

	return 0;
}