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;

// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment,[-PI,PI]
using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
bool operator==(const CP &l, const CP &r) {
  return norm(l - r) <= EPS * EPS;
}
bool operator<(const CP &l, const CP &r) {
  if(l.X != r.X) return l.X < r.X;
  return l.Y < r.Y;
}

// cos a
long double costh(long double a, long double b,
                  long double c) {
  return (b * b + c * c - a * a) / (2.0L * b * c);
}

// dot(a,b) = |a||b|cos x
long double dot(CP a, CP b) { return (conj(a) * b).X; }
// cross(a,b) : area of parallelogram
// sign : a-> b ,counter clockwise? + : -
long double cross(CP a, CP b) { return (conj(a) * b).Y; }
long double corner(CP a, CP b) {
  //[0,PI]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}
bool equalP(CP a, CP b) { return norm(a - b) <= EPS * EPS; }

CP projectionLP(CP s, CP t, CP p) {
  if(s == t) return s;
  CP base = t - s;
  long double r = dot(p - s, base) / norm(base);
  return s + base * r;
}

CP reflectionLP(CP s, CP t, CP p) {
  CP tmp = (projectionLP(s, t, p) - p);
  tmp *= 2;
  return p + tmp;
}

int calc_clockwiseSP(CP s, CP t, CP p) {
  t -= s;
  p -= s;
  if(cross(t, p) > EPS) return 1;   // "COUNTER_CLOCKWISE"
  if(cross(t, p) < -EPS) return -1; //"CLOCK_WISE"
  if(dot(t, p) < 0) return 2;       // "ONLINE_BACK"
  if(norm(t) < norm(p)) return -2;  // "ONLINE_FRONT"
  return 0;                         // "ON_SEGMENT"
}

int parallel_orthogonalLL(CP s, CP t, CP a, CP b) {
  t -= s;
  b -= a;
  if(abs(cross(t, b)) <= EPS) return 2; // "parallel"
  if(abs(dot(t, b)) <= EPS) return 1;   // "orthogonal"
  return 0;
}

CP intersectionLL(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_segSP(CP s, CP t, CP p) {
  // if not use end point, dot(s - p, t - p) < 0
  return abs(cross(s - p, t - p)) <= EPS &&
         dot(s - p, t - p) <= 0;
}

// crossing segments? (a,b) and (c,d)
bool iscrossSS(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= EPS) {
    return on_segSP(a, b, c) || on_segSP(a, b, d) ||
           on_segSP(c, d, a) || on_segSP(c, d, b);
  }
  CP isp = intersectionLL(a, b, c, d);
  return on_segSP(a, b, isp) && on_segSP(c, d, isp);
}

long double distLP(CP s, CP t, CP p) {
  return abs(cross(t - s, p - s) / abs(t - s));
}

long double distSP(CP s, CP t, CP p) {
  if(dot(t - s, p - s) < 0) return abs(p - s);
  if(dot(s - t, p - t) < 0) return abs(p - t);
  return distLP(s, t, p);
}

long double distSS(CP a, CP b, CP c, CP d) {
  long double res = 1e18;
  if(iscrossSS(a, b, c, d)) return 0.0L;
  res = min(res, distSP(a, b, c));
  res = min(res, distSP(a, b, d));
  res = min(res, distSP(c, d, a));
  res = min(res, distSP(c, d, b));
  return res;
}

// counter clockwise
bool is_convex(const vector<CP> &pol) {
  int n = pol.size();
  for(int i = 0; i < n; ++i)
    if(cross(pol[(i + 1) % n] - pol[i],
             pol[(i + 2) % n] - pol[(i + 1) % n]) < -EPS)
      return 0;
  return 1;
}

vector<CP> convex_hull(vector<CP> &ps) {
  auto lmd = [&](const CP &l, const CP &r) {
    if(l.X != r.X) return l.X < r.X;
    return l.Y < r.Y;
  };
  vector<CP> qs;
  int psize = ps.size();
  sort(ps.begin(), ps.end(), lmd);
  int k = 0;
  qs.resize(psize * 2);
  for(int i = 0; i < psize; ++i) {
    while(k > 1 && cross(qs[k - 1] - qs[k - 2],
                         ps[i] - qs[k - 1]) <= 0)
      --k;
    qs[k++] = ps[i];
  }
  for(int i = psize - 2, t = k; i >= 0; --i) {
    while(k > t && cross(qs[k - 1] - qs[k - 2],
                         ps[i] - qs[k - 1]) <= 0)
      --k;
    qs[k++] = ps[i];
  }
  qs.resize(k - 1);
  return qs;
}

long double convex_diameter(const vector<CP> &pol) {
  vector<CP> v = pol;
  v = convex_hull(v);
  int n = v.size(), i = 0, j = 0;
  if(n < 2) return 0.0L;
  if(n == 2) return abs(v[0] - v[1]);
  for(int k = 0; k < n; ++k) {
    if(v[k].X < v[i].X) i = k;
    if(v[k].X > v[j].X) j = k;
  }
  long double res = 0;
  int si = i, sj = j;
  while(i != sj || j != si) {
    res = max(res, abs(v[i] - v[j]));
    if(cross(v[(i + 1) % n] - v[i], v[(j + 1) % n] - v[j]) <
       0)
      (++i) %= n;
    else
      (++j) %= n;
  }
  return res;
}

vector<CP> convex_cut(const vector<CP> &pol, const CP &s,
                      const CP &t) {
  vector<CP> res;
  int n = pol.size();
  for(int i = 0; i < n; ++i) {
    CP nows = pol[i], nowt = pol[(i + 1) % n];
    if(cross(t - s, nows - s) >= -EPS) res.push_back(nows);
    if(cross(t - s, nows - s) * cross(t - s, nowt - s) < 0)
      res.push_back(intersectionLL(s, t, nows, nowt));
  }
  return res;
}

struct Circle {
  CP o;
  long double r;
  Circle(long double _x = 0.0L, long double _y = 0.0L,
         long double _r = 0.0L)
      : o(CP(_x, _y)), r(_r) {}
  Circle(CP _o, long double _r = 0.0) : o(_o), r(_r) {}
};

// number of tangents
int iscrossCC(Circle l, Circle r) {
  long double distlr = abs(l.o - r.o);
  if(distlr - (l.r + r.r) > EPS)
    return 4; // not touch
  else if(abs(distlr - (l.r + r.r)) <= EPS)
    return 3; // circumscription
  else if(max(l.r, r.r) - (distlr + min(l.r, r.r)) < -EPS)
    return 2; // cross
  else if(max(l.r, r.r) - (distlr + min(l.r, r.r)) <= EPS)
    return 1; // inscribed
  else        // contain
    return 0;
}

void intersectionCC(Circle c1, Circle c2, CP &res1,
                    CP &res2) {
  if(iscrossCC(c1, c2) == 4) {
    res1 = res2 = CP(-1e18, -1e18);
    return;
  }
  long double d = abs(c1.o - c2.o);
  long double arg = acos(costh(c2.r, c1.r, d));
  res1 = (c2.o - c1.o) * CP(cos(arg), sin(arg));
  res1 *= c1.r / abs(res1);
  res1 += c1.o;
  res2 = reflectionLP(c1.o, c2.o, res1);
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

void intersectionCL(Circle ci, CP s, CP t, CP &res1,
                    CP &res2) {
  res1 = res2 = projectionLP(s, t, ci.o);
  long double r = sqrtl(ci.r * ci.r - norm(res1 - ci.o));
  t -= s;
  t *= r / abs(t);
  res1 += t;
  res2 -= t;
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

void contactCP(Circle ci, CP p, CP &res1, CP &res2) {
  long double d = abs(ci.o - p);
  if(abs(d - ci.r) <= EPS) {
    res1 = res2 = p;
    return;
  }
  else if(d < ci.r) {
    res1 = res2 = CP(-1e18, -1e18);
    return;
  }
  long double arg = asin(ci.r / d);
  res1 = (ci.o - p) * CP(cos(arg), sin(arg));
  res1 *= (d * cos(arg)) / abs(res1);
  res1 += p;
  res2 = reflectionLP(p, ci.o, res1);
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

long double polygonarea(const vector<CP> &pol) {
  int n = pol.size();
  long double res = 0;
  for(int i = 0; i < n; ++i)
    res += (pol[(i - 1 + n) % n].X - pol[(i + 1) % n].X) *
           pol[i].Y;
  return res / 2.0L;
}

int containPolP(const vector<CP> &pol, CP p) {
  bool con = 0, onseg = 0;
  int n = pol.size();
  for(int i = 0; i < n; ++i) {
    onseg |= on_segSP(pol[i], pol[(i + 1) % n], p);
    CP s = pol[i] - p, t = pol[(i + 1) % n] - p;
    if(s.Y > t.Y) swap(s, t);
    if(s.Y * t.Y <= 0 && t.Y > 0 && cross(s, t) < 0)
      con = !con;
  }
  if(onseg) return 1;
  if(con) return 2;
  return 0;
}

long double closest_pair(vector<CP> &v, int l = -1,
                         int r = -1, bool reqsqrt = 0) {
  if(l == r && l == -1) {
    l = 0;
    r = v.size();
    reqsqrt = 1;
    auto lmd = [&](const CP &l, const CP &r) {
      if(l.X != r.X) return l.X < r.X;
      return l.Y < r.Y;
    };
    sort(v.begin(), v.end(), lmd);
  }
  if(r - l < 2) return 1e18;
  if(r - l == 2) {
    if(v[l].Y > v[l + 1].Y) swap(v[l], v[l + 1]);
    if(reqsqrt) return abs(v[l] - v[l + 1]);
    return norm(v[l] - v[l + 1]);
  }
  int mid = (l + r) / 2;
  long double x = v[mid].X,
              res = min(closest_pair(v, l, mid),
                        closest_pair(v, mid, r));
  auto f = [](CP pl, CP pr) { return pl.Y < pr.Y; };
  inplace_merge(v.begin() + l, v.begin() + mid,
                v.begin() + r, f);
  vector<CP> tmp;
  for(int i = l; i < r; ++i) {
    long double dx = abs(v[i].X - x);
    int tsize = tmp.size();
    if(dx * dx >= res) continue;
    for(int j = 0; j < tsize; ++j) {
      CP delta = v[i] - tmp[tsize - 1 - j];
      if(delta.Y * delta.Y >= res) break;
      res = min(res, norm(delta));
    }
    tmp.push_back(v[i]);
  }
  if(reqsqrt) res = sqrtl(res);
  return res;
}

int main() {
  cout << fixed << setprecision(10);
  vector<CP> v;
  int n;
  cin >> n;
  for(int i = 0; i < n; ++i) {
    long double x, y;
    cin >> x >> y;
    v.emplace_back(x, y);
  }
  cout << closest_pair(v) << endl;
  return 0;
}