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>

namespace LCY{
	#define double long double
	const double EPS=1e-10;
	const double Pi=acos(-1.0);
	inline int dcmp(double x){if(fabs(x)<EPS)return 0;return (x<0)?-1:1;}
	struct Point{double x,y;Point(double _x=0,double _y=0){x=_x;y=_y;}};
	struct Vector{double x,y;Vector(double _x=0,double _y=0){x=_x;y=_y;}};
	
	Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
	Vector operator * (Vector a,double d){return Vector(a.x*d,a.y*d);}
	Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
	
	inline double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
	inline double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
	inline double norm(Vector a){return dot(a,a);}
	inline double abs(Vector a){return std::sqrt(norm(a));}
	
	struct Line{
		Point p1,p2;
		Line(Point _p1=Point(0,0),Point _p2=Point(0,0)){p1=_p1;p2=_p2;}
	};
	inline bool is_parallel(Line l1,Line l2){return dcmp(cross(l2.p2-l2.p1,l1.p2-l1.p1))==0;}
	inline bool is_vertical(Line l1,Line l2){return dcmp(dot(l2.p2-l2.p1,l1.p2-l1.p1))==0;}
	
	Point project(Line l,Point p){
		Vector base=l.p2-l.p1;
		double r=dot(p-l.p1,base)/norm(base);
		return l.p1+base*r;
	}
	Point reflect(Line l,Point p){
		Point q=project(l,p);
		Vector v=p-q;v.x=-v.x;v.y=-v.y;
		return q+v;
	}
	int ccw(Vector v1,Vector v2){
		if(dcmp(cross(v1,v2))>0)return 1;//COUNTER_CLOCKWISE
		else if(dcmp(cross(v1,v2))<0)return 2;//CLOCKWISE
		else{
			if(dcmp(dot(v1,v2))<0)return 3;//ONLINE_BACK
			else{
				if(dcmp(norm(v1)-norm(v2))<0)return 4;//ONLINE_FRONT
				else return 5;//ON_SEGMENT
			}
		}
	}
	inline bool is_inter(Line l1,Line l2){
		bool flag=1;
		int t1=ccw(l1.p2-l1.p1,l2.p1-l1.p1),t2=ccw(l1.p2-l1.p1,l2.p2-l1.p1);
		if(t1==5 || t2==5) return true;
		else if(t1==t2)return false;
		else if(t1>=3 && t2<=2) return false;
		else if(t1<=2 && t2>=3) return false;
		std::swap(l1,l2);
		t1=ccw(l1.p2-l1.p1,l2.p1-l1.p1),t2=ccw(l1.p2-l1.p1,l2.p2-l1.p1);
		if(t1==5 || t2==5) return true;
		else if(t1==t2)return false;
		else if(t1>=3 && t2<=2) return false;
		else if(t1<=2 && t2>=3) return false;
		return true;
	}
	inline Point line_intersection(Line l1,Line l2){
		if(is_parallel(l1,l2)) return Point(233,233);
		Vector u=l1.p1-l2.p1,v=l1.p2-l1.p1,w=l2.p2-l2.p1;
		double t=cross(w,u)/cross(v,w);
		return l1.p1+v*t;
	}
	inline Point segment_intersection(Line l1,Line l2){
		if(!is_inter(l1,l2)) return Point(233,233);
		return line_intersection(l1,l2);
	}
	inline double line_point_distance(Line l,Point p){
		return std::abs(cross(l.p2-l.p1,p-l.p1))/abs(l.p2-l.p1);
	}
	inline double segment_point_distance(Line l,Point p){
		if(dcmp(dot(l.p2-l.p1,p-l.p1))<0) return abs(p-l.p1);
		if(dcmp(dot(l.p1-l.p2,p-l.p2))<0) return abs(p-l.p2);
		return line_point_distance(l,p);
	}
	inline double segment_distance(Line l1,Line l2){
		#define spd segment_point_distance
		if(is_inter(l1,l2))return 0.0;
		return std::min(std::min(spd(l1,l2.p1),spd(l1,l2.p2)),std::min(spd(l2,l1.p1),spd(l2,l1.p2)));
	}
	double area(std::vector<Point> &Q){
		int n=Q.size();
		double ans=0;
		Point o=Point(0.0,0.0);
		for(int i=0;i<n;++i)ans+=cross(Q[i]-o,Q[(i+1)%n]-o)/2.0;
		return ans;
	}
	double circumference(std::vector<Point> &Q){
		int n=Q.size();
		double ans=0;
		for(int i=0;i<n;++i)ans+=abs(Q[i]-Q[(i+1)%n]);
		return ans;
	}
	bool is_convex(std::vector<Point> &Q){
		int n=Q.size();
		Point o=Point(0.0,0.0);
		for(int i=0;i<n;++i){
			Point lst=Q[(i+n-1)%n],now=Q[i],nxt=Q[(i+1)%n];
			if(ccw(now-lst,nxt-lst)==2)return false;
		}
		return true;
	}
	int in_convex(std::vector<Point> &Q,Point p){
		int n=Q.size();
		Point pp=Point(p.x+100000.0,p.y+Pi*100000.0);
		Vector v=pp-p;
		int cnt=0;
		for(int i=0;i<n;++i){
			Point p1=Q[i],p2=Q[(i+1)%n];
			if(dcmp(cross(p1-p,p2-p))==0 && dcmp(dot(p1-p,p2-p))<=0)return 1;
			Point x=line_intersection(Line(p,pp),Line(p1,p2));
			if(x.x==233 && x.y==233)continue;
			if(ccw(p1-x,p2-x)!=3)continue;
			if(dcmp(x.x-p.x)<0)continue;
			cnt++;
		}
		return (cnt&1)?2:0;
	}
	bool cmp_x(Point a,Point b){return dcmp(a.x-b.x)<0||(dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)<0);}
	bool cmp_y(Point a,Point b){return dcmp(a.y-b.y)<0||(dcmp(a.y-b.y)==0 && dcmp(a.x-b.x)>0);}
	std::vector<Point> get_convex(std::vector<Point> &Q){
		std::vector<Point> sta;
		sort(Q.begin(),Q.end(),cmp_y);
		int n=Q.size();
		for(int i=0;i<n;++i){
			while(sta.size()>=2 && dcmp(cross(sta[sta.size()-1]-sta[sta.size()-2],Q[i]-sta[sta.size()-2]))<0)sta.pop_back();
			sta.push_back(Q[i]);
		}
		int t=sta.size();
		for(int i=n-2;i>=0;--i){
			while(sta.size()>t && dcmp(cross(sta[sta.size()-1]-sta[sta.size()-2],Q[i]-sta[sta.size()-2]))<0)sta.pop_back();
			sta.push_back(Q[i]);
		}
		sta.pop_back();
		return sta;
	}
	double diameter(std::vector<Point> &Q){
		if(Q.size()<=1)return 0;
		if(Q.size()==2)return abs(Q[1]-Q[0]);
		int i=0,j=0,n=Q.size();
		for(int k=0;k<n;++k){
			if(cmp_x(Q[i],Q[k])) i=k;
			if(!cmp_x(Q[j],Q[k])) j=k;
		}
		double ans=0.0;
		int si=i,sj=j;
		while(i!=sj || j!=si){
			ans=std::max(ans,abs(Q[i]-Q[j]));
			if(dcmp(cross(Q[(i+1)%n]-Q[i],Q[(j+1)%n]-Q[j]))>0)j=(j+1)%n;
			else i=(i+1)%n;
		}
		return ans;
	}
	double closest_pair(Point *Q,int n){
		if(n<=1)return 1e9;
		int m=n/2;
		double x=Q[m].x;
		double d=std::min(closest_pair(Q,m),closest_pair(Q+m,n-m));
		std::vector<Point> q;
		int i=0,j=m;
		while(i<m && j<n){
			if(cmp_y(Q[i],Q[j]))q.push_back(Q[i++]);
			else q.push_back(Q[j++]);
		}
		while(i<m)q.push_back(Q[i++]);
		while(j<n)q.push_back(Q[j++]);
		for(int i=0;i<n;++i)Q[i]=q[i];
		q.clear();
		
		for(int i=0;i<n;++i){
			if(dcmp(std::fabs(Q[i].x-x)-d)>=0)continue;
			for(int j=q.size()-1;j>=0;--j){
				d=std::min(d,abs(Q[i]-q[j]));
				if(dcmp(Q[i].y-q[j].y)-d>=0)break;
			}
			q.push_back(Q[i]);
		}
		return d;
	}
}
using namespace LCY;
using namespace std;
Point Q[1000005];
int main(){
	int n;cin>>n;for(int i=0;i<n;++i)cin>>Q[i].x>>Q[i].y;
	sort(Q,Q+n,cmp_x);
	cout<<setiosflags(ios::fixed)<<setprecision(10)<<closest_pair(Q,n)<<endl;
	return 0;
}