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

const int INF = INT_MAX / 3;

#define REP(i,n) for(int i=0;i<(int)n;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


double EPS = 1e-10;

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) return 0;
	return a + b;
}

struct P {
	double x, y;
	P() {}
	P(double x, double y) : x(x), y(y) {
	}
	P operator +(P p) {
		return P(add(x, p.x), add(y, p.y));
	}
	P operator -(P p) {
		return P(add(x, -p.x), add(y, -p.y));
	}
	P operator *(double d) {
		return P(d*x, d*y);
	}
	double dot(P p) {
		return add(x*p.x, y*p.y);
	}
	double det(P p) {
		return add(x*p.y, -y*p.x);
	}
	void print() {
		printf("%.10lf %.10lf \n", x, y);
		return;
	}
};

double dist(P p1, P p2) {
	double dx = p1.x - p2.x;
	double dy = p1.y - p2.y;
	return sqrt(dx*dx + dy*dy);
}

bool x_asc(const P& left, const P& right) {
	return left.x < right.x;
}

bool y_asc(const P& left, const P& right) {
	return left.y < right.y;
}

void merger(vector<P> &pointList, int start, int m, int end) {
	vector<P> tmp(end - start + 1);
	int i = start;
	int j = m + 1;
	for (int k = 0; k<end - start + 1; k++) {

		if (i == m + 1) {
			tmp[k] = pointList[j];
			j++;
			continue;
		}
		if (j == end + 1) {
			tmp[k] = pointList[i];
			i++;
			continue;
		}
		if (pointList[i].y >= pointList[j].y) {
			tmp[k] = pointList[j];
			j++;
			continue;
		}
		if (pointList[i].y < pointList[j].y) {
			tmp[k] = pointList[i];
			i++;
			continue;
		}
	}

	for (int i = start; i<end + 1; i++) {
		pointList[i] = tmp[i-start];
	}
}

double closestPoint(vector<P> &pointList, int start, int end) {
	int n = end - start + 1;
	int m = (start+end) / 2;
	double center = pointList[m].x;
	double d;
	if (start == end) return INF;
	d = min(closestPoint(pointList, start, m), closestPoint(pointList, m + 1, end));
	merger(pointList, start, m, end);

	vector<P> rangeList;
	for (int i = start; i<end + 1; i++) {
		if (fabs(pointList[i].x - center) >= d) continue;

		for (int j = rangeList.size() - 1; j>-1; j--) {
			double dd = dist(rangeList[j], pointList[i]);
			if (pointList[i].y - rangeList[j].y > d) break;
			d = min(d, dd);
		}
		rangeList.push_back(pointList[i]);

	}
	return d;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<P> pointList(n);
	REP(i, n) {
		scanf("%lf", &pointList[i].x);
		scanf("%lf", &pointList[i].y);
	}

	sort(ALL(pointList), x_asc);

	printf("%.10lf \n", closestPoint(pointList, 0, pointList.size() - 1));
	return 0;
}