Pagini recente » Cod sursa (job #2287579) | Cod sursa (job #2166656) | Cod sursa (job #1644848) | Cod sursa (job #2225664) | Cod sursa (job #631256)
Cod sursa(job #631256)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
pair<double,double > v[100100],y[100100],w[100100];
int n,i,j,nr;
double inf=2<<29,best,best2;
inline double dist2(pair<double,double> a,pair<double,double> b) {
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
inline double dei(int s,int d) {
if(s==d)
return inf;
else if(d-s==1) {
if(y[s].first<y[d].first)
swap(y[s],y[d]);
return dist2(v[s],v[d]);
}
int mij=(s+d)/2;
best=min(dei(s,mij),dei(mij+1,d));
merge(y+s,y+mij,y+mij,y+d,w);
copy(w,w+(d-s),y+s);
for(i=s,nr=0,best2=best;i<=d;i++)
if(abs(y[i].second-v[mij].first)<best2)
w[nr++]=y[i];
//best2=min(best2,abs(y[i].second-v[mij].first));
for(i=0;i<nr-1;i++)
for(j=i+1;j<i+8&&j<nr;j++)
best=min(best,dist2(w[i],w[j]));
return best;
}
void citire() {
ifstream in("cmap.in");
in>>n;
for(i=0;i<n;i++)
in>>v[i].first>>v[i].second;
sort(v,v+n);
for(i=0;i<n;i++)
y[i]=make_pair(v[i].second,v[i].first);
in.close();
}
int main() {
citire();
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<dei(0,n-1)<<'\n';
out.close();
return 0;
}