Pagini recente » Cod sursa (job #1007480) | Cod sursa (job #2071277) | Cod sursa (job #2741766) | Cod sursa (job #497576) | Cod sursa (job #2913469)
#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<ld> P;
const ld eps = 1e-7;
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++) {
ld 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);
ld res = 2e9;
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, abs(A[j] - A[i]));
}
}
sort(A.begin() + l, A.begin() + r, cmpY);
return;
}
auto m = (r+l+1)/2;
ld 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 (abs(A[i].real() - X) < res + eps) {
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, abs(buf[i] - buf[j]));
}
}
};
go(go, 0, N);
cout << std::fixed << setprecision(6) << res << "\n";
return 0;
}