Pagini recente » Cod sursa (job #363692) | Cod sursa (job #2388691) | Cod sursa (job #1972737) | Cod sursa (job #1342203) | Cod sursa (job #630457)
Cod sursa(job #630457)
#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)
#define inf 2100000000
using namespace std;
vector<pair<int,int> > v,y,w(100100);
int n;
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+1,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)
v[nr++]=y[i];
for(i=0;i<nr-1;i++)
for(j=i+1;j<i+8&&j<nr;j++)
best=min(best,1LL*dist(v[i],v[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;
y[i]=make_pair(v[i].second,v[i].first);
}
in.close();
}
int main() {
int d;
citire();
sort(v.begin(),v.end());
d=dei(0,n-1);
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<sqrtl(d)<<'\n';
out.close();
return 0;
}