Pagini recente » Rating andreev (nastinka) | Cod sursa (job #186247) | Cod sursa (job #1997421) | Cod sursa (job #1817797) | Cod sursa (job #2913518)
#include <algorithm>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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(auto &p: A) {
ll x,y;
cin >> x >> y;
p = {x,y};
}
sort(A.begin(), A.end(), [](const P &a, const P &b){ return a.real() < b.real(); });
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(int j = i+1; j < r; ++j) {
res = min(res, norm(A[i]- A[j]));
}
}
sort(A.begin() + l, A.begin() + r, [](const P &a, const P &b){ return a.imag() < b.imag(); });
return;
}
int 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, [](const P &a, const P &b){
return a.imag() < b.imag();
});
{
vector<P> buffer(8);
for(int i = l, buf_start = 0, buf_end = 0; true;) {
while(i < r && buf_end < buf_start + 8) {
if (square(A[i].real() - X) <= res) {
buffer[buf_end & 7] = A[i];
buf_end++;
}
i++;
}
for(int ti = buf_start + 1; ti < buf_end; ti++) {
res = min(res, norm(buffer[buf_start & 7] - buffer[ti & 7]));
}
buf_start++;
if (buf_start >= buf_end) break;
}
}
};
go(go, 0, N);
cout << fixed << setprecision(6) << sqrt(res) << "\n";
return 0;
}