Pagini recente » Cod sursa (job #2593280) | Cod sursa (job #756808) | Cod sursa (job #1560851) | Cod sursa (job #2842258) | Cod sursa (job #473525)
Cod sursa(job #473525)
#include<iomanip>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define NMAX 100003
typedef long long ll;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
vector < pair<ll,ll> > px,py,pv(NMAX);
int n,i;
ll distP(const pair<ll,ll> &p1, const pair<ll,ll> &p2) {
return (p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second);
}
ll dmin(int l,int r) {
ll best;
int i,j;
if(r-l<=2) {
best=distP(px[l],px[l+1]);
if(r-l==2) best=min(best,min(distP(px[l],px[r]),distP(px[l+1],px[r])));
sort(py.begin()+l,py.begin()+r+1);
}
else {
int mid=(l+r)/2;
best=min(dmin(l,mid),dmin(mid+1,r));
merge(py.begin()+l,py.begin()+mid+1,py.begin()+mid+1,py.begin()+r+1,pv.begin());
copy(pv.begin(),pv.begin()+(r-l+1),py.begin()+l);
int nv=0;
for(i=l;i<=r;i++)
if(abs(px[mid].first-py[i].second)<=best) pv[nv++]=py[i];
for(i=0;i<nv-1;i++)
for(j=i+1;j<=i+7 && j<nv;j++)
best=min(best,distP(pv[i],pv[j]));
}
return best;
}
int main() {
fi>>n;
px.resize(n);
py.resize(n);
for(i=0;i<n;i++) fi>>px[i].first>>px[i].second;
sort(px.begin(),px.end());
for(i=0;i<=n;i++) py[i]=make_pair(px[i].second,px[i].first);
fo<<fixed<<setprecision(7)<<sqrt(dmin(0,n-1))<<"\n";
return 0;
}