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<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const double INF = 1000001;
const double eps = 1e-10;
clock_t START, END;

//basic defitition
struct Point {
	int i;
	double x, y;
	Point(double x = 0, double y = 0, int i = 0) :x(x), y(y), i(i) {}
	bool operator < (const Point& rhs) const {
		return x < rhs.x;
	}
};
int dcmp(double x) {
	if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
double Distance(Point P, Point Q) {
	double _ans = sqrt(fabs(P.x - Q.x) * fabs(P.x - Q.x) + fabs(P.y - Q.y) * fabs(P.y - Q.y));
	return _ans;
}

double shortestdistance = 0;
vector<Point> S_X, S_Y;

double divide(int L, int R) {
	if (R - L <= 2) {
		for (int i = L; i < R; i++) {
			for (int j = i + 1; j <= R; j++) {
				if (S_Y[i].y > S_Y[j].y) {
					swap(S_Y[i].x, S_Y[j].x);
					swap(S_Y[i].y, S_Y[j].y);
				}
			}
		}
		switch (R - L) {
		case 2: return min(Distance(S_X[L + 1], S_X[R]), min(Distance(S_X[L], S_X[R]), Distance(S_X[L], S_X[L + 1]))); break;
		case 1: return Distance(S_X[L], S_X[R]); break;
		default: return INF;
		}
	}
	else {
		int M = L + (R - L) / 2;
		double _min = min(divide(L, M), divide(M + 1, R));
		double l = (R - L) % 2 ? (S_X[M].x + S_X[M + 1].x) / 2 : S_X[M].x;
		vector<Point> Y, T;
		int i, j;
		for (i = L, j = M + 1; i <= M && j <= R;) {
			if (S_Y[i].y <= S_Y[j].y) {
				if (dcmp(S_Y[i].x - l + _min) >= 0 && dcmp(l + _min - S_Y[i].x) >= 0)
					Y.push_back(S_Y[i]);
				T.push_back(S_Y[i]);
				i++;
			}
			else {
				if (dcmp(S_Y[j].x - l + _min) >= 0 && dcmp(l + _min - S_Y[j].x) >= 0)
					Y.push_back(S_Y[j]);
				T.push_back(S_Y[j]);
				j++;
			}
		}
		while (i <= M) {
			if (dcmp(S_Y[i].x - l + _min) >= 0 && dcmp(l + _min - S_Y[i].x) >= 0)
				Y.push_back(S_Y[i]);
			T.push_back(S_Y[i++]);
		}
		while (j <= R) {
			if (dcmp(S_Y[j].x - l + _min) >= 0 && dcmp(l + _min - S_Y[j].x) >= 0)
				Y.push_back(S_Y[j]);
			T.push_back(S_Y[j++]);
		}
		for (i = L, j = 0; i <= R; i++, j++)
			S_Y[i] = T[j];
		int N = Y.size();
		for (i = 0; i < N; i++) {
			for (j = i + 1; j <= i + 6 && j < N; j++) {
				_min = min(_min, Distance(Y[i], Y[j]));
			}
		}
		Y.clear();
		//printf("%.10lf\n", _min);
		return _min;
	}
}

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in19.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}
	int n;
	double x, y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &x, &y);
		S_X.push_back(Point(x, y, i));
		S_Y.push_back(Point(x, y, i));
	}
	sort(S_X.begin(), S_X.end());
	sort(S_Y.begin(), S_Y.end());
	double ans = divide(0, n - 1);
	printf("%.6lf\n", ans);
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}