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 <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)

const double eps = 1e-10;
const double inf = 1e+10;
const double pi = acos(-1.0);

struct Point {
  double x, y;
  Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}  
  double norm() {return sqrt(x*x + y*y);}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
double operator * (const Point &p, const Point q) {return p.x * q.x + p.y * q.y;}
bool operator == (const Point &p, const Point &q) {return (abs(p.x - q.x) < eps && abs(p.y - q.y) < eps);}
bool operator != (const Point &p, const Point &q) {return !(p == q);}
double cross(const Point &p, const Point &q) {return p.x*q.y - p.y*q.x;}
double dist(const Point &p, const Point &q) {return (p-q).norm();}
bool compx(const Point &p, const Point &q) {return p.x != q.x? p.x < q.x : p.y < q.y;}
bool compy(const Point &p, const Point &q) {return p.y != q.y? p.y < q.y : p.x < q.x;}

struct Segment {
  Point p , q;
  Segment(Point p = Point(0.0,0.0), Point q = Point(0.0,0.0)) : p(p), q(q) {}
};

struct Line {
  double a, b, c;
  Line(double a, double b, double c) : a(a), b(b), c(c) {}
  Line(Point p, Point q) {
    a = q.y - p.y;
    b = p.x - q.x;
    c = q.x * p.y - p.x * q.y;
  }
};

struct Circle {
  double r;
  Point p;
  Circle(Point p = Point(0.0, 0.0), double r = 0.0) : p(p), r(r) {}
};

// 点の直線への射影
Point projection (Point p, Line l) {
  double x = p.x - l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 線対称な点
Point reflection(Point p, Line l) {
  double x = p.x - 2.0 * l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - 2.0 * l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 点の線分からの回転方向
int ccw(Point p, Point p1, Point p2) {
  p1 = p1 - p; p2 = p2 - p;
  if(cross(p1,p2) > eps) return 1; 
  if(cross(p1,p2) < -eps) return -1; 
  if(p1 * p2 < 0) return 2; 
  if(p1.norm() < p2.norm()) return -2; 
  return 0; 
}

// 点が線分上にあるか判定
bool on_segment(Point p, Segment s) {
  return (ccw(s.p,s.q,p) == 0 ? true : false);
}

// 線分の交差判定
bool segment_segment_cross(const Segment l, const Segment s) {
  return ccw(l.p,l.q,s.p) * ccw(l.p,l.q,s.q) <= 0 && ccw(s.p,s.q,l.p) * ccw(s.p,s.q,l.q) <= 0;
}

// 直線の平行・直交判定 (平行:2 直交:1 その他:0)
int line_parallel_orthogonal(Line l, Line s) {
  if(abs(l.a*s.a + l.b*s.b) < eps) return 1;
  else if(abs(l.a*s.b - l.b*s.a) < eps) return 2;
  else return 0;
}

// 直線と直線の交点 
vector<Point> line_line_cross(Line l, Line s) {
  vector<Point> vp;
  if(line_parallel_orthogonal(l,s) != 2) {
    Point p;
    p.x = (l.b*s.c - s.b*l.c) / (l.a*s.b - s.a*l.b);
    p.y = (-l.a*s.c + s.a*l.c) / (l.a*s.b - s.a*l.b);
    vp.push_back(p);
  }
  return vp;
}

// 点と直線の距離
double point_line_dist(Point p, Line l) {
  return abs(l.a*p.x + l.b*p.y + l.c) / sqrt(l.a*l.a + l.b*l.b);
}

// 点と線分の距離
double point_segment_dist(Point p, Segment s) {
  Point h = projection(p,Line(s.p,s.q));
  if(on_segment(h,s)) return dist(p,h);
  else return min(dist(p,s.p),dist(p,s.q));
}

// 線分と線分の距離
double segment_segment_dist(Segment l, Segment s) {
  if(segment_segment_cross(l,s)) return 0.0;
  else return min({point_segment_dist(l.p,s),point_segment_dist(l.q,s),point_segment_dist(s.p,l),point_segment_dist(s.q,l)});
}

// 直線と直線の距離
double line_line_dist(Line l, Line s) {
  if(line_parallel_orthogonal(l,s) != 2) return 0.0;
  else if(abs(s.a) < eps) return point_line_dist(Point(0.0,-s.c/s.b),l);
  else return point_line_dist(Point(-s.c/s.a,0),l);
}

// 直線と線分の距離
double line_segment_dist(Line l, Segment s) {
  Point a, b;
  if(abs(l.a) < eps) a = Point(0.0,-l.c/l.b), b = Point(1.0,-l.c/l.b);
  else if(abs(l.b) < eps) a = Point(-l.c/l.a,0.0), b = Point(-l.c/l.a,0.0);
  else a = Point(0.0,-l.c/l.b), b = Point(-l.c/l.a,0);

  if(ccw(a,b,s.p) * ccw(a,b,s.q) <= 0) return 0.0;
  else return min(point_line_dist(s.p,l),point_line_dist(s.q,l));
}

// ★円と円の交差判定 (離れる:4 外接:3 交わる:2 内接:1 内包:0)
int circle_circle_pos(Circle c, Circle d) {
  if(dist(c.p,d.p) >= c.r + d.r + eps) return 4;
  else if(abs(dist(c.p,d.p) - c.r - d.r) < eps) return 3;
  else if(dist(c.p,d.p) >= abs(c.r-d.r) + eps) return 2;
  else if(abs(dist(c.p,d.p) - abs(c.r-d.r)) < eps) return 1;
  else return 0; 
}

// ★円と直線の交点
vector<Point> circle_line_cross(Circle c, Line l) {
  vector<Point> vp;
  Point h = projection(c.p,l);

  double d = l.a*c.p.x + l.b*c.p.y + l.c;
  double q = c.r*c.r - d*d / (l.a*l.a + l.b*l.b);
  if(q >= eps) {
    Point p1, p2;
    p1.x = h.x + sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p1.y = h.y - sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    p2.x = h.x - sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p2.y = h.y + sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    vp.push_back(p1);
    vp.push_back(p2);
  } else if(abs(q) < eps) {
    vp.push_back(h);
  }
  return vp;
} 

// ★円と円の交点
vector<Point> circle_circle_cross(Circle c, Circle d) {
  Line l(2.0*(c.p.x-d.p.x),2.0*(c.p.y-d.p.y),-c.p.x*c.p.x+d.p.x*d.p.x-c.p.y*c.p.y+d.p.y*d.p.y+c.r*c.r-d.r*d.r);
  return circle_line_cross(c,l);
}

// ★多角形の面積
double polygon_area(vector<Point>& v) {
  int l = v.size();
  double s = 0.0;
  for(int i = 0; i < l; i++) s += 1/2.0 * cross(v[i],v[(i+1)%l]);
  return s;
}

// ★多角形の凸性
bool polygon_convex(vector<Point>& v) {
  int l = v.size();
  for(int i = 0; i < l; i++) {
    if(cross(v[(i+1)%l]-v[i],v[(i+2)%l]-v[i]) < -eps) return false;
  }
  return true;
} 

// ★点の多角形への包含 (含まれる:2 辺上:1 外:0)
int polygon_inclusion(const vector<Point>& v, const Point p) {
  int l = v.size();
  bool in = false;
  for(int i = 0; i < l; i++) {
    Point a = v[i] - p, b = v[(i+1)%l] - p;
    if(on_segment(Point(0.0,0.0),Segment(a,b))) return 1;
    if(a.y > b.y) swap(a,b);
    if(a.y <= 0 && b.y > 0 && cross(a,b) < 0) in = !in; 
  }
  return in ? 2 : 0;
}

// ★凸包 O(nlogn) (Graham Scan)
vector<Point> convex_hull(vector<Point>& v) {
  int l = v.size();
  sort(v.begin(),v.end(),compx);
  vector<Point> c(2*l);
  int k = 0;
  for(int i = 0; i < l; i++) {
    while(k > 1 && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  for(int i = l-2, t = k; i >= 0; i--) {
    while(k > t && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  c.resize(k-1);
  return c;
}

// ★最遠点距離(キャリパー法) O(n) (凸包を構成する場合O(nlogn))
double convex_diameter(vector<Point>& v) {
  vector<Point> c = convex_hull(v);
  int l = c.size();
  if(l == 2) return (dist(c[0],c[1]));
  int i = 0, j = 0;
  for(int k = 0; k < l; k++) {
    if(!compx(c[i],c[k])) i = k;
    if(compx(c[j],c[k])) j = k;
  }
  double res = 0.0;
  int si = i, sj = j;
  while(i != sj || j != si) {
    res = max(res,dist(c[i],c[j]));
    if(cross(c[(i+1)%l]-c[i],c[(j+1)%l]-c[j]) < 0) i = (i + 1) % l;
    else j = (j + 1) % l;
  }
  return res;
}

// 最近接点距離 O(nlogn) x座標でsortして渡す.
double closest_pair(vector<Point>::iterator it, int n) {
  if(n <= 1) return inf;
  int m = n / 2;
  double x = it[m].x;
  double d = min(closest_pair(it,m),closest_pair(it+m,n-m));
  inplace_merge(it,it+m,it+n,compy);

  vector<Point> b;
  for(int i = 0; i < n; i++) {
    if(abs(it[i].x-x) >= d) continue;
    for(int j = 0; j < b.size(); j++) {
      double dx = it[i].x - b[b.size()-j-1].x;
      double dy = it[i].y - b[b.size()-j-1].y;
      if(dy >= d) break;
      d = min(d,sqrt(dx*dx+dy*dy));
    }
    b.push_back(it[i]);
  }
  return d;
}

int main() {
  int n;
  cin >> n;
  vector<Point> v(n);
  rep(i,n) cin >> v[i].x >> v[i].y;
  sort(v.begin(),v.end(),compx);
  printf("%.9lf\n",closest_pair(v.begin(),n));
  return 0; 
}