# Cod sursa(job #1828614)

Utilizator Data 13 decembrie 2016 17:25:17 Cele mai apropiate puncte din plan 100 cpp done Arhiva educationala 1.52 kb
``````#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

vector <pair<int,int> > v, w, rez, aux;
const int INF = 4e18;

long long get_dist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first) * 1LL * (a.first - b.first)  + (a.second - b.second) * 1LL * (a.second - b.second);
}

long long rezolva(int st, int dr)
{
if (st == dr)
return INF;
else if (dr - st == 1)
return get_dist(v[st], v[dr]);

int mid = (st+dr)/2;

long long sol = min(rezolva(st, mid), rezolva(mid, dr));

rez.clear();
rez.resize(dr + 1 - st + 1);
aux.clear();
merge(w.begin() + st, w.begin() + mid, w.begin() + mid, w.begin() + dr + 1, rez.begin());

vector <pair<int ,int> > ::iterator it;

for (it = rez.begin(); it != rez.end(); ++it)
{
if (abs(it->second - v[mid].first) <= sol)
aux.push_back(make_pair(it->second, it->first));
}

for (int i = 0; i < aux.size(); ++i)
for (int j = i + 1; j < aux.size() && j - i < 8; ++j) {
sol = min(sol, get_dist(aux[i], aux[j]));
}

return sol;
}

int main()
{
int x,y,n;

fin>>n;

for(int i = 0; i < n; i++)
{
fin>>x>>y;
v.push_back(make_pair(x,y));
w.push_back(make_pair(y,x));
}

sort(v.begin(),v.end());
w.push_back(make_pair(INF,INF));
sort(w.begin(),w.end());

fout<<fixed<<setprecision(6)<<sqrt(rezolva(0,v.size()-1));
}
``````