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 <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int M = 100007;
const double INF = 1e50;

struct PT {double x, y;};
bool cmp(PT a, PT b)
{
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cmp_y(PT a, PT b)
{
	return a.y < b.y;
}
PT a[M];
double Dis(PT a, PT b)
{
	double x = b.x - a.x;
	double y = b.y - a.y;
	return sqrt(x*x + y*y);
}

double Closest_pair(PT *a, int n)
{
	if (n == 1)  return INF;
	
	double d = INF;
	int m = n/2;
	d = min(Closest_pair(a, m), Closest_pair(a+m, n-m));
	
	// 接下来讨论在中间的情况
	double mx = a[m].x;
	vector<PT> b;
	for (int i = m; i >= 0; --i)
	{
		if (fabs(a[i].x - mx) > d) 	break;
		else 						b.push_back(a[i]);
	}
	for (int i = m+1; i < n; ++i)
	{
		if (fabs(a[i].x - mx) > d)	break;
		else 						b.push_back(a[i]);
	}
	sort(b.begin(), b.end(), cmp_y);
	
	for (int i = 0; i < b.size(); ++i)
	{
		for (int j = i+1; fabs(b[j].y - b[i].y) < d && j < b.size(); ++j)
		{
			double dis = Dis(b[i], b[j]);
			if (dis < d) d = dis;
		}
	}
	
	
	return d;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%lg %lf", &a[i].x, &a[i].y);
	
	sort(a, a+n, cmp);
	printf("%7f", Closest_pair(a, n));
	return 0;
}