Pagini recente » Cod sursa (job #2697330) | Cod sursa (job #2832670) | Cod sursa (job #143153) | Cod sursa (job #3276396) | Cod sursa (job #3282917)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#define INF 100000000
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[0], X[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);
// impera
for (int i = mid - 3; i < mid + 3; i++) {
if (fabs(X[mid].first - X[i].first) < d) {
strip.push_back(X[i]);
}
}
for (int i = 0; i < strip.size(); i++) {
for (int j = 0; j < 6 && i + j < strip.size(); j++) {
double newDist = dist(strip[i], strip[i + j]);
if (newDist) {
d = std::min<double>(d, newDist);
}
}
}
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});
}
std::vector<std::pair<double, double>> pairsY = pairs;
sort(pairs.begin(), pairs.end());
fout << std::fixed << std::setprecision(6) << (new Solution())->divide(pairs, pairsY, 0, n, INF);
}