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<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

class Vec{
public:
  double x, y;
  Vec(double x = 0, double y = 0):x(x),y(y){}

  Vec &read(){
    cin >> x >> y;
    return *this;
  }

  void print(){
    printf("%.10lf %.10lf\n", x, y);
  }

  bool operator<(const Vec &other){
    if(x < other.x)return true;
    if(x == other.x && y < other.y)return true;
    return false;
  }
  
  Vec operator+(const Vec &other)
  {
    Vec result = *this;
    result.x += other.x;
    result.y += other.y;
    return result;
  }

  Vec operator-(const Vec &other)
  {
    Vec result = *this;
    result.x -= other.x;
    result.y -= other.y;
    return result;
  }

  Vec operator*(const double &k)
  {
    Vec result = *this;
    result.x *= k;
    result.y *= k;
    return result;
  }

  Vec operator/(const double &k)
  {
    Vec result = *this;
    result.x /= k;
    result.y /= k;
    return result;
  } 
  
  double cross(const Vec &other)
  {
    return x*other.y - y*other.x;
  }

  double dot(const Vec &other){
    return x*other.x + y*other.y;
  }
  
  bool operator==(const Vec &other) const
  {
    return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
  }

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

  double norm2()
  {
    return x*x+y*y;
  }

  Vec standard(){
    Vec result = *this;
    return result/result.norm();
  }
};

//cw:1, ccw:-1, other:0
Int CCW(Vec a, Vec b, Vec c){
  b = b - a;
  c = c - a;
  if(b.cross(c) > EPS)return -1;
  if(b.cross(c) < -EPS)return 1;
  return 0;
}

double dist(Vec a, Vec b){
  return (a-b).norm();
}


bool comp_x(Vec a, Vec b){return a < b;}
bool comp_y(Vec a, Vec b){
  return (a.y < b.y || abs(a.y - b.y) < EPS && a.x < b.x);
}

pair<Vec, Vec> _cp(vector<Vec>::iterator l, vector<Vec>::iterator r){
  int n = r - l;
  if(n <= 3){
    pair<Vec, Vec> res = {*l, *(l+1)};
    for(auto it = l;it < r;it++)
      for(auto jt = it + 1;jt < r;jt++)
	if(dist(*it, *jt) < dist(res.first, res.second))
	  res = {*it, *jt};
    sort(l, r, comp_y);
    return res;
  }
  pair<Vec, Vec> res, res2;
  double minDist;
  auto mid = l + (n / 2);
  double midx = mid->x;
  res = _cp(l, mid);
  minDist = dist(res.first, res.second);
  res2 = _cp(mid, r);
  if(minDist > dist(res2.first, res2.second)){
    minDist = dist(res2.first, res2.second);
    res = res2;
  }
  inplace_merge(l, mid, r, comp_y);
  vector<Vec> center;
  for(auto it = l;it < r;it++)
    if(midx - minDist < it->x && it->x < midx + minDist)
      center.push_back(*it);
  if(center.size() <= 1)return res;
  auto jt = center.begin();
  for(auto it = center.begin();it < center.end();it++){
    while(jt == center.end() || jt > center.begin() && it->y - minDist < jt->y)jt--;
    while(jt < center.end() && it->y + minDist > jt->y){
      if(it != jt && dist(*it, *jt) < minDist){
	res = {*it, *jt};
	minDist = dist(res.first, res.second);	
      }
      jt++;
    }
  }
  return res;  
}

pair<Vec, Vec> closestPair(vector<Vec> &points){
  sort(points.begin(), points.end(), comp_x);
  return _cp(points.begin(), points.end());  
}

int main(){
  int n;
  cin >> n;
  vector<Vec> points(n);
  for(auto &p:points)p.read();
  pair<Vec, Vec> res;
  res = closestPair(points);
  printf("%.10lf\n", dist(res.first, res.second));
  return 0;
}