Pagini recente » Cod sursa (job #2373547) | Cod sursa (job #1952773) | Cod sursa (job #3158003) | Cod sursa (job #2921878) | Cod sursa (job #721305)
Cod sursa(job #721305)
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int n;
double sol,infinit=100000000000000001.0;
typedef pair<double,double> Punct;
Punct X[100100],Y[100100],Z[100100];
Punct v[100100];
inline void Citire()
{
int i;
freopen("cmap.in","r",stdin);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf %lf",&X[i].first,&X[i].second);
}
}
inline double Dist(Punct A,Punct B)
{
return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}
inline double Divide_et_Impera(int st,int dr)
{
if(st>=dr-1)
return infinit;
// IMPERA
if(dr-st==2)
{
sort(Y+st,Y+st+1);
return Dist(X[st],X[st+1]);
}
// DIVIDE
int mij=(st+dr)/2,i,j,size;
double distanta=min(Divide_et_Impera(st,mij),Divide_et_Impera(mij,dr));
// MERGE
merge(Y+st,Y+mij,Y+mij,Y+dr,Z);
// COPY
copy(Z,Z+dr-st,Y+st);
// SELECTARE BANDA DE LATIME 2*distanta
size=0;
for(i=st;i<dr;i++)
{
//daca punctul se afla la distanta mai mica decat "distanta" de mijloc
//atunci intra in banda de latime 2*distanta
if(abs(Y[i].second-X[mij].first)<=distanta)
v[size++]=Y[i];
}
for(i=0;i<size;i++)
{
//in dreptunghiul format din 2 patrate de distanta*distanta
//am maxim 8 puncte de luat in calcul,pe Z[i] si inca maxim 7
for(j=i+1;j<size && j-i<8;j++)
{
distanta=min(distanta,Dist(v[i],v[j]));
}
}
return distanta;
}
inline void Rezolvare()
{
int i;
sort(X,X+n);
for(i=0;i<n;i++)
Y[i]=make_pair(X[i].second,X[i].first);
sol=Divide_et_Impera(0,n);
}
inline void Afisare()
{
freopen("cmap.out","w",stdout);
printf("%.6lf\n",sol);
}
int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}