Pagini recente » Cod sursa (job #2927561) | Cod sursa (job #613926) | Cod sursa (job #1412686) | Cod sursa (job #2246677) | Cod sursa (job #650717)
Cod sursa(job #650717)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#define PDD pair<double,double>
#define MP make_pair
#define st first
#define nd second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const double INF = 2e9;
int N;
vector < PDD > V(100005), X, Y;
double dist(const PDD &x,const PDD &y)
{
return sqrt((x.st - y.st) * (x.st - y.st) + (x.nd - y.nd) * (x.nd - y.nd));
}
double solve(int st,int dr)
{
if(dr - st == 1)
return INF;
else if(dr - st == 2)
{
if(Y[st] > Y[st + 1])
swap(Y[st],Y[st + 1]);
return dist(X[st],X[st + 1]);
}
int mid = (st + dr)/2 , v_sz = 0;
double bst = min(solve(st,mid),solve(mid,dr));
sort(Y.begin() + st,Y.begin() + dr);
for(int i = st;i<dr;++i)
if(abs(Y[i].nd - X[mid].st)<=bst) V[v_sz++] = Y[i];
for(int i = 0;i<v_sz;++i)
for(int j = i + 1;j<v_sz && j - i <8;++j)
bst = min(bst,dist(V[i],V[j]));
return bst;
}
int main()
{
fin>>N;
X.resize(N) , Y.resize(N);
for(int i = 0;i<N;++i)
fin>>X[i].st>>X[i].nd;
sort(X.begin(),X.end());
for(int i = 0;i<N;++i)
Y[i] = MP(X[i].nd,X[i].st);
fout<<fixed<<setprecision(6)<<solve(0,X.size());
return 0;
}