Pagini recente » Cod sursa (job #610299) | Cod sursa (job #1121223) | Cod sursa (job #401573) | Cod sursa (job #69109) | Cod sursa (job #871137)
Cod sursa(job #871137)
#include<fstream>
using namespace std;
#include<vector>
#include<utility>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define INF 100000
ifstream cin("cmap.in");
ofstream cout("cmap.out");
typedef pair<double,double> punct;
typedef vector< punct > vp;
typedef vp::iterator vpit;
vp P; //vectorul punctelor din plan
//functia de comparare a absciselor (pentru sortare)
bool lessx(punct p1, punct p2){
return p1.first<p2.first;
};
//calculul distantei intre doua puncte
double dist(punct p1, punct p2){
return sqrt((p2.first-p1.first)*(p2.first-p1.first)+(p2.second-p1.second)*(p2.second-p1.second));
};
//selecteaza in R punctele din P situate inm banda
// (xmed-d. xmed+d)
void selx(vpit l, vpit r, double d, double xmed, vp& R){
for(vpit i=l; i!=r+1; i++)
if(fabs((*i).first-xmed)<d) R.push_back(*i);
};
//determina distanta minima intre 2 puncte R considerand
//cel mult 7 puncte
double sely(const vp& R, double d){
int n=R.size();
double dm=d;
for(int j=0;j<n;j++)
for(int k=j+1; k<min(n, j+7); k++)
{ punct p1=R[j];
punct p2=R[k];
dm=min(dm, dist(p1, p2));
}
return dm;
};
double dMin(vpit l, vpit r)
{ double d;
if(l==r)
d=INF;
else
{
vpit m=l+(r-l)/2;
double dl=dMin(l, m);
double dr=dMin(m+1, r);
d=min(dl,dr);
inplace_merge(l, m, r);
vp R;
selx(l, r, d, (*m).first, R);
d=sely(R, d);
}
return d;
};
int main ()
{
int n;
cin>>n;
P.resize(n);
for(int i=0;i<n;i++)
cin>>P[i].first>>P[i].second;
sort(P.begin(), P.end());
double d=dMin(P.begin(), P.end());
cout<<fixed<<setprecision(6)<<d<<endl;
// system("pause");
return 0;
}