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 <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

typedef long long ll;


#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)

#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)

class Point {
 public:
  double x, y;

  Point(double x = 0, double y = 0): x(x), y(y) {}

  Point operator + (Point p) { return Point(x+p.x, y+p.y); }
  Point operator - (Point p) { return Point(x-p.x, y-p.y); }
  Point operator * (double a) { return Point(a*x, a*y); }
  Point operator / (double a) { return Point(x/a, y/a); }

  double norm() { return x*x+y*y; }
  double abs() { return sqrt(norm()); }

  bool operator < (const Point &p) const {
    return x != p.x ? x < p.x : y < p.y;
  }

  bool operator == (const Point &p) const {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

typedef Point Vector;
typedef vector <Vector> Polygon;

class Segment {
 public:
  Point p1, p2;

  Segment(Point p1 = Point(), Point p2 = Point()): p1(p1), p2(p2) {}
};

double norm(Vector a) {
  return a.x*a.x+a.y*a.y;
}

double abs(Vector a) {
  return sqrt(norm(a));
}

double getDistance(Point a, Point b) {
  return abs(a-b);
}

// ?????????|a||b|cos
double cross(Vector a, Vector b) {
  return a.x*b.y-a.y*b.x;
}
// ?????????|a||b|sin
double dot(Vector a, Vector b) {
  return a.x*b.x+a.y*b.y;
}

bool compareX(Point a, Point b) {
  return a.x < b.x;
}
bool compareY(Point a, Point b) {
  return a.y < b.y;
}
double bruteForce(Polygon p) {
  double ret = DBL_MAX;
  int n = p.size();
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (abs(p[i]-p[j]) < ret) ret = abs(p[i]-p[j]);
    }
  }
  
  return ret;
}

double stripClosest(Polygon s, double d) {
  double ret = d;
  sort(s.begin(), s.end(), compareY);

  int n = s.size();
  // ?????????????????????6??????????????????????????????
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n && (s[j].y-s[i].y) < ret; j++) {
      if (abs(s[i]-s[j]) < ret) ret = abs(s[i]-s[j]);
    }
  }

  return ret;
}

double closestUtil(Polygon p) {
  int n = p.size();
  if (n <= 3) return bruteForce(p);

  int mid = n/2;
  Point midPoint = p[mid];

  Polygon p1, p2;
  for (int i = 0; i < mid; i++) p1.push_back(p[i]);
  for (int i = mid; i < n; i++) p2.push_back(p[i]);
  double dl = closestUtil(p1);
  double dr = closestUtil(p2);

  double d = min(dl, dr);

  Polygon s;
  for (int i = 0; i < n; i++) {
    if (abs(p[i].x-midPoint.x) < d) {
      s.push_back(p[i]);
    }
  }

  return min(d, stripClosest(s, d));
}

double closest(Polygon p) {
  sort(p.begin(), p.end(), compareX);

  return closestUtil(p);
}

int main() {
  int n;
  cin >> n;
  Polygon poly;
  for (int i = 0; i < n; i++) {
    double x, y;
    cin >> x >> y;
    poly.push_back(Vector(x, y));
  }
  cout << fixed << setprecision(20) << closest(poly) << endl;
}