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;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-10
#define Vector Point
#define INF 2000000000
#define DOUBLE_INF 1e50
#define sq(x) ((x)*(x))
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)

// Geometry Library
// written by okuraofvegetable

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

struct Point{
	double x,y;
	Point() {}
	Point(double x,double y) : x(x),y(y){}
	Point operator + (Point p){return Point(add(x,p.x),add(y,p.y));}
	Point operator - (Point p){return Point(add(x,-p.x),add(y,-p.y));}
	Point operator * (double d){return Point(x*d,y*d);}
	double dot(Point p){return add(x*p.x,y*p.y);}
	double det(Point p){return add(x*p.y,-y*p.x);}
	double norm(){return sqrt(x*x+y*y);}
	double norm2(){return x*x+y*y;}
	double dist(Point p){return ((*this)-p).norm();}
	double dist2(Point p){return sq(x-p.x)+sq(y-p.y);}
	Point vert(){return Point(y,-x);}
	void dump(const char* msg=""){printf("%s%.12f %.12f\n",msg,x,y);return;}
	
	// following functions for vector operation

	// signed area of triange (0,0) (x,y) (p.x,p.y)
	double area(Point p){
		return (x*p.y-p.x*y)/2.0;
	}
};
// direction a -> b -> c
// verified AOJ CGL_1_C
enum {COUNTER_CLOCKWISE,
		CLOCKWISE,
		ONLINE_BACK,
		ONLINE_FRONT,
		ON_SEGMENT};
int ccw(Point a,Point b,Point c){
	Vector p = b-a;
	Vector q = c-a;
	if(p.det(q)>0.0)return COUNTER_CLOCKWISE; // counter clockwise
	if(p.det(q)<0.0)return CLOCKWISE; // clockwise
	if(p.dot(q)<0.0)return ONLINE_BACK; // c--a--b online_back
	if(p.norm()<q.norm())return ONLINE_FRONT; // a--b--c online_front 
	return ON_SEGMENT;// a--c--b on_segment
}
struct Line{
	Point a,b;
	Line(){}
	Line(Point a,Point b):a(a),b(b){}
	bool on(Point q){
		return (a-q).det(b-q)==0; 
	}
	// folloing 2 functions verified AOJ CGL_2_A
	bool is_parallel(Line l){return (a-b).det(l.a-l.b)==0;}
	bool is_orthogonal(Line l){return (a-b).dot(l.a-l.b)==0;}
	Point intersection(Line l){
		assert(!is_parallel(l));
		return a+(b-a)*((l.b-l.a).det(l.a-a)/(l.b-l.a).det(b-a));
	}
	// projection of p to this line
	// verified AOJ CGL_1_A
	Point projection(Point p){
		return (b-a)*((b-a).dot(p-a)/(b-a).norm2())+a;
	}
	// reflection point of p onto this line
	// verified AOJ CGL_1_B
	Point refl(Point p){
		Point proj = projection(p);
		return p+((proj-p)*2.0);
	}
};
struct Segment{
	Point a,b;
	Segment(){}
	Segment(Point a,Point b):a(a),b(b){}
	Line line(){
		return Line(a,b);
	}
	bool on(Point q){
		return ((a-q).det(b-q)==0&&(a-q).dot(b-q)<=0); 
	}
	// verified AOJ CGL_2_B
	bool is_intersect(Segment s){
		if(line().is_parallel(s.line())){
			if(on(s.a)||on(s.b))return true;
			if(s.on(a)||s.on(b))return true;
			return false;
		}
		Point p = line().intersection(s.line());
		if(on(p)&&s.on(p))return true;
		else return false;
	}
	bool is_intersect(Line l){
		if(line().is_parallel(l)){
			if(l.on(a)||l.on(b))return true;
			else return false;
		}
		Point p = line().intersection(l);
		if(on(p))return true;
		else return false;
	}
	// following 2 distance functions verified AOJ CGL_2_D
	double distance(Point p){
		double res = DOUBLE_INF;
		Point q = line().projection(p);
		if(on(q))res = min(res,p.dist(q));
		res = min(res,min(p.dist(a),p.dist(b)));
		return res;
	}
	double distance(Segment s){
		if(is_intersect(s))return 0.0;
		double res = DOUBLE_INF;
		res = min(res,s.distance(a));
		res = min(res,s.distance(b));
		res = min(res,this->distance(s.a));
		res = min(res,this->distance(s.b));
		return res;
	}
};

// Polygon 

typedef vector<Point> Polygon;
// verified AOJ CGL_3_A
// Polygon don't need to be convex
double area(Polygon& pol){
	vector<Point> vec;
	double res = 0.0;
	int M = pol.size();
	for(int i=0;i<M;i++){
		res += (pol[i]-pol[0]).area(pol[(i+1)%M]-pol[0]);	
	}
	return res;
}
bool is_convex(Polygon& pol){
	int n = pol.size();
	for(int i=0;i<n-1;i++){
		if(ccw(pol[i],pol[i+1],pol[(i+2)%n])==CLOCKWISE){
			return false;
		}
	}
	return true;
}
// vecrified AOJ CGL_3_C
enum {OUT,ON,IN};
int contained(Polygon& pol,Point p){
	int n = pol.size();
	Point outer(1e9,p.y);
	Segment s = Segment(outer,p);
	int cnt = 0;
	for(int i=0;i<n;i++){
		Segment e = Segment(pol[i],pol[(i+1)%n]);
		if(e.on(p))return ON;
		Vector a = pol[i]-p;
		Vector b = pol[(i+1)%n]-p;
		if(a.y>b.y)swap(a,b);
		if(a.y<=0.0&&b.y>0.0){
			if(a.det(b)<0.0)cnt++;
		}
	}
	if((cnt&1)==1)return IN;
	else return OUT;
}
// compare function for convex_hull
// sort points by (x-y) lexicographical order.
// you can change (y-x) order with no change in convex_hull
bool comp(const Point& p,const Point& q){
	if(p.x!=q.x)return p.x<q.x;
	else return p.y<q.y;
}
// Convex hull
// if you want not to contain points on boundary,
// change while(....<=0.0)
// verified AOJ CGL_4_A
Polygon convex_hull(vector<Point> ps){
	sort(all(ps),comp);
	int k = 0;
	int n = ps.size();
	Polygon qs(2*n);
	for(int i=0;i<n;i++){
		while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<0.0)k--;
		qs[k++]=ps[i];
	}
	for(int i=n-2,t=k;i>=0;i--){
		while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<0.0)k--;
		qs[k++]=ps[i];
	}
	qs.resize(k-1);
	return qs;
}
// Caliper method
// verified AOJ CGL_4_B
double convex_diameter(Polygon& cv){
	int i=0,j=0;
	int n = cv.size();
	for(int k=0;k<n;k++){
		if(!comp(cv[i],cv[k]))i=k;
		if(comp(cv[j],cv[k]))j=k;
	}
	int si=i,sj=j;
	double res = 0.0;
	while(i!=sj||j!=si){
		res = max(res,cv[i].dist(cv[j]));
		if((cv[(i+1)%n]-cv[i]).det(cv[(j+1)%n]-cv[j])<0.0)i=(i+1)%n;
		else j=(j+1)%n;
	}
	return res;
}
// Cut conovex polygon by a line and return left polygon
// verified AOJ CGL_4_C
Polygon convex_cut(Polygon& cv,Line l){
	int n = cv.size();
	Polygon left; 
	for(int i=0;i<n;i++){
		Segment e = Segment(cv[i],cv[(i+1)%n]);
		if(ccw(l.a,l.b,cv[i])!=CLOCKWISE)left.pb(cv[i]);
		if(e.is_intersect(l)){
			if(!e.line().is_parallel(l)){
				left.pb(e.line().intersection(l));
			}
		}
	}
	return left;
}
// distance between closest pair
bool comp_y(const Point& p,const Point& q){
	return p.y<q.y;
}
double closest_pair(vector<Point>::iterator a,int n){
	if(n<=1)return DOUBLE_INF;
	int m = n/2;
	double x = (a+m)->x;
	double d = min(closest_pair(a,m),closest_pair(a+m,n-m));
	inplace_merge(a,a+m,a+n,comp_y);
	vector<Point> b;
	for(int i=0;i<n;i++){
		double ax = (a+i)->x;
		double ay = (a+i)->y;
		if(abs(ax-x)>=d)continue;
		for(int j=0;j<b.size();j++){
			double dx = ax-b[b.size()-1-j].x;
			double dy = ay-b[b.size()-1-j].y;
			if(dy>=d)break;
			d = min(d,sqrt(dx*dx+dy*dy));
		}
		b.pb(*(a+i));
	}
	return d;
}
double closest_pair(vector<Point> a){
	sort(all(a),comp);
	return closest_pair(a.begin(),(int)a.size());
}
// for input
Point input_point(){
	Point p;
	cin >> p.x >> p.y;
	return p;
}
Segment input_segment(){
	Point a,b;
	a = input_point();
	b = input_point();
	return Segment(a,b);
}
Line input_line(){
	Point a,b;
	a = input_point();
	b = input_point();
	return Line(a,b);
}

int main(){
	int n;
	cin >> n;
	vector<Point> pol;
	for(int i=0;i<n;i++){
		pol.pb(input_point());
	}
	printf("%.12f",closest_pair(pol));
	return 0;
}