Pagini recente » Cod sursa (job #3281384) | Cod sursa (job #3187568) | Cod sursa (job #2149702) | Cod sursa (job #2432053) | Cod sursa (job #3281506)
#include <algorithm>
#include <fstream>
#include <vector>
#include <cmath>
#include <float.h>
#include <iomanip>
#pragma GCC optimize("Ofast,unroll-loops")
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
bool cmpx(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.first < b.first;
}
bool cmpy(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.second;
}
double distanta(const std::pair<int, int>& p1, const std::pair<int, int>& p2) {
double dx = p1.first - p2.first;
double dy = p1.second - p2.second;
return sqrt(dx * dx + dy * dy);
}
double caz_de_baza(const std::vector<std::pair<int, int>>& v, double d) {
double mindist = d;
int size = v.size();
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
double dist = distanta(v[i], v[j]);
mindist = std::min(mindist, dist);
}
}
return mindist;
}
double apropiate_zona(const std::vector<std::pair<int, int>>& v, double d) {
double mindist = d;
int size = v.size();
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size && (v[j].second - v[i].second) < mindist; j++) {
mindist = std::min(mindist, distanta(v[i], v[j]));
}
}
return mindist;
}
double apropiate(const std::vector<std::pair<int, int>>& v, int left, int right, double mindist) {
if (right - left <= 2) {
return caz_de_baza({v.begin() + left, v.begin() + right}, mindist);
}
int mid = (left + right) / 2;
double d1 = apropiate(v, left, mid, mindist);
double d2 = apropiate(v, mid + 1, right, mindist);
double currentmind = std::min(d1, d2);
std::vector<std::pair<int, int>> strip;
for (int i = left; i < right; i++) {
if (std::abs(v[i].first - v[mid].first) < currentmind) {
strip.push_back(v[i]);
}
}
return std::min(currentmind, apropiate_zona(strip, currentmind));
}
int main() {
int n;
fin >> n;
if (n < 2) {
fout << "Insufficient points to calculate distance\n";
return 0;
}
std::vector<std::pair<int, int>> v(n);
for (int i = 0; i < n; i++) {
fin >> v[i].first >> v[i].second;
}
std::sort(v.begin(), v.end(), cmpx);
fout << std::setprecision(8) << apropiate(v, 0, n, DBL_MAX);
return 0;
}