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;

namespace ClosestPair{
	// DIM=3????£????????¬????????????????????????´?????????getNearPoints()makeBucket()?????´
	const double EPS = 1e-9;
	const int DIM = 3;
	typedef array<double,DIM> P;

	double dist(const P &p1,const P &p2){
		double ans = 0;
		for(int i = 0 ; i < DIM ; i++)
			ans += (p1[i]-p2[i])*(p1[i]-p2[i]);
		return sqrt(ans);
	}
	typedef array<int,DIM> Block;
	typedef map<Block,vector<int>> Bucket;
	Block getBlock(const P &p,double w){
		Block res;
		for(int i = 0 ; i < DIM ; i++) res[i] = p[i] / w;
		return res;
	}
	vector<int> getNearPoints(const Bucket &b,double w,const P &p){
		vector<int> res;
		auto key = getBlock(p,w);
		for(int x0 = -1 ; x0 <= 1 ; x0++)
			for(int x1 = -1 ; x1 <= 1 ; x1++)
				for(int x2 = -1 ; x2 <= 1 ; x2++){
					auto it = b.find(Block{key[0]+x0,key[1]+x1,key[2]+x2});
					if( it != b.end() ){
						for( int id : it->second ) res.push_back(id);
					}
				}
		return res;
	}
	//???w???n?¬?????????±????????????????????????????????¨????????°??¨??????????????????????±????????????¨?????§?????????
	Bucket makeBucket(const vector<P> &ps,double w){
		Bucket b;
		for(int i = 0 ; i < ps.size() ; i++)
			b[getBlock(ps[i],w)].push_back(i);
		return b;
	}
	// ????????????????????¢????????????????????±???????¬??§??????? map????????¨?????????????????§???????¨???????O(n log n)
	// ?????±??????????????????????§???????????????????????¢????????£?????????????????????????????????§??????????????§???????????????2w??????????????????????????????w???????????????????\??????????
	double closetPairDistance(vector<P> ps){
		assert(ps.size()>=2);
		random_shuffle(ps.begin(),ps.end());
		double w = dist(ps[0],ps[1]);
		vector<P> build = {ps[0],ps[1]};
		auto b = makeBucket(build,w);
		for(int i = 2 ; i < ps.size() ; i++){
			double next_w = w;
			for( int j : getNearPoints(b,2*w,ps[i]) )
				next_w = min(next_w,dist(ps[i],ps[j]));
			build.push_back(ps[i]);
			if( w - EPS > next_w ){
				w = next_w;
				b = makeBucket(build,2*w);
			}else{
				b[getBlock(ps[i],2*w)].push_back(i);
			}
		}
		return w;
	}
};

using namespace ClosestPair;

int main(){
	int n;
	vector<P> ps;
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		double x,y;
		cin >> x >> y;
		ps.push_back(P{x,y,0});
	}
	printf("%.10lf\n",closetPairDistance(ps));
}