Pagini recente » Cod sursa (job #1091724) | Cod sursa (job #2177268) | Cod sursa (job #2176933) | Cod sursa (job #235030) | Cod sursa (job #3282925)
#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();
// std::cout << "Y: (pentru " << left << ' ' << right << ")\n";
for (int i = std::max(left, mid - 3); i < std::min(mid + 3, right); i++) {
if (fabs(X[i].first - X[mid].first) < d) {
Y.push_back(X[i]);
// std::cout << '{' << X[i].first << ' ' << X[i].second << "} ";
}
}
// std::cout << '\n';
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);
}