Pagini recente » Cod sursa (job #2790258) | Cod sursa (job #1173148) | Cod sursa (job #2648766) | Cod sursa (job #1218719) | Cod sursa (job #781525)
Cod sursa(job #781525)
#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;
else if(dr-st==2){
sort(Y+st,Y+dr);
return Dist(X[st],X[st+1]);
}
int mij=(st+dr)/2,i,j,size;
double distanta=min(Divide_et_Impera(st,mij),Divide_et_Impera(mij,dr));
merge(Y+st,Y+mij,Y+mij,Y+dr,Z);
copy(Z,Z+dr-st,Y+st);
size=0;
for(i=st;i<dr;i++){
if(abs(Y[i].second-X[mij].first)<=distanta)
v[size++]=Y[i];
}
for(i=0;i<size;i++)
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;
}