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;
typedef long long ll;
typedef pair<int,int> pii;
typedef complex<long double> point;

#define dot(a,b) ((conj(a)*(b)).real())
#define length(a) hypot((a).X,(a).Y)

#define X real()
#define Y imag()
#define vect(p1,p2) ((p2)-(p1))
#define cross(a,b) ((conj(a)*(b)).imag())
const long double EPS = 1e-12;
const long double INF = 1e18;

#define STRAIGHT 0
#define CLOCKWISE 1
#define COUNTERCLOCKWISE 2
int orient(const point &a, const point &b, const point &c){
    long double res = cross(vect(a, b), vect(a, c));

    if(res < -EPS)
        return CLOCKWISE;
    if(res > EPS)
        return COUNTERCLOCKWISE;

    return STRAIGHT;
}


long double point_line_distance(const point& a, const point& b, const point& p) {
	return fabs(cross(b - a, p - a)) / length(b - a);
}
long double point_segment_distance(const point& a, const point& b, const point& p) {
	if (dot(p-a,b-a) < EPS)
		return length(p - a);
	if (dot(p-b,a-b) < EPS)
		return length(p - b);
	return point_line_distance(a, b, p);
}

bool point_on_line(const point &a, const point &b,const point &p) {
	return fabs(cross(vect(a,b), vect(a,p))) < EPS;
}

bool point_on_segment(const point &a,const point &b,const point &p) {
	return dot(vect(a,b), vect(a,p)) > -EPS && point_on_line(a, b, p)
			&& dot(vect(b,a), vect(b,p)) > -EPS;
}

bool line_intersect(point a, point b, point p, point q, point& r) {
	long double d1 = cross(p - a, b - a);
	long double d2 = cross(q - a, b - a);
	if (fabs(d2 - d1) < EPS)
		return false;
	r = (d1 * q - d2 * p) / (d1 - d2);
	return true;
}
bool segment_intersect(point a, point b, point p, point q) {

    if(orient(a, b, p) == STRAIGHT && orient(b, p, q) == STRAIGHT)
        return point_on_segment(a, b , p) || point_on_segment(a, b, q);

    long double d1 = cross(p - a, b - a);
    long double d2 = cross(q - a, b - a);
    long double d3 = cross(a - p, q - p);
    long double d4 = cross(b - p, q - p);

    if (d1 * d2 < EPS && d3 * d4 < EPS)
        return true;
    else
        return false;
}


struct orient_cmp {
	point a;
	orient_cmp(point a): a(a){}

	bool operator()(const point& c, const point& b) const {
	    return orient(a, b, c) == CLOCKWISE;
	}
};

bool point_in_triangle(const point& a, const point& b, const point& c, const point& p){
    long double s1 = fabs(cross(vect(a, b), vect(a, c)));
    long double s2 = fabs(cross(vect(p, a), vect(p, b))) + fabs(cross(vect(p, b), vect(p, c))) + fabs(cross(vect(p, c),vect(p, a)));

    return fabs(s1 - s2) < EPS;
}

bool point_in_convex_polygon(const vector<point> &convex, const point &p){
    int n = convex.size();

    if(point_on_segment(convex[0], convex[1], p))
        return true;

    if(point_on_segment(convex[0], convex[n-1], p))
        return true;

    if(orient(convex[0], convex[1], p) == CLOCKWISE)
        return false;

    if(orient(convex[0], convex[n-1], p) == COUNTERCLOCKWISE)
        return false;


    auto pos = lower_bound(convex.begin() + 1, convex.end(), p, orient_cmp(convex[0])) - convex.begin();

    if(pos == 1 || pos == n)
        return false;

    if(point_on_segment(convex[pos-1], convex[pos], p))
        return true;

    if(point_in_triangle(convex[0], convex[pos-1], convex[pos], p))
        return true;

    return false;
}
bool segment_intersect_convex_polygon(const vector<point> &convex, const point &a, const point &b){
    int n = convex.size();

    auto pos = lower_bound(convex.begin() + 1, convex.end(), a, orient_cmp(convex[0])) - convex.begin();

    if(pos == 0 || pos == n)
        return false;

    return segment_intersect(a, b, convex[pos-1], convex[pos]);
}

struct cmp {
	point about;
	cmp(point about): about(about) {}

	bool operator()(const point& p, const point& q) const {
		int res = orient(p, about, q);

		if (res == STRAIGHT)
			return make_pair(p.Y, p.X) < make_pair(q.Y, q.X);
		return res == CLOCKWISE;
	}
};

vector<point> convex_hull(vector<point> points) {
    vector<point> convex;

	point mn(INF, INF);
	for (int i = 0; i < points.size(); i++) {
		if (make_pair(points[i].Y, points[i].X) < make_pair(mn.Y, mn.X))
			mn = points[i];
	}

	sort(points.begin(), points.end(), cmp(mn));

	convex.clear();
	convex.push_back(points[0]);

	if (points.size() == 1)
		return convex;

	convex.push_back(points[1]);

	for (int i = 2; i <= points.size(); i++) {
		point c = points[i % points.size()];

		while (convex.size() > 1) {
			point b = convex[convex.size() - 1];
			point a = convex[convex.size() - 2];

			if (orient(a,b,c) == COUNTERCLOCKWISE)
				break;

			convex.pop_back();
		}
		if (i < points.size())
			convex.push_back(points[i]);
	}

	return convex;
}


vector<point> polygon_cut(const vector<point>& polygon, const point& a, const point& b) {
    vector<point> res;

    for (int i = 0; i < polygon.size(); i++) {
        auto p = polygon[i];
        auto q = polygon[(i + 1) % polygon.size()];

        if (orient(a, b, p) == COUNTERCLOCKWISE)
            res.push_back(p);

        if ((orient(a, b, p) == COUNTERCLOCKWISE) ^ (orient(a, b, q) == COUNTERCLOCKWISE)) {
            point r;
            if(line_intersect(b, a, p, q, r))
                res.push_back(r);
        }
    }
    //cout << a <<" " <<b <<": " <<"\n";
    //for(auto p: res)
     //   cout << p <<"\n";
    //cout <<"\n";

    return res;
}

vector<point> convex_polygon_intersection(const vector<point>& polygon1, const vector<point>& polygon2) {
    vector<point> res = polygon1;

    for (int i = 0; i < polygon2.size(); i++) {
        auto p = polygon2[i];
        auto q = polygon2[(i + 1) % polygon2.size()];

        res = polygon_cut(res, p, q);
    }

    return res;
}

double polygon_area(const vector<point>& polygon) {
    if(polygon.size()<3 )
        return 0;

    double res = 0;
    for (int i = 0; i < polygon.size() - 1; i++)
        res += cross(polygon[i], polygon[i+1]);
    res += cross(polygon.back(), polygon.front());

    res /= 2.0;
    return fabs(res);
}

struct order_by_x_cmp{
  bool operator ()(const point &left, const point &right) const{
    if(left.X != right.X)
        return left.X < right.X;
    return left.Y < right.Y;
  }
};

struct order_by_y_cmp{
  bool operator ()(const point &left, const point &right) const{
    if(left.Y != right.Y)
        return left.Y < right.Y;
    return left.X < right.X;
  }
};

point p1, p2;

double closest_pair(vector<point> points) {
    int n = points.size();
    sort(points.begin(), points.end(), order_by_x_cmp());
    set<point, order_by_y_cmp> active_set;

    double best_dist = INF;

    for (int i = 0, j = 0; i < n; i++) {
        while (j<n && points[i].X - points[j].X + EPS >= best_dist) {
            active_set.erase(points[j]);
            j++;
        }

        auto it1 = active_set.lower_bound(points[i] + point(0, -best_dist - EPS));
        auto it2 = active_set.upper_bound(points[i] + point(0, +best_dist + EPS));

        for (auto it = it1; it != it2; it++){
            double new_dist = abs(points[i] - (*it));

            if(new_dist < best_dist){
                best_dist = new_dist;
                p1 = points[i], p2 = *it;
            }
        }


        active_set.insert(points[i]);
    }

    return best_dist;
}
int main(){

    int n; cin>>n;
    vector<point>vec;
    for(int i=0 ; i<n; i++){
        double x,y; cin>>x>>y;
        vec.push_back(point(x, y));
    }

    cout << setprecision(12)<< fixed <<  closest_pair(vec) <<"\n";
    return 0;
}