Pagini recente » Cod sursa (job #417660) | Cod sursa (job #1923546) | Cod sursa (job #1668783) | Cod sursa (job #768058) | Cod sursa (job #2321394)
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
// X - vector sortat crescator dupa abscisa
// Y - vector sortat crescator dupa ordonata
vector< pair< int, int > > X, Y;
double dist(const pair< int, int > &a, const pair< int, int > &b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double distMin(const vector< pair< int, int > > &X, const vector< pair< int, int > > &Y, int left, int right) {
if (right - left + 1 == 2) {
return dist(X[left], X[right]);
}
if (left == right) {
return 1e9;
}
int mid = (left + right) / 2;
vector< pair< int, int > > leftY, rightY;
for (auto it: Y) {
if (it.first <= X[mid].first) {
leftY.push_back(it);
} else {
rightY.push_back(it);
}
}
double d1 = distMin(X, leftY, left, mid);
double d2 = distMin(X, rightY, mid + 1, right);
double d = min(d1, d2);
vector< pair< int, int > > LY;
for (auto it: Y) {
if (X[mid].first - d <= it.first && it.first <= X[mid].first + d) {
LY.push_back(it);
}
}
double d3 = 1e9;
for (int i = 0; i < (int)LY.size(); ++i) {
for (int j = i + 1; j < i + 7; ++j) {
if (j < (int)LY.size()) {
d3 = min(d3, dist(LY[i], LY[j]));
}
}
}
return min(d, d3);
}
int main() {
ios::sync_with_stdio(false); in.tie(0); out.tie(0);
int n; in >> n;
X.resize(n); Y.resize(n);
for (int i = 0; i < n; ++i) {
in >> X[i].first >> X[i].second;
Y[i] = X[i];
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end(), [&](const pair< int, int > &a, const pair< int, int > &b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
});
double ans = distMin(X, Y, 0, n - 1);
out << fixed << setprecision(6) << ans << "\n";
in.close(); out.close();
return 0;
}