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 <cstdio>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAXSIZE = 1e5+7;
const int INF = 0x3fffffff;
struct point 
{
	double x, y;
};
typedef point Point;
int keep[MAXSIZE];
Point dots[MAXSIZE];
bool comxy(Point a, Point b){
	if(a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}
bool cmpy(int a, int b){
	return dots[a].y < dots[b].y;
}
double distent(int a, int b){
	return sqrt((dots[a].x - dots[b].x) * (dots[a].x - dots[b].x) + (dots[a].y - dots[b].y) * (dots[a].y - dots[b].y));
}
double divSolve(int left, int right){
	double dis = INF;
	if(left == right)
		return dis;
	if(left + 1 == right)
		return distent(left, right);
	int mid = (left + right) >> 1;
	double wayf = divSolve(left, mid);
	double ways = divSolve(mid + 1, right);
	dis = min(wayf, ways);
	int k = 0;
	for(int i = left; i <= right; i++){
		if(fabs(dots[mid].x - dots[i].x) <= dis){
			keep[k++] = i;
		}
	}
	sort(keep,keep+k,cmpy);
	for(int i = 0; i < k; i++){
		for(int j = i+1; j < k && (dots[keep[j]].y - dots[keep[i]].y) < dis; j++){
			dis = min(dis, distent(keep[j],keep[i]));
		}
	}
	return dis;
}
int main(){
	int n;
	while(~scanf("%d",&n)){
		memset(keep,0,sizeof(keep));
		for(int i = 0; i < n; i++){
			scanf("%lf %lf",&dots[i].x, &dots[i].y);
		}
		sort(dots, dots+n, comxy);
		double res = divSolve(0,n-1);
		printf("%0.10lf\n", res);
	}
	return 0;
}