Pagini recente » Cod sursa (job #526244) | Cod sursa (job #1477461) | Cod sursa (job #120839) | Cod sursa (job #2800820) | Cod sursa (job #933158)
Cod sursa(job #933158)
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair<LL,LL> > X,Y,V(100005);
LL n,oo=(1<<30);
void Read()
{
LL x,y;
fin>>n;
for(LL i=1;i<=n;i++)
{
fin>>x>>y;
X.push_back(make_pair(x,y));
}
sort(X.begin(),X.end());
for(LL i=0;i<n;i++)
Y.push_back(make_pair(X[i].second,X[i].first));
}
LL dist(pair<LL,LL> A,pair<LL,LL> B)
{
return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
LL Solve(LL s,LL d, vector < pair <LL, LL> >& X, vector < pair <LL, LL> >& Y)
{
if (s>=d-1)
return oo;
if(s+2==d)
{
if(Y[s]>Y[s+1])
swap(Y[s],Y[s+1]);
return dist(Y[s],Y[s+1]);
}
LL m=(s+d)/2;
LL best=min(Solve(s,m,X,Y),Solve(m,d,X,Y));
merge(Y.begin() + s, Y.begin() + m, Y.begin() + m, Y.begin() + d, V.begin());
copy(V.begin(), V.begin() + (d - s), Y.begin() + s);
LL SIZE=0;
for(LL i=s;i<d;i++)
if(abs(Y[i].second-X[m].first)<=best)
V[SIZE++]=Y[i];
for(size_t i=0;i<SIZE-1;i++)
for(size_t j=i+1;j<SIZE&&j-i<8;j++)
best=min(best,dist(V[i],V[j]));
return best;
}
int main()
{
Read();
fout.precision(7);
fout<<fixed<<sqrt(Solve(0,X.size(),X,Y));
return 0;
}