Pagini recente » Cod sursa (job #1268980) | Cod sursa (job #1542994) | Cod sursa (job #1264572) | Cod sursa (job #429117) | Cod sursa (job #1163068)
//dupa ideea O(nlogn) si codul lui Marius Stroe
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
typedef long long int LL;
typedef std::pair<LL,LL> PLL;
const LL INF=std::numeric_limits<LL>::max();
LL dist(PLL a, PLL b){ return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); }
std::vector<PLL> X,Y,temp;
LL get(unsigned st, unsigned dr){
if(st+1>=dr) return INF;
else if(dr-st==2){
if(Y[st]>Y[st+1]) Y[st].swap(Y[st+1]);
return dist(X[st],X[st+1]);
}
else{
unsigned mid=(st+dr)>>1;
LL best = std::min( get(st,mid), get(mid,dr) );
std::merge(Y.begin()+st, Y.begin()+mid, Y.begin()+mid, Y.begin()+dr, temp.begin());
std::copy(temp.begin(), temp.begin()+(dr-st), Y.begin()+st);
unsigned tsz=0;
for(unsigned i=st;i<dr;++i)
if(std::abs(Y[i].second-X[mid].first)<=best)
temp[tsz++]=Y[i];
for(unsigned i=0;i<tsz-1;++i)
for(unsigned j=i+1;j<tsz && j-i<8;++j)
best = std::min(best, dist(temp[i],temp[j]));
return best;
}
}
int main(){
std::freopen("cmap.in","r",stdin);
std::freopen("cmap.out","w",stdout);
unsigned n; std::scanf("%u",&n);
X.resize(n); Y.resize(n); temp.resize(n);
for(unsigned i=0;i<n;++i) std::scanf("%lld %lld",&X[i].first,&X[i].second);
std::sort(X.begin(),X.end());
for(unsigned i=0;i<n;++i){ Y[i].first=X[i].second; Y[i].second=X[i].first; }
std::printf("%.8Lf\n",std::sqrt(static_cast<long double>(get(0,n))));
}