Pagini recente » Cod sursa (job #1110661) | Cod sursa (job #315955) | Cod sursa (job #1288127) | Cod sursa (job #605823) | Cod sursa (job #2299144)
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
#define maxn 100005
#define ll long long
const ll inf=999999999;
#define minim(a,b) a<b?a:b
int n;
vector<pair<ll,ll> > x;
ll calc(const pair<ll,ll> a,const pair<ll,ll> b){
return ((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}
ll solve(int st,int dr)
{
if(dr-st<=3){
ll ans=inf;
for (int i=st;i<dr;i++)
for (int j=i+1;j<=dr;j++)
ans=minim(ans,calc(x[i],x[j]));
return ans;
}
int mij=(st+dr)/2;
ll best=minim(solve(st,mij),solve(mij+1,dr));
vector<pair<int,int> > aux;
for(int i=st;i<=dr;++i)
if(best>=abs(x[i].first-x[mij].first))
aux.push_back(x[i]);
int counter=aux.size();
sort(aux.begin(),aux.end());
for(int i=0;i<counter-1;++i)
for(int j=i+1;j<counter&&(j-i<8);++j)
best=minim(calc(aux[i],aux[j]),best);
return best;
}
int main()
{
int i;
cin>>n;
x.resize(n+1);
for(i=1;i<=n;i++)
cin>>x[i].first>>x[i].second;
sort(x.begin(),x.end());
cout<<fixed<<setprecision(6)<<sqrt(solve(1,n));
return 0;
}