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-9;
struct dot{
	double x,y;
	double len(){return sqrt(x*x+y*y);}
	dot(double a=0.0,double b=0.0){x=a,y=b;}
	dot operator +(const dot&b)const {return dot(x+b.x,y+b.y);}
	dot operator -(const dot&b)const {return dot(x-b.x,y-b.y);}
	dot operator *(const double&z)const {return dot(x*z,y*z);}
	bool operator <(const dot&b)const {return (y<b.y)||(y==b.y&&x<b.x);}
	bool operator ==(const dot&b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}	
	bool operator !=(const dot&b)const {return fabs(x-b.x)>=eps||fabs(y-b.y)>=eps;}
	void read(){scanf("%lf%lf",&x,&y);} 
};
struct line{
	dot x1,x2;
	void read(){x1.read();x2.read();};
	line(dot a=dot(0.0,0.0),dot b=dot(0.0,0.0)){x1=a,x2=b;} 
	dot getdot(){return x2-x1;}
};
double chaji(dot x,dot y){
	return x.x*y.y-x.y*y.x;
}
double neiji(dot x,dot y){
	return x.x*y.x+x.y*y.y;
}
double cos(dot x,dot y){
	if (!x.len()||!y.len())return 0;
	return neiji(x,y)/x.len()/y.len();
}
dot Projection(dot x,line y){//求x关于直线y的投影点（垂足） 
	y.x2=y.x2-y.x1;
	x=x-y.x1;
	double len=cos(x,y.x2)*x.len()/y.x2.len();
	y.x2=y.x2*len;
	return y.x2+y.x1;
}
dot Reflection(dot x,line y){//求x关于直线y的对称点 
	dot z=Projection(x,y);
	return z*2-x;
}
int Counter_Clockwise(dot x,line y){//求两个向量的五种关系 
	x=x-y.x1;y.x2=y.x2-y.x1;
	if (chaji(y.x2,x)!=0){
		if (chaji(y.x2,x)>0)return 1;
		return 2;
	} 
	if (fabs(cos(x,y.x2)+1)<eps)return 3;
	if (x.len()>y.x2.len())return 4;
	return 5;
} 
int Parallel_Orthogonal(line x,line y){//求两个直线是垂直还是平行还是其他 
	dot a=x.getdot(),b=y.getdot();
	if (chaji(a,b)==0)return 2;
	if (neiji(a,b)==0)return 1;
	return 0;
}
int Intersection(line x,line y){//求两条线段是否相交 
	int Minx1=min(x.x1.x,x.x2.x),Maxx1=max(x.x1.x,x.x2.x);
	int Minx2=min(y.x1.x,y.x2.x),Maxx2=max(y.x1.x,y.x2.x);
	int Miny1=min(x.x1.y,x.x2.y),Maxy1=max(x.x1.y,x.x2.y);
	int Miny2=min(y.x1.y,y.x2.y),Maxy2=max(y.x1.y,y.x2.y);
	if (Minx1>Maxx2||Minx2>Maxx1)return 0;
	if (Miny1>Maxy2||Miny2>Maxy1)return 0;
	if (chaji(x.getdot(),y.x1-x.x1)*chaji(x.getdot(),y.x2-x.x1)>0)return 0;
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
int Intersection2(line x,line y){//求线段和直线是否相交 
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
dot CrossPoint(line x,line y){//求两条线段的交点 
	if (fabs(cos(x.getdot(),y.getdot())-1)<eps||fabs(cos(x.getdot(),y.getdot())+1)<eps){
		if (x.x1<x.x2)swap(x.x1,x.x2);
		if (y.x1<y.x2)swap(y.x1,y.x2);
		if (x.x2<y.x2)return y.x2;
		else return x.x2;
	}
	else {
		if (x.x2.x-x.x1.x==0){
			double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
			return dot(x.x2.x,x.x2.x*k2+b2);
		}
		if (y.x2.x-y.x1.x==0){
			double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
			return dot(y.x2.x,y.x2.x*k1+b1);			
		}
		double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
		double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
		dot ans;
		ans.x=(b2-b1)/(k1-k2);ans.y=ans.x*k1+b1;
		return ans;
	}
} 
double Dis(dot x,dot y){//点到点的距离 
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dist(line x,dot y){//点到线段的距离 
	dot P=Projection(y,x);
	double k=neiji(x.getdot(),P-x.x1)/neiji(x.getdot(),x.getdot());
	if (k<=0)return Dis(x.x1,y);
	if (k>=1)return Dis(x.x2,y);
	return Dis(y,P);
}
double Distance(line x,line y){//线段之间距离 
	return min(min(dist(x,y.x1),dist(x,y.x2)),min(dist(y,x.x1),dist(y,x.x2)));
}
struct polygon{
	vector<dot > A;
	double S(){//多边形面积
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=chaji(A[i],A[i+1])/2;
		if (A.size()>1)ans+=chaji(A[A.size()-1],A[0])/2;
		return ans;		
	}
	double C(){//多边形周长 
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=Dis(A[i],A[i+1]);
		if (A.size()>1)ans+=Dis(A[A.size()-1],A[0]);
		return ans;
	}
	void read(){
		int n;scanf("%d",&n);A.resize(n);
		for (int i=0;i<n;i++)A[i].read();
	}
	int Is_Convex(){//是否是凸多边形 
		for (int i=0;i<A.size();i++)
			if (chaji(A[(i+1)%A.size()]-A[i],A[(i+2)%A.size()]-A[(i+1)%A.size()])<0)
				return 0;
		return 1;
	}
}G;
int PolygonPointContainment(polygon G,dot x){//射线和多边形的关系
	for (int i=0;i<G.A.size();i++)
		if (Counter_Clockwise(x,line(G.A[i],G.A[(i+1)%G.A.size()]))==5)return 1;
	for (int i=0;i<G.A.size();i++)
		if (x==G.A[i])return 1;
	double k=sqrt(2)+1,b=x.y-x.x*k;
	dot x2=dot(-1000000000,-1000000000*k+b);line R=line(x,x2);
	int ans=0;
	for (int i=0;i<G.A.size();i++)
		if (Intersection(R,line(G.A[i],G.A[(i+1)%G.A.size()])))ans++;
	if (ans&1)return 2;
	return 0;	
}
int isclock(dot x,dot y,dot z){//是否顺时针 
	return chaji(z-x,y-x)<0;
}
polygon Convex_Hull(polygon G){//求凸包 
	polygon ans1,ans2;
	sort(G.A.begin(),G.A.end());
	ans1.A.push_back(G.A[0]);ans1.A.push_back(G.A[1]);
	for (int i=2;i<G.A.size();i++){
		while (ans1.A.size()>=2&&isclock(ans1.A[ans1.A.size()-2],ans1.A[ans1.A.size()-1],G.A[i]))
			ans1.A.pop_back();
		ans1.A.push_back(G.A[i]);	
	}
	ans2.A.push_back(G.A[G.A.size()-1]);ans2.A.push_back(G.A[G.A.size()-2]);
	for (int i=G.A.size()-3;i>=0;i--){
		while (ans2.A.size()>=2&&isclock(ans2.A[ans2.A.size()-2],ans2.A[ans2.A.size()-1],G.A[i]))
			ans2.A.pop_back();
		ans2.A.push_back(G.A[i]);		
	}
	for (int i=1;i<ans2.A.size()-1;i++)ans1.A.push_back(ans2.A[i]);
	return ans1;
}
double DiameterofaConvexPolygon(polygon G){//求直径 
	int l=0,r=1,flag=1;
	double ans=Dis(G.A[0],G.A[1]);
	while (l!=0||flag){
		flag=0;
		while (Dis(G.A[l],G.A[r])<=Dis(G.A[l],G.A[(r+1)%G.A.size()])){
			r=(r+1)%G.A.size();
			ans=max(ans,Dis(G.A[l],G.A[r]));
		}
		l=(l+1)%G.A.size();
		ans=max(ans,Dis(G.A[l],G.A[r]));
	}
	return ans;
}
double Convex_Cut(polygon G,line x){//求多边形在线的左边的部分 
	polygon ans;line y=x;
	for (int i=0;i<G.A.size();i++){
		if (chaji(y.x2-y.x1,G.A[i]-y.x1)>=0)ans.A.push_back(G.A[i]);
		if (Intersection2(line(G.A[i],G.A[(i+1)%G.A.size()]),y))
			ans.A.push_back(CrossPoint(line(G.A[i],G.A[(i+1)%G.A.size()]),y));	
	}
	return ans.S();
}
int cmp2(int x,int y){
	return G.A[x]<G.A[y];
}
double ClosestPair(int l,int r){//求平面最近点对 
    double d=1e20;vector<int > ans;
    if (l==r)return d;
    if (l+1==r)return Dis(G.A[l],G.A[r]);
    int mid=(l+r)/2; 
    double d1=ClosestPair(l,mid),d2=ClosestPair(mid+1,r);
    d=min(d1,d2);
    for (int i=l;i<=r;i++)
        if (fabs(G.A[mid].x-G.A[i].x)<=d)ans.push_back(i);
    sort(ans.begin(),ans.end(),cmp2);
    for (int i=0;i<ans.size();i++)
        for (int j=i+1;j<ans.size()&&G.A[ans[j]].y-G.A[ans[i]].y<d;j++)
			d=min(d,Dis(G.A[ans[i]],G.A[ans[j]]));
    return d;
}
int cmp(dot x,dot y){
	return x.x<y.x||(x.x==y.x&&x.y<y.y);
}
int main(){
	G.read();
	sort(G.A.begin(),G.A.end(),cmp);
    printf("%.10lf\n",ClosestPair(0,G.A.size()-1));
  	return 0;
}