Pagini recente » Cod sursa (job #3293708) | Diferente pentru implica-te/arhiva-educationala intre reviziile 222 si 223 | Istoria paginii implica-te/arhiva-educationala | Diferente pentru implica-te/arhiva-educationala intre reviziile 189 si 223 | Cod sursa (job #3292292)
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;
ifstream fin("cmap.in");
double dist(pair<int, int> a, pair<int, int> b)
{
return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}
bool compX(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
bool compY(pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
double median(vector<pair<int, int>> &points, int start, int end)
{
int mid = (start + end) / 2;
double l = (double)(points[mid].first + points[mid + 1].first) / 2.0;
return l;
}
double min_dist(vector<pair<int, int>> &points, int start, int end)
{
if (end - start == 1) {
return DBL_MAX;
}
if (end - start == 2) {
return dist(points[start], points[end - 1]);
}
int mid = (start + end) / 2;
double d1 = min_dist(points, start, mid);
double d2 = min_dist(points, mid, end);
double minimum = min(d1, d2);
vector<pair<int, int>> closer_to_median;
double mid_ = median(points, start, end);
for (int i = start; i < end; i++) {
if (points[i].first - mid_ < minimum) {
closer_to_median.push_back(points[i]);
}
}
sort(closer_to_median.begin(), closer_to_median.end(), compY);
for (int i = 0; i < closer_to_median.size(); i++) {
for (int j = 1; j < 6 && i + j < closer_to_median.size(); j++) {
if (dist(closer_to_median[i], closer_to_median[i + j]) < minimum) {
minimum = dist(closer_to_median[i], closer_to_median[i + j]);
}
}
}
return minimum;
}
int main()
{
int n;
fin >> n;
vector<pair<int, int>> points(n);
for (int i = 0; i < n; i++) {
fin >> points[i].first >> points[i].second;
}
FILE* f = fopen("cmap.out", "w");
sort(points.begin(), points.end(), compX);
fprintf(f, "%.6f", min_dist(points, 0, n));
}