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>

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 y_less(const point &P1, const point &P2){ return P1.second < P2.second; }
bool y_greater(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, y_less); // y_sort, down to up.
	double median = P[m].second;
    double d = min(closest(P, m), closest(P + m, n - m));

    sort(P, P + m, y_less);
    sort(P + m, P + n, y_greater);
    int a, b;
    for(a = m - 1; a > 0; a--){ if(P[a].second < median - d) break; }
    for(b = n - 1; b > m; b--){ if(P[b].second > median + d) break; }
    sort(P + a, P + m);
    sort(P + b, P + n);

    // x_sort, left to right.
    int u, v, i, j;
    u = i = a, v = j = b;
    while(i < m && j < n){
        if(P[u].first < P[v].first){
            for(i = a; i < m; i++){
                if(P[i].first >= P[v].first){ u = i; break; }
                if(P[v].first - P[i].first >= d){ a++; }
                else{
                    d = min(d, dist(P[v], P[i]));
                }
            }
        }else{
            for(j = b; j < n; j++){
                if(P[j].first > P[u].first){ v = j; break; }
                if(P[u].first - P[j].first >= d){ b++; }
                else{
                    d = min(d, dist(P[u], P[j]));
                }
            }
        }
    };
    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;
}