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;

//point
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 cmp_y(const P &a, const P &b){
		return a.imag() != b.imag() ? a.imag() < b.imag() : a.real() < b.real();
	}
}
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);
}
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;								  // a--c--b on line
}

// line
struct L : public vector<P> {
	L(const P& a, const P& b) {
		push_back(a); push_back(b);
	}
};
P crosspoint(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]);
}

// polygon
typedef vector<P> G;

P extreme(const vector<P> &po, const L &l) {
  int k = 0;
  for (int i = 1; i < po.size(); ++i)
    if (dot(po[i], l[1]-l[0]) > dot(po[k], l[1]-l[0])) k = i;
  return po[k];
}

enum { OUT, ON, IN };
int contains(const G& po, const P& p) {
  bool in = false;
  for (int i = 0; i < po.size(); ++i) {
  	P a = po[i] - p, b = po[(i+1)%po.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 area2(const G& po) {
	double A = 0;
  	for (int i = 0; i < po.size(); ++i) 
    	A += cross(po[i], po[(i+1)%po.size()]);
	//????????????????????????????????¨????????????
  	return A/2;
}

bool isconvex(const G &p) {
	int n = p.size();
	if(cross(p[0]-p[n-1],p[n-2]-p[n-1]) < 0) return false;
	for(int i = 1; i < n-1; ++i) {
		if(cross(p[i+1]-p[i],p[i-1]-p[i]) < 0) return false;
	}
	return true;

}

G convex_hull(G ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end(), cmp_y);
  G r(2*n);
  for(int i = 0; i < n; i++){
    while(k>1 && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  for(int i = n-2, t = k; i >= 0; i--){
    while(k>t && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  r.resize(k-1);
  return r;
}

// caliper
double convex_diameter(const G &pt) {
	const int n = pt.size();
	if(n <= 1) return 0;
	if(n == 2) return abs(pt[0]-pt[1]);
	
	int i = 0, j = 0;
	for(int k = 0; k < n; ++k){
		if(!(pt[i] < pt[k])) i = k;
		if(pt[j] < pt[k]) j = k;
	}
   
	double res = 0;
	int si = i, sj = j;
	while(i != sj || j != si) {
		res = max(res, abs(pt[i]-pt[j]));
		if(cross(pt[(i+1)%n]-pt[i],pt[(j+1)%n]-pt[j]) < 0) i = (i+1)%n;
		else j = (j+1)%n;
	}
	return res;
}

// po???l??§?????????????????´???????????????
G convex_cut(const G& po, const L& l) {
  G Q;
  for (int i = 0; i < po.size(); ++i) {
  	P A = po[i], B = po[(i+1)%po.size()];
    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(crosspoint(L(A, B), l));
  	}
  }
  return Q;
}

//?????????????????¢
double closestPair(G p, int flag=1) {
	if(flag) sort(p.begin(), p.end());
	int n = p.size(), s = 0, m=n/2;
	if(n<=1) return INF;
	G b(begin(p), begin(p)+m), c(begin(p)+m, end(p)), e;
	double x = p[m].real(), d=min(closestPair(b, 0), closestPair(c, 0));
	sort(p.begin(), p.end(), cmp_y);
	for(int i=0; i<n; ++i) {
		if(abs(real(p[i])-x) >= d) continue;
		for(int j=0; j<e.size(); ++j) {
			if(imag(p[i]-e[e.size()-1-j]) >= d) break;
			d = min(d, abs(p[i]-e[e.size()-1-j]));
		}
		e.push_back(p[i]);
	}
	return d;
}

int main() {
	int n;
	cin >> n;
	G po;
	for(int i=0; i<n; ++i) {
		double x, y;
		cin >> x >> y;
		P p(x, y);
		po.push_back(p);
	}
	cout << fixed << setprecision(15) << closestPair(po) << endl;
}