Pagini recente » Cod sursa (job #1492379) | Cod sursa (job #16397) | Cod sursa (job #3212860) | Cod sursa (job #1020447) | Cod sursa (job #1215508)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
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;
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 cmap(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+1],v[dr]));
minim=min(minim,dist(v[st],v[dr]));
interclasare(st,st+1,dr);
return minim;
}
int m=(st+dr)>>1;
long long qs=cmap(st,m);
long long qd=cmap(m+1,dr);
minim=min(qs,qd);
interclasare(st,m,dr);
for (i=st;i<=dr;++i)
for (j=i+1;j<i+8 && 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(cmap(1,n))<<"\n";
return 0;
}