Pagini recente » Cod sursa (job #568027) | Cod sursa (job #1546308) | Cod sursa (job #2150296) | Cod sursa (job #2230709) | Cod sursa (job #2913505)
#include <algorithm>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef complex<ll> P;
ll square(ll x) { return x*x; }
int main(void) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int N;
cin >> N;
vector<P> A(N);
for(int i = 0; i < N; i++) {
ll x,y;
cin >> x >> y;
A[i] = {x,y};
}
auto cmpX = [](const P &a, const P &b){ return a.real() < b.real(); };
auto cmpY = [](const P &a, const P &b){ return a.imag() < b.imag(); };
sort(A.begin(), A.end(), cmpX);
ll res = 1e9 * 2ll * 1e9;
auto go = [&](auto self, int l, int r)->void {
if (r <= l + 3) {
for(int i = l; i < r; ++i) {
for(auto j = i+1; j < r; ++j) {
res = min(res, norm(A[j] - A[i]));
}
}
sort(A.begin() + l, A.begin() + r, cmpY);
return;
}
auto m = (r+l+1)/2;
ll X = A[m].real();
self(self, l, m);
self(self, m, r);
inplace_merge(A.begin() + l, A.begin() + m, A.begin() + r, cmpY);
vector<P> buf;
for(int i = l; i < r; i++) if (square(A[i].real() - X) <= res) {
buf.push_back(A[i]);
}
for(int i = 0; i < (int)buf.size(); i++) {
for(int j = i+1; j < (int)buf.size() && j < i+8; j++) {
res = min(res, norm(buf[i] - buf[j]));
}
}
};
go(go, 0, N);
cout << std::fixed << setprecision(6) << sqrt(res) << "\n";
return 0;
}