Pagini recente » Cod sursa (job #1849683) | Cod sursa (job #1103333) | Cod sursa (job #820105) | Cod sursa (job #1049750) | Cod sursa (job #933186)
Cod sursa(job #933186)
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#define LL long long
#define left Y.begin()+s
#define middle Y.begin()+m
#define right Y.begin()+d
#define PAIR pair<LL,LL>
using namespace std;
vector <PAIR> X,Y,V(100005);
int n;
LL oo=(1LL<<62);
void read()
{
ifstream fin("cmap.in");
LL x,y;
fin>>n;
for(LL i=0;i<n;i++)
{
fin>>x>>y;
X.push_back(make_pair(x,y));
}
sort(X.begin(),X.end());
for(int i=0;i<n;i++)
Y.push_back(make_pair(X[i].second,X[i].first));
fin.close();
}
inline LL dist(PAIR A,PAIR B)
{
return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
inline LL solve(LL s,LL d,vector<PAIR> &X,vector<PAIR> &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]);
}
int m=(s+d)/2;
LL best=min(solve(s,m,X,Y),solve(m,d,X,Y));
merge(left,middle,middle,right,V.begin());
copy(V.begin(),V.begin()+(d-s),left);
size_t SIZE=0;
for(int 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();
ofstream fout("cmap.out");
fout.precision(7);
fout<<fixed<<sqrt(double(solve(0,X.size(),X,Y)));
fout.close();
return 0;
}