Pagini recente » Cod sursa (job #886667) | Cod sursa (job #2394404) | Istoria paginii runda/n | Cod sursa (job #999567) | Cod sursa (job #1214761)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
#define NMAX 100005
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair <long long,long long> v[NMAX],aux[NMAX];
int n;
inline long long dist(pair <long long,long long> A, pair <long long,long long> B)
{
long long X=(A.first-B.first)*(A.first-B.first);
long long Y=(A.second-B.second)*(A.second-B.second);
return X+Y;
}
void interclasare(int st, int m, int dr)
{
int i,j,k;
for (i=st,j=m+1,k=st-1;i<=m && j<=dr;)
if (v[i].second<v[j].second)
aux[++k]=v[i++];
else
aux[++k]=v[j++];
for (;i<=m;++i)
aux[++k]=v[i];
for (;j<=dr;++j)
aux[++k]=v[j];
for (i=st;i<=dr;++i)
v[i]=aux[i];
}
long long rec(int st, int dr)
{
int i,j;
long long minim;
if (dr-st==1)
{
interclasare(st,st,dr);
return dist(v[st],v[dr]);
}
if (dr-st==2)
{
minim=min(dist(v[st],v[st+1]),dist(v[st],v[dr]));
minim=min(minim,dist(v[dr],v[st+1]));
interclasare(st,st+1,dr);
return minim;
}
int m=(st+dr)>>1;
long long qs=rec(st,m);
long long qd=rec(m+1,dr);
interclasare(st,m,dr);
minim=min(qs,qd);
for (i=st;i<=dr;++i)
for (j=i+1;j<=i+7 && j<=dr;++j)
minim=min(minim,dist(v[i],v[j]));
return minim;
}
int main()
{
int i;
fin>>n;
for (i=1;i<=n;++i)
fin>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
fout<<setprecision(6)<<fixed<<(double)sqrt(rec(1,n))<<"\n";
return 0;
}