Pagini recente » Cod sursa (job #3293591) | Diferente pentru implica-te/arhiva-educationala intre reviziile 205 si 223 | Diferente pentru implica-te/arhiva-educationala intre reviziile 198 si 223 | Istoria paginii implica-te/arhiva-educationala | Cod sursa (job #3290484)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <limits.h>
using namespace std;
int n;
vector<pair<int, int>> points;
double dist(pair<int, int>& a, pair<int, int>& b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int bsearch1(vector<pair<int, int>>& v, int l, int r, double x) {
int res = r;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((double)v[mid].first >= x) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return res;
}
int bsearch2(vector<pair<int, int>>& v, int l, int r, double x) {
int res = l;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((double)v[mid].first <= x) {
l = mid + 1;
res = mid;
} else {
r = mid - 1;
}
}
return res;
}
double divide(int l, int r) {
if (l == r)
return INT_MAX;
if (r - l == 1)
return dist(points[l], points[r]);
int mid = l + (r - l) / 2;
double left = divide(l, mid);
double right = divide(mid + 1, r);
double d = min(left, right);
int leftest_left = bsearch1(points, l, mid, (double)points[mid].first - d);
int rightest_right = bsearch2(points, mid + 1, r, (double)points[mid].first + d);
sort(points.begin() + leftest_left, points.begin() + rightest_right + 1,
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
});
for (int i = leftest_left; i <= rightest_right; ++i) {
for (int j = i + 1; j <= i + 7 && j <= rightest_right; ++j) {
d = min(d, dist(points[i], points[j]));
}
}
return d;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> n;
points.resize(n);
for (int i = 0; i < n; ++i) {
fin >> points[i].first >> points[i].second;
}
sort(points.begin(), points.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first;
});
fout << fixed << setprecision(6) << divide(0, n - 1) << '\n';
return 0;
}