Pagini recente » Cod sursa (job #2532418) | Cod sursa (job #2682535) | Cod sursa (job #2337392) | Cod sursa (job #859929) | Cod sursa (job #1163755)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF ~(1LL<<63)
#define Nmax 100010
using namespace std;
pair <int, int> X[Nmax],Y[Nmax],aux[Nmax];
vector <pair <int, int> > Pct;
int N;
inline long long Distanta(pair<int, int> a, pair<int, int> b)
{
return 1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second);
}
void Citire_si_formare()
{
scanf("%d",&N);
for(int i=0;i<N;++i)
scanf("%d %d",&X[i].first,&X[i].second);
sort(X,X+N);
for(int i=0;i<N;++i)
{
Y[i].first=X[i].second;
Y[i].second=X[i].first;
}
}
long long Divide(int st, int dr)
{
if(dr-st<=1)
return INF;
if(dr-st==2)
{
if(Y[st]>Y[st+1])
swap(Y[st],Y[st+1]);
return Distanta(Y[st],Y[st+1]);
}
int mid=(st+dr)/2;
long long minim=min(Divide(st,mid),Divide(mid,dr));
merge(Y+st,Y+mid,Y+mid,Y+dr,aux);
copy(aux,aux+dr-st,Y+st);
Pct.clear();
for(int i=st;i<dr;++i)
{
if(abs(X[mid].first-Y[i].second)<=minim)
Pct.push_back(Y[i]);
}
for(int i=0;i<Pct.size();++i)
for(int j=i+1;j< Pct.size() && j-i<=8 ; ++j)
minim=min(minim,Distanta(Pct[i],Pct[j]));
return minim;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
Citire_si_formare();
long long d=Divide(0,N);
double Rezultat= sqrt(d);
printf("%lf\n",Rezultat);
return 0;
}