Pagini recente » Cod sursa (job #1120178) | Cod sursa (job #1620768) | Cod sursa (job #658860) | Cod sursa (job #1589530) | Cod sursa (job #673664)
Cod sursa(job #673664)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define NMAx 100100
#define ff first
#define ss second
#define oo (1<<30)
#define pp(a) (a)*(a)
#define dist(a,b) sqrt(pp(a.ff-b.ff)+pp(a.ss-b.ss))
using namespace std;
pair<double,double > V[NMAx],Y[NMAx],w[NMAx];
int n,nr;
double dei(int left,int right) {
if(left==right)
return oo;
else if(right-left==1) {
if(Y[left].ff>Y[right].ff)
swap(Y[left],Y[right]);
return dist(V[left],V[right]);
}
int i,j,mid=(left+right)>>1;
double best;
best=min(dei(left,mid),dei(mid,right));
merge(Y+left,Y+mid,Y+mid,Y+right,w);
copy(w,w+(right-left),Y+left);
for(i=left,nr=0;i<=right;i++)
if(abs(Y[i].ss-V[mid].ff)<=best)
w[nr++]=Y[i];
for(i=0;i<nr-1;i++)
for(j=i+1;j<i+8&&j<nr;j++)
best=min(best,dist(w[i],w[j]));
return best;
}
void citire() {
int i;
ifstream in("cmap.in");
in>>n;
for(i=0;i<n;i++)
in>>V[i].ff>>V[i].ss;
sort(V,V+n);
for(i=0;i<n;i++)
Y[i]=make_pair(V[i].ss,V[i].ff);
in.close();
}
int main() {
citire();
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<dei(0,n-1)<<'\n';
out.close();
return 0;
}