Pagini recente » Cod sursa (job #3293237) | Cod sursa (job #3247898) | Cod sursa (job #2176893) | Cod sursa (job #3274048) | Cod sursa (job #3282928)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#define INF 10000000
class Solution {
public:
std::vector<std::pair<double, double>> Y;
double divide(std::vector<std::pair<double, double>>& X, int left, int right, double d) {
if (right - left < 2) {
return INF;
}
if (right - left == 2) {
return dist(X[left], X[left + 1]);
}
int mid = (left + right) / 2;
double d1 = divide(X, left, mid, d);
double d2 = divide(X, mid, right, d);
d = std::min(d1, d2);
Y.clear();
for (int i = left; i < right; i++) {
if (fabs(X[i].first - X[mid].first) < d) {
Y.push_back(X[i]);
}
}
std::sort(Y.begin(), Y.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
double newDist = 0;
for (int i = 0; i < Y.size(); i++) {
for (int j = 1; j < 6 && i + j < Y.size(); j++) {
newDist = dist(Y[i], Y[i + j]);
if (newDist) {
d = std::min<double>(d, newDist);
}
}
}
// std::cout << d << '\n';
return d;
}
private:
double dist(std::pair<double, double>& a, std::pair<double, double>& b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
};
int main() {
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int n, x, y;
std::vector<std::pair<double, double>> pairs;
fin >> n;
for (int i = 0; i < n; i++) {
fin >> x >> y;
pairs.push_back({x, y});
}
sort(pairs.begin(), pairs.end());
Solution solution;
fout << std::fixed << std::setprecision(6) << solution.divide(pairs, 0, n, INF);
}