# Cod sursa(job #2046406)

Utilizator Data 23 octombrie 2017 19:46:38 Cele mai apropiate puncte din plan 0 cpp done Arhiva educationala 1.25 kb
``````#include <bits/stdc++.h>
#define ll long long
#define NMAX 100005
#define pr pair<int, int>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

inline ll dist(int a, int b, pr v[])
{
return (v[a].first - v[b].first) * (v[a].first - v[b].first) + (v[a].second - v[b].second) * (v[a].second - v[b].second);
}

inline ll distPr(pr a, pr b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

ll dei(int left, int right, pr v[])
{
if(right - left == 2)
return dist(left, left + 1, v);
else if (right - left == 3)
return min(dist(left, left + 1, v), min(dist(left, left + 2, v), dist(left + 1, left + 2, v)));
vector<pr> w;
int mid = (left + right) / 2;
ll best = min(dei(left, mid, v), dei(mid, right, v));
int y = v[mid].first;
int k = 0;
for (int i = left; i < right; i++)
if (abs(v[i].first - v[mid].first) <= best)
w.push_back(v[i]);
for(unsigned i = 0; i < w.size(); i++)
for(unsigned j = 1; i + j < w.size() && j <= 8; j++)
best = min(distPr(w[i], w[i + j]), 1LL * best);
return best;
}

int main()
{
pair<int, int> v[NMAX];
int n;
f>>n;
for(int i = 0; i < n; i++)
f>>v[i].first>>v[i].second;
sort(v, v + n);
g<<fixed<<setprecision(6)<<sqrt(dei(0, n, v));
return 0;
}

``````