Pagini recente » Cod sursa (job #1090391) | Cod sursa (job #1086753) | Cod sursa (job #1973689) | Cod sursa (job #2926287) | Cod sursa (job #1214758)
#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;
double dist(pair <long long,long long> A, pair <long long,long long> B)
{
double X=(A.first-B.first)*(A.first-B.first);
double Y=(A.second-B.second)*(A.second-B.second);
return sqrt(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];
}
double rec(int st, int dr)
{
int i,j;
double 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;
double qs=rec(st,m);
double 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<<rec(1,n)<<"\n";
return 0;
}