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 <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
typedef long long ll;
int sgn(double x){
    if(fabs(x)<eps){
        return 0;
    }
    if(x<0){
        return -1;
    }else{
        return 1;
    }
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
}p[100005];
int a[100005];   //暂存点的坐标
bool cmpx(const Point &a,const Point &b){
    return a.x<b.x;
}
bool cmpy(int a,int b){
    return p[a].y<p[b].y;
}
double closest(int low,int high){
    if(low+1 == high){    //只有两个点
        return p[low].distance(p[high]);
    }
    if(low+2 == high){   //三个点也好算
        return min(p[low].distance(p[high]),min(p[low].distance(p[low+1]),p[low+1].distance(p[high])));
    }
    int mid = (low+high)>>1;
    double ans = min(closest(low,mid),closest(mid+1,high));
    int i,j,cnt = 0;
    for(int i = low;i <= high;++i ){
        if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans){
            a[cnt++] = i;
        }
    }
    sort(a,a+cnt,cmpy);
    for(int i = 0;i < cnt;++i ){
        for(int j = i+1;j < cnt;++j ){
            if(p[a[j]].y-p[a[i]].y>=ans){
                break;
            }
            ans = min(ans,p[a[i]].distance(p[a[j]]));
        }
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;++i ){
        p[i].input();
    }
    sort(p,p+n,cmpx);
    printf("%.8f\n",closest(0,n-1));
    return 0;
}