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>
#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define numa(x,a) for(auto x: a)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define pf push_front
#define sec second
#define sz(x) ((int)(x).size())
#define ALL( c ) (c).begin(), (c).end()
#define gcd(a,b) __gcd(a,b)
#define mem(x,n) memset(x,n,sizeof(x))
#define endl "\n"
using namespace std;
template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class T,class U> std::ostream& operator<<(std::ostream &os, std::pair<T,U> &p){ os << "(" << p.first <<", " << p.second <<")";return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "}" : ", "); return os; }
#define DEBUG1(var0) { std::cerr << (#var0) << "=" << (var0) << endl; }
#define DEBUG2(var0, var1) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG1(var1); }
#define DEBUG3(var0, var1, var2) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG2(var1,var2); }
#define DEBUG4(var0, var1, var2, var3) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG3(var1,var2,var3); }
using ll = long long;

typedef struct P{
  long double x;
  long double y;
}P_t;

inline long double dist(const P_t &a, const P_t &b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

pair <pair <int, int>, long double> closest_pair(const vector <int> &xi, const vector <int> &yi, const vector <P_t> &ps){//note that xi and yi must be sorted by x and y, respectively
  assert(xi.size() == yi.size());
  if (xi.size() == 1) {
    return make_pair(mp(-1,-1), -1);
  }
  if (xi.size() == 2) {
    return make_pair(mp(xi[0], xi[1]), dist(ps[xi[0]], ps[xi[1]]));
  }

  int med = xi.size() / 2;
  vector <int> lxi(xi.begin(), xi.begin() + med);
  vector <int> lyi(lxi.size());
  vector <int> rxi(xi.begin() + med, xi.end());
  vector <int> ryi(rxi.size());

  set <int> lxis(xi.begin(), xi.begin() + med);

  for (int i = 0, cnt1 = 0, cnt2 = 0; i < yi.size(); i++) {
    if (lxis.find(yi[i]) != lxis.end()) {
      lyi[cnt1++] = yi[i];
    }else{
      ryi[cnt2++] = yi[i];
    }
  }
  //DEBUG4(lxi, lyi, rxi, ryi);
  pair <pair <int, int>, long double> ansl = closest_pair(lxi, lyi, ps);
  pair <pair <int, int>, long double> ansr = closest_pair(rxi, ryi, ps);
  long double dl = ansl.second;
  long double dr = ansr.second;
  long double d;
  pair <int,int> ansp;
  if (dl > 0 && dl < dr) {
    d = dl;
    ansp = ansl.first;
  }else{
    d = dr;
    ansp = ansr.first;
  }
  long double medx = (ps[lxi.back()].x + ps[rxi.front()].x) / 2.0;
  vector <int> cands;
  for (int i: yi) {
    if (medx - 2 * d <= ps[i].x && ps[i].x <= medx + 2 * d) {
      cands.push_back(i);
    }
  }
  for (int i = 0; i < cands.size(); i++) {
    for (int j = i + 1; j < cands.size(); j++) {
      if (ps[cands[j]].y - ps[cands[i]].y > 2 * d) {
        break;
      }
      long double d2 = dist(ps[cands[j]], ps[cands[i]]);
      if (d2 < d) {
        ansp = make_pair(cands[j], cands[i]);
        d = d2;
      }
    }
  }
  return make_pair(ansp, d);
}

int main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int N;
  cin >> N;
  std::vector <P_t> ps(N);
  std::vector <pair <long double, int> > xi_(N);
  std::vector <pair <long double, int> > yi_(N);
  for (int i = 0; i < N; i++) {
    cin >> ps[i].x >> ps[i].y;
    xi_[i].first = ps[i].x;
    xi_[i].second = i;
    yi_[i].first = ps[i].y;
    yi_[i].second = i;
  }
  sort(xi_.begin(), xi_.end());
  sort(yi_.begin(), yi_.end());
  std::vector <int> xi(N);
  std::vector <int> yi(N);
  for (int i = 0; i < N; i++) {
    xi[i] = xi_[i].second;
    yi[i] = yi_[i].second;
  }
  pair <pair <int, int> , long double> ans = closest_pair(xi, yi, ps);
  /*
  if (ans.first.first > ans.first.second) {
    cout << ans.first.second << ' ' << ans.first.first << ' ';
  }else{
    cout << ans.first.first << ' ' << ans.first.second << ' ';
  }
  */
  cout << fixed << setprecision(10)<< ans.second << endl;
  return 0;
}