Pagini recente » Cod sursa (job #1009388) | Cod sursa (job #2232661) | Cod sursa (job #255511) | Cod sursa (job #2668005) | Cod sursa (job #630489)
Cod sursa(job #630489)
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#define sqr(a) (a)*(a)
#define dist(a,b) sqr(a.first-b.first)+sqr(a.second-b.second)
using namespace std;
vector<pair<long long,long long> > v,y,w(100100);
int n;
long long inf=4000000000000000LL;
long long dei(int s,int d) {
if(d-s<1)
return inf;
else if(d-s==1) {
if(y[s].first<y[d].first)
swap(y[s],y[d]);
return dist(v[s],v[d]);
}
int mij=(s+d)/2,i,nr=0,j;
long long best=min(dei(s,mij),dei(mij+1,d));
merge(y.begin()+s,y.begin()+mij,y.begin()+mij,y.begin()+d,w.begin());
copy(w.begin(),w.begin()+d-s,y.begin()+s);
for(i=s;i<=d;i++)
if(abs(y[i].second-v[mij].first)<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;
v.resize(n);
y.resize(n);
for(i=0;i<n;i++)
in>>v[i].first>>v[i].second;
sort(v.begin(),v.end());
for(i=0;i<n;i++)
y[i]=make_pair(v[i].second,v[i].first);
in.close();
}
int main() {
long long d;
citire();
d=dei(0,n-1);
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<sqrtl(d)<<'\n';
out.close();
return 0;
}