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:
//finds the pair with minimum distance between them
// verified against CGL_5_A AOJ

#include <bits/stdc++.h>
using namespace std;

struct Point {
  double x, y;
};

Point result1, result2;
double bestDistance;

double euclideanDistance(Point a, Point b)  {
  double X = a.x - b.x, Y = a.y - b.y;
  return sqrt(X * X + Y * Y);
}

// comparison first done by y coordinate, then by x coordinate
bool lesser(Point a, Point b) {
  if(a.y < b.y) {
    return true;
  }
  if(a.y > b.y) {
    return false;
  }
  return a.x < b.x;
}

void merge(Point* a, Point* aux, int lo, int mid, int hi)   {
  int i, j, k;
  for (k = lo; k <= hi; k++) {
    aux[k] = a[k];
  }

  i = lo; j = mid + 1; k = lo;
  while(i <= mid && j <= hi) {
    a[k++] = lesser(aux[i], aux[j]) ? aux[i++] : aux[j++];      
  }

  // Copy the rest of the left side of the array into the target array
  while (i <= mid) {
    a[k++] = aux[i++];
  }
}

double closestPair(Point* pointsByX, Point* pointsByY, Point* aux, int lo, int hi) {
  if(hi <= lo) {
    return numeric_limits<double>::infinity();
  }

  int mid = lo + (hi - lo) / 2;
  double delta = closestPair(pointsByX, pointsByY, aux, lo, mid);
  double dist = closestPair(pointsByX, pointsByY, aux, mid + 1, hi);
  if (dist < delta) {
    delta = dist;
  }

  merge(pointsByY, aux, lo, mid, hi);

  int m = 0, i, j;
  for (i = lo; i <= hi; i++) {
    if (abs(pointsByY[i].x - pointsByX[mid].x) < delta) {
      aux[m++] = pointsByY[i];
    }
  }
  double distance;
  for(i = 0; i < m; i++) {
    for(j = i + 1; j < m && (aux[j].y - aux[i].y < delta); j++) {
      distance = euclideanDistance(aux[i], aux[j]);
      if (distance < delta) {
        delta = distance;
        if (delta < bestDistance) {
          bestDistance = delta;
          result1 = aux[i];
          result2 = aux[j];
        }
      }
    }
  }
  return delta;
}

bool comp(Point a, Point b)  {
    return a.x < b.x;
}

int main()  {

  int n, i;
  Point *points, *pointsByY, *aux;

  scanf("%d", &n);    //Enter the number of points in the plane
  points = new Point[n];
  for (i = 0; i < n; i++) { // Enter n points (x, y)
    scanf("%lf %lf", &points[i].x, &points[i].y);
  }

  if (n <= 1) return 0;

  sort(points, points + n, comp);
  pointsByY = new Point[n];
  for (i = 0; i < n; i++) {
    pointsByY[i] = points[i];
  }
  aux = new Point[n];

  bestDistance = numeric_limits<double>::infinity();
  closestPair(points, pointsByY, aux, 0, n - 1);
  //printf("%lf %lf\n", result1.x, result1.y);
  //printf("%lf %lf\n", result2.x, result2.y);
  printf("%.12lf\n", bestDistance);
  return 0;
}