#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
double dist(pair<long,long> pct1,pair<long,long> pct2)
{
return sqrt(double((pct1.first-pct2.first)*(pct1.first-pct2.first)+(pct1.second-pct2.second)*(pct1.second-pct2.second)));
}
pair<pair<long,long>,pair<long,long>> minStripDist (vector<pair<long,long>> strip, double mini,pair<pair<long,long>,pair<long,long>> minPoint)
{
for(long i=0;i<strip.size()-1;i++)
for(long j=i+1;j<strip.size()&&(strip[j].second-strip[i].second<mini);j++)
if(dist(strip[i],strip[j])<mini)
{
mini=dist(strip[i],strip[j]);
minPoint=make_pair(strip[i],strip[j]);
}
return minPoint;
}
pair<pair<long,long>,pair<long,long>> minDist(vector<pair<long,long>> vct_x, vector<pair<long,long>> vct_y, long n)
{
if(n==2)
return make_pair(vct_x[0],vct_x[1]); //cand n=2
if(n==3) //sau n=3
{ //putem calcula cele mai apropiate puncte
double mini=dist(vct_x[0],vct_x[1]);
pair<pair<long,long>,pair<long,long>> result;
result.first=vct_x[0];
result.second=vct_x[1];
//prin "brute force"
if(mini>dist(vct_x[0],vct_x[2]))
{
mini=dist(vct_x[0],vct_x[2]); //sunt "base case"-uri
result.first=vct_x[0];
result.second=vct_x[2];
}
if(mini>dist(vct_x[1],vct_x[2]))
{
mini=dist(vct_x[1],vct_x[2]);
result.first=vct_x[1];
result.second=vct_x[2];
}
return result;
}
/* cout<<"vx"<<endl;
for(int i=0;i<n;i++)
cout<<vct_x[i].first<<" "<<vct_x[i].second<<" ";
cout<<endl;
cout<<"vy"<<endl;
for(int i=0;i<n;i++)
cout<<vct_y[i].first<<" "<<vct_y[i].second<<" ";
cout<<endl;
*/
long mid=n/2; // gasim pozitia din mijlocul vectorului sortat dupa x
while(mid>0&&vct_x[mid].first==vct_x[mid-1].first) mid--;
pair<long,long> midPoint=vct_x[mid]; //acesta imparte vectorul initial in 2 subvectori de lungimi aproximativ egale
// cout<<"mid "<<mid<<"cu val "<<vct_x[mid].first<<" "<<vct_x[mid].second<<endl;
vector<pair<long,long>> LeftYPoints;
vector<pair<long,long>> RightYPoints;
for(long i=0;i<n;i++)
{
if(vct_y[i].second<midPoint.first) // daca e in stanga puntului din mijloc
{
LeftYPoints.push_back(vct_y[i]);
} //vct_y are x-ul pe second, vct_x are x-ul pe first
else
{
RightYPoints.push_back(vct_y[i]);
}
}
/* cout<<"leftypoints"<<endl;
for(int i=0;i<LeftYPoints.size();i++)
cout<<LeftYPoints[i].first<<" "<<LeftYPoints[i].second<<" ";
cout<<endl;
cout<<"rightypoints"<<endl;
for(int i=0;i<RightYPoints.size();i++)
cout<<RightYPoints[i].first<<" "<<RightYPoints[i].second<<" ";
cout<<endl; */
pair<pair<long,long>,pair<long,long>> leftMin=minDist(vct_x,LeftYPoints,LeftYPoints.size());
vector<pair<long,long>> rightRemainder;
for(long i=LeftYPoints.size();i<n;i++)
rightRemainder.push_back(vct_x[i]);
pair<pair<long,long>,pair<long,long>> rightMin=minDist(rightRemainder,RightYPoints,RightYPoints.size());
double distL=dist(leftMin.first,leftMin.second);
double distR=dist(rightMin.first,rightMin.second);
double miniDist;
pair<pair<long,long>,pair<long,long>> minPoint;
if(distL<distR)
{
miniDist=distL;
minPoint=leftMin;
}
else
{
miniDist=distR;
minPoint=rightMin;
}
vector<pair<long,long>> strip; // strip va retine doar puncte care se afla la distanta maxima miniDist de dreapta
//verticala de ecuatie x=midPoint.x
for(long i=0;i<n;i++)
{
if((vct_y[i].second>=midPoint.first)&&vct_y[i].second-midPoint.first<miniDist)
strip.push_back(make_pair(vct_y[i].second,vct_y[i].first));
else if((vct_y[i].second<midPoint.first)&&midPoint.first-vct_y[i].second<miniDist)
strip.push_back(make_pair(vct_y[i].second,vct_y[i].first));
}
pair<pair<long,long>,pair<long,long>> stripPoint=minStripDist(strip,miniDist,minPoint);
if(stripPoint!=minPoint)
return stripPoint;
return minPoint;
}
int main()
{
long n;
ifstream fin;
fin.open("grader_test13.in");
ofstream fout;
fout.open("cmap.out");
vector<pair<long,long>> vct_x,vct_y;
fin>>n;
for(long i=0;i<n;i++)
{
pair<long,long> pct;
fin>>pct.first>>pct.second; //first=x, second=y
vct_x.push_back(make_pair(pct.first,pct.second));
vct_y.push_back(make_pair(pct.second,pct.first));
}
sort(vct_x.begin(),vct_x.end()); // sortez punctele dupa x
sort(vct_y.begin(),vct_y.end()); // sortez punctele dupa y
pair<pair<long,long>,pair<long,long>> result=minDist(vct_x,vct_y,n);
fout<<std::fixed << std::setprecision(7)<<dist(result.first, result.second);
return 0;
}