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<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<set>
#include<map>
#define re register
#define ll long long
using namespace std;
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch>'9'|| ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
const double eps=1e-10,Pi=acos(-1.0);
struct node{
    double x,y;
    node operator+(node b){return (node){x+b.x,y+b.y};}
    node operator-(node b){return (node){x-b.x,y-b.y};}
    node operator*(double b){return (node){x*b,y*b};}
    double len(){return sqrt(x*x+y*y);}
};
int fh(double a){return fabs(a)<eps?0:a>eps?1:-1;}
node corner(node a,double B){return (node){a.x*cos(B)-a.y*sin(B),a.y*cos(B)+a.x*sin(B)};}
double cross(node a,node b){return a.x*b.y-a.y*b.x;}
double dot(node a,node b){return a.x*b.x+a.y*b.y;}
double distance(node a,node b){return (a-b).len();}
node projection(node p1,node p2,node p){node v=p2-p1;return p1+v*(dot(v,p-p1)/dot(v,v));}
node reflection(node p1,node p2,node p){node P=projection(p1,p2,p);P=P*2-p;return P;}
void Counter_Clockwise(node p1,node p2,node p){
    if(cross(p2-p1,p-p1)>eps){puts("COUNTER_CLOCKWISE");return;}
    if(cross(p2-p1,p-p1)<-eps){puts("CLOCKWISE");return;}
    if(dot(p2-p1,p-p1)<-eps){puts("ONLINE_BACK");return;}
    if(dot(p2-p1,p2-p1)>=dot(p-p1,p2-p1)){puts("ON_SEGMENT");return;}
    puts("ONLINE_FRONT");
}
bool insegment(node A,node B,node p){
    if(fh(cross(B-A,p-A)))return false;
    return ((fh(p.x-A.x)>=0 && fh(B.x-p.x)>=0) || (fh(p.x-A.x)<=0 && fh(B.x-p.x)<=0)) && ((fh(p.y-A.y)>=0 && fh(B.y-p.y)>=0) || (fh(p.y-A.y)<=0 && fh(B.y-p.y)<=0));
}
int parallel(node A1,node A2,node B1,node B2){
    if(!fh(cross(B2-B1,A2-A1)))return 2;
    if(!fh(dot(B2-B1,A2-A1)))return 1;
    return 0;
}
bool intersection(node A1,node A2,node B1,node B2){
    if(!fh(cross(B2-B1,A2-A1))){
        if(insegment(A1,A2,B1) || insegment(A1,A2,B2) || insegment(B1,B2,A1) || insegment(B1,B2,A2))return true;
        return false;
    }
    return fh(cross(A1-B1,B2-B1)*cross(A2-B1,B2-B1))<=0 && (fh(cross(B1-A1,A2-A1)*cross(B2-A1,A2-A1))<=0);
}
node getintersection(node A1,node A2,node B1,node B2){
    node v=A2-A1;
    return A1+v*(cross(B2-B1,B1-A1)/cross(B2-B1,A2-A1));
}
double distance(node A1,node A2,node B1,node B2){
    if(intersection(A1,A2,B1,B2))return 0.0;
    node p;double ans=1e18;
    ans=min(ans,(A1-B1).len());ans=min(ans,(A1-B2).len());ans=min(ans,(A2-B1).len());ans=min(ans,(A2-B2).len());
    p=projection(A1,A2,B1);
    if(insegment(A1,A2,p))ans=min(ans,(B1-p).len());
    p=projection(A1,A2,B2);
    if(insegment(A1,A2,p))ans=min(ans,(B2-p).len());
    p=projection(B1,B2,A1);
    if(insegment(B1,B2,p))ans=min(ans,(A1-p).len());
    p=projection(B1,B2,A2);
    if(insegment(B1,B2,p))ans=min(ans,(A2-p).len());
    return ans;
}
double area(node *p,int n){
    double area=0;
    for(int i=1;i<n;i++){
		area+=cross(p[i],p[i+1]);
	}
    area+=cross(p[n],p[1]);
    return area*0.5;
}
bool is_convex(node *p,int n){
    for(int i=2;i<n;i++)if(cross(p[i]-p[i-1],p[i+1]-p[i-1])<0)return false;
    if(cross(p[n]-p[n-1],p[1]-p[n-1])<0)return false;
    if(cross(p[1]-p[n],p[2]-p[n])<0)return false;
    return true;
}
int inConvex(node O,node *p,int n){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(insegment(p[i],p[(i+1)%n],O))return 1;
        node A=p[i]-O,B=p[(i+1)%n]-O;
        if(A.y>B.y)swap(A,B);
        if(A.y<eps && B.y>eps && cross(A,B)>eps)cnt++;
    }
    return cnt&1?2:0;
}
bool cmp(node a,node b){return a.y<b.y || (!fh(a.y-b.y) && a.x<b.x);}
bool cmp1(node a,node b){return a.x<b.x || (!fh(a.x-b.x) && a.y<b.y);}
bool cmp2(node a,node b){return atan2(a.y,a.x)<atan2(b.y,b.x) || (!fh(atan2(a.y,a.x)-atan2(b.y,b.x)) && a.x>b.x);}
double Diameter(node *p,int n){
    int id=1;double ans=0;
    for(int i=0;i<n;i++){
        node p1=p[i],p2=p[(i+1)%n];
        for(int nxt=(id+1)%n;fh(fabs(cross(p[nxt]-p1,p2-p1))-fabs(cross(p[id]-p1,p2-p1)))>=0;id=nxt,nxt=(nxt+1)%n);
        ans=max(ans,max((p[id]-p1).len(),(p[id]-p2).len()));
    }
    return ans;
}
double cutarea(node *p,int n,node A1,node A2){
	node c[200010];int tot=0;
	for(int i=0;i<n;i++){
		node p1=p[i],p2=p[(i+1)%n];
		node P=getintersection(p1,p2,A1,A2);
		if(insegment(p1,p2,P))c[++tot]=P;
		if(cross(A2-A1,p2-A1)>-eps)c[++tot]=p2;
	}
	return area(c,tot);
}
double Closest_Pair(node *p,int n){
	double ang=(rand()%360+1)*1./360*Pi/2,ans=1e18;
	for(int i=1;i<=n;i++)p[i]=corner(p[i],ang);
	sort(p+1,p+n+1,cmp1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=200 && i+j<=n;j++)
			ans=min(ans,distance(p[i],p[i+j]));
	return ans;
}
node p[400010];int n;
int main(){
    n=gi();
	for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	printf("%.10lf\n",Closest_Pair(p,n));
    return 0;
}