Pagini recente » Cod sursa (job #2962556) | Cod sursa (job #1065667) | Cod sursa (job #3130003) | Cod sursa (job #3261506) | Cod sursa (job #2999765)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int nmax = 1e5;
vector<pair<ll, ll>> v(nmax+5);
ll dist(pair<ll, ll> a, pair<ll, ll> b) {
return (a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second);
}
ll solve(int left, int right, vector<pair<ll, ll>>&x, vector<pair<ll, ll>>&y) {
if(left >= right-1) return inf;
if(right - left == 2) {
if(y[left] > y[left+1]) swap(y[left], y[left+1]);
return dist(x[left], x[left+1]);
}
int mid = (left + right) / 2;
ll best = min(solve(left, mid, x, y), solve(mid, right, x, y));
merge(y.begin() + left, y.begin() + mid, y.begin() + mid, y.begin() + right, v.begin());
copy(v.begin(), v.begin() + (right - left), y.begin() + left);
int temp = 0;
for(int i=left; i<right; i++)
if(abs(y[i].second - x[mid].first) <= best)
v[temp++] = y[i];
for(int i=0; i<temp-1; i++)
for(int j=i+1; j<temp and j-i < 8; j++)
best = min(best, dist(v[i], v[j]));
return best;
}
int main() {
ifstream f("cmap.in");
ofstream g("cmap.out");
int n; f >> n;
vector<pair<ll, ll>> x(n), y(n);
for(int i=0; i<n; i++) f >> x[i].first >> x[i].second;
sort(x.begin(), x.end());
for(int i=0; i<n; i++) y[i] = {x[i].second, x[i].first};
g << fixed << setprecision(6) << sqrt(solve(0, n, x, y));
return 0;
}