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 <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
const int N = 100010 + 5;
typedef double db;
const db eps = 1e-8;
const db INF = 1e20;
struct Point{
    db x, y;
    void input(){
        scanf("%lf%lf", &x, &y);
    }
}p[N];
db dist(Point a, Point b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Point tmpt[N];
bool cmpx(Point a, Point b){
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cmpy(Point a, Point b){
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}
db closest_pair(int left, int right){
    db d = inf;
    if(left == right) return d;
    if(left == right - 1) return dist(p[left], p[right]);
    int mid = left + right >> 1;
    db d1 = closest_pair(left, mid);
    db d2 = closest_pair(mid+1, right);
    d = min(d1, d2);
    int cnt = 0;
    for(int i=left;i<=right;i++){
        if(fabs(p[mid].x - p[i].x) <= d){
            tmpt[++cnt] = p[i];
        }
    }
    sort(tmpt + 1, tmpt + cnt + 1, cmpy);
    for(int i=1;i<=cnt;i++)
        for(int j=i + 1;j<=cnt && tmpt[j].y - tmpt[i].y < d;j++)
            d = min(d, dist(tmpt[i], tmpt[j]));
    return d;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) p[i].input();
    sort(p+1, p+1+n, cmpx);
    printf("%.8f\n", closest_pair(1, n));

    return 0;
}