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 <bits/stdc++.h>
using namespace std;
/*******************??????********************/
const double EPS = 1e-8;
const double INF = 1e12;
#define X real()
#define Y imag()
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
#define diff(P, i) (next(P, i) - curr(P, i))
#define EQ(a,b) (abs((a)-(b)) < EPS)

typedef complex<double> P;
namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
	bool operator == (const P& a, const P& b) {
		return abs(a-b) < EPS;
	}
}
double cross(const P& a, const P& b) {//??????
	return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {//??????
	return real(conj(a)*b);
}

struct L : public vector<P> {//??????
	L(const P &a, const P &b) {
		push_back(a); push_back(b);
	}
};

typedef vector<P> G;
struct C {//???
	P p; double r;
	C(const P &p, double r) : p(p), r(r) { }
};

int ccw(P a, P b, P c) {//??????????????????
	b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

bool intersectLL(const L& l,const L& m){
	//non-parallel || sameline
	return abs(cross(l[1]-l[0],m[1]-m[0])) > EPS || abs(cross(l[1]-l[0],m[0]-l[0])) < EPS;
}
bool intersectLS(const L& l,const L& s){
	// s[0] is left of l,s[1] is right of l
	return cross(l[1]-l[0],s[0]-l[0]) * cross(l[1]-l[0],s[1]-l[0]) < EPS;
}
bool intersectSS(const L &s, const L &t) {
	return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
		ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
bool intersectLP(const L& l,const P& p){
	return abs(cross(l[1]-p,l[0]-p)) < EPS;
}
bool intersectSP(const L& s,const P& p){
	return abs(s[0]-p)+abs(s[1]-p) - abs(s[1]-s[0]) < EPS;// triangle inequality
}
// ??´???????????????
bool orthogonalLL(const L &l1, const L &l2){
	return (dot(l1[0]-l1[1], l2[0]-l2[1]) <= EPS && dot(l1[0]-l1[1], l2[0]-l2[1]) >= -EPS);
}
// ??????????????????
bool parallelLL(const L &l1, const L &l2){
	return (cross(l1[0]-l1[1], l2[0]-l2[1]) <= EPS && cross(l1[0]-l1[1], l2[0]-l2[1]) >= -EPS);
}
// p??????l?????????????????????????????????
P projection(const L& l,const P& p){
	double t = dot(p-l[0],l[0]-l[1]) / norm(l[0]-l[1]);
	return l[0] + t*(l[0]-l[1]);
}
// l???????§°?????¨????????????p??¨???????§°?????????????????????
P reflection(const L& l,const P& p){
	return p + 2. * (projection(l,p) - p);
}
double distancePP(const P &a, const P &b){
	return abs(a - b);
}
double distanceSP(const L &s, const P &p) {
	const P r = projection(s, p);
	if (intersectSP(s, r)) return abs(r - p);
	return min(abs(s[0] - p), abs(s[1] - p));
}
double distanceLP(const L& l,const P& p){
	return abs(p - projection(l,p));
}
double distanceLL(const L& l,const L& m){
	return intersectLL(l,m) ? 0 : distanceLP(l,m[0]);
}
double distanceLS(const L& l,const L& s){
	if(intersectLS(l,s)) return 0;
	return min(distanceLP(l, s[0]),distanceLP(l, s[1]));
}
double distanceSS(const L &s, const L &t) {
	if (intersectSS(s, t)) return 0;
	return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
		min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
// ??????
P crosspointLL(const L &l, const L &m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
	if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
	return m[0] + B / A * (m[1] - m[0]);
}
// ????§???¢?????¢???
double area(const G &g){
	double A = 0.0;
	for(int i=0;i<g.size();i++)
		A += cross(g[i],g[(i+1)%g.size()]);
	return A / 2.0;
}
// ?????????
bool isconvex(const G &g){
	for(int i=0;i<g.size();i++){
		if(ccw(g[(i-1+g.size())%g.size()], g[i], g[(i+1)%g.size()]) == -1)return false;
	}
	return true;
}
// convex full
G convex_full(G &ps){
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	G ch(2*n);
	for (int i = 0; i < n; ch[k++] = ps[i++])//lower-hull
		while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
	for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--])//upper-hull
		while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
	ch.resize(k-1);
	return ch;
}
// ????§???¢?????´??????????????????????????¢
double convex_diameter(const G &pt){
	const int n = pt.size();
	int is = 0, js = 0;
	for(int i=1;i<n;i++){
		if(imag(pt[i]) > imag(pt[is])) is = i;
		if(imag(pt[i]) < imag(pt[js])) js = i;
	}
	double maxd = norm(pt[is]-pt[js]);
	int i, maxi, j, maxj;
	i = maxi = is;
	j = maxj = js;
	do {
		if (cross(diff(pt,i), diff(pt,j)) >= 0) j = (j+1) % n;
		else i = (i+1) % n;
		if (norm(pt[i]-pt[j]) > maxd) {
			maxd = norm(pt[i]-pt[j]);
			maxi = i; maxj = j;
	    }
	} while (i != is || j != js);
	return sqrt(maxd); /* farthest pair is (maxi, maxj). */
}
// ???????§???¢?????????
// ???????§???¢?????´?????§???????????????????????´???????????????
G convex_cut(const G &g, const L &l){
	G Q;
	for(int i=0;i<g.size();i++){
		P A = curr(g, i), B = next(g, i);
		if(ccw(l[0], l[1], A) != -1) Q.push_back(A);
	if(ccw(l[0], l[1], A) * ccw(l[0], l[1], B) < 0) Q.push_back(crosspointLL(L(A, B), l));
	}
	return Q;
}
// ??????????????§??????
bool is_convex(G &g){
	G cf = convex_full(g);
	if(cf.size() == g.size())return true;
	return false;
}
// ??????????§???¢????????????
enum{ OUT, ON, IN};
int contains(const G &g, const P &p){
	bool in = false;
	for(int i=0;i<g.size();i++){
		P a = g[i] - p, b = g[(i+1)%g.size()] - p;
		if( imag(a) > imag(b) )swap(a, b);
		if( imag(a) <= 0 && 0 < imag(b) )
			if( cross(a, b) < 0) in = !in;
		if( cross(a, b) == 0 && dot(a, b) <= 0 )return ON;
	}
	return in ? IN : OUT;
}
// ????????????
double compare_x(const P &a, const P &b){
	return a.X != b.X ? a.X < b.X : a.Y < b.Y;
}
double compare_y(const P &a, const P &b){
	return a.Y != b.Y ? a.Y < b.Y : a.X < b.X;
}
double convex_radius(P *a, int n){
	if(n <= 1) return INF;
	int m = n / 2;
	double x = a[m].X;
	double d = min(convex_radius(a, m), convex_radius(a + m, n - m));
	sort(a, a + n, compare_y);
	vector<P> b;
	for(int i = 0; i < n; ++i){
		if(fabs(a[i].X - x) >= d) continue;
		for(int j = 0; j < (int)b.size(); ++j){
			P p0 = a[i], p1 = b[(int)(b.size()) - j - 1];
			if(p0.Y - p1.Y >= d) break;
			d = min(d, abs(p0 - p1));
		}
		b.push_back(a[i]);
	}
	return d;
}
int main(void){
	int n;
	cin >> n;
	G g(n);
	for(int i=0;i<n;i++){
		double x,y;
		cin >> x >> y;
		g[i] = P(x,y);
	}
	sort(g.begin(),g.end(),compare_x);
	cout << fixed << setprecision(20) << convex_radius(&g[0],n) << endl;
	return 0;
}