Pagini recente » Cod sursa (job #2258644) | Cod sursa (job #1325791) | Cod sursa (job #3218448) | Cod sursa (job #1937015) | Cod sursa (job #673663)
Cod sursa(job #673663)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define NMAx 100100
#define ff first
#define ss second
#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) {
double best;
if(right-left<=2) {
best=dist(V[left],V[right]);
if(right-left==2) {
best=min(best,dist(V[left],V[left+1]));
best=min(best,dist(V[left+1],V[right]));
}
sort(Y+left,Y+right);
return best;
}
int i,j,mid=(left+right)>>1;
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;
}