Pagini recente » Istoria paginii utilizator/tzancauraganufacepblainfo | Cod sursa (job #706088) | Cod sursa (job #1568115) | Cod sursa (job #1531377) | Cod sursa (job #1690872)
#define pdd std::pair<double, double>
#include <fstream>
#include <set>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <limits>
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
struct by_y {
bool operator()(const pdd a, const pdd b) const {
return a.second != b.second ? a.second < b.second : a.first < b.first;
}
};
double getDistance(const pdd a, const pdd b) {
return std::sqrt((a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second));
}
int main() {
int N;
fin >> N;
std::set<pdd, by_y> candidates;
std::vector<pdd> pointsSorted;
for (int i = 0; i < N; i++) {
int a, b;
fin >> a >> b;
pointsSorted.push_back({ a, b });
}
std::sort(pointsSorted.begin(), pointsSorted.end());
double minDistance = std::numeric_limits<double>::infinity();
std::vector<pdd>::iterator leftMost = pointsSorted.begin();
for (std::vector<pdd>::iterator it = pointsSorted.begin(); it != pointsSorted.end(); it++) {
pdd current = *it;
while (current.first - leftMost->first > minDistance) {
candidates.erase(*leftMost);
leftMost++;
}
std::set<pdd, by_y>::iterator rangeFrom = candidates.lower_bound(std::make_pair(current.first, current.second - minDistance));
std::set<pdd, by_y>::iterator rangeEnd = candidates.upper_bound(std::make_pair(current.first, current.second + minDistance));
for (std::set<pdd, by_y>::iterator it1 = rangeFrom; it1 != rangeEnd; it1++) {
double tempDistance = getDistance(current, *it1);
if (tempDistance < minDistance) {
minDistance = tempDistance;
}
}
candidates.insert(current);
}
fout << std::fixed << std::setprecision(6) << minDistance << "\n";
return 0;
}