Pagini recente » Cod sursa (job #200583) | Cod sursa (job #3193724) | Cod sursa (job #1229391) | Cod sursa (job #3293772) | Cod sursa (job #3282858)
#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>> strip;
double divide( std::vector<std::pair<double, double>> &X,
std::vector<std::pair<double, double>> &Y, 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, Y, left, mid, d);
double d2 = divide(X, Y, mid, right, d);
d = std::min(d1, d2);
strip.clear();
for (auto p : Y) {
if (std::fabs(p.first - X[mid].first) < d) {
strip.push_back(p);
}
}
for (int i = 0; i < strip.size(); i++) {
for (int j = 1; j < 6 && i + j < strip.size(); j++) {
d = std::min(d, dist(strip[i], strip[i + j]));
}
}
return d;
}
static inline 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::ios_base::sync_with_stdio(false);
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});
}
std::vector<std::pair<double, double>> X = pairs, Y = pairs;
sort(X.begin(), X.end());
sort(Y.begin(), Y.end(), [](std::pair<double, double>& a, std::pair<double, double>& b) {
return a.second < b.second;
});
fout << std::fixed << std::setprecision(6) << (new Solution())->divide(X, Y, 0, X.size() - 1, INF);
}