Pagini recente » Cod sursa (job #3253530) | Cod sursa (job #1836047) | Cod sursa (job #2248263) | Cod sursa (job #3191772) | Cod sursa (job #3290450)
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> p;
double sq(double x) {
return x * x;
}
double dist(pair<int, int> a, pair<int, int> b) {
return sqrt(sq(((double)(a.first - b.first))) + sq(((double)(a.second - b.second))));
}
int smallest_bigger(int l, int r, double x) {
int res = l;
while(l <= r) {
int mid = (r - l) / 2 + l;
if ((double) p[mid].first >= x) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return res;
}
int biggest_smaller(int l, int r, double x) {
int res = r;
while(l <= r) {
int mid = (r - l) / 2 + l;
if ((double) p[mid].first <= x) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
double divide(int l, int r)
{
if (r == l)
return INT_MAX;
if (r == l + 1)
return dist(p[l], p[r]);
int mid = (r - l) / 2 + l;
double d1 = divide(l, mid);
double d2 = divide(mid + 1, r);
double d = min(d1, d2);
// cautam cel mai mic nr > p[mid] - d
int p1 = smallest_bigger(l, mid, (double)p[mid].first - d);
// cautam cel mai mare nr < p[mid] + d
int p2 = biggest_smaller(mid + 1, r, (double)p[mid].first + d);
// sortare dupa y
auto comp = [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
};
sort(p.begin() + p1, p.begin() + p2 + 1, comp);
for (int i = p1; i <= p2; ++i) {
for (int j = 1; j <= 6 && j + i <= p2; ++j)
d = min(d, dist(p[i], p[i + j]));
}
return d;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin >> n;
p.resize(n);
for (int i = 0; i < n; ++i)
fin >> p[i].first >> p[i].second;
auto comp = [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first == b.first ? a.second < b.second : a.first < b.first;
};
sort(p.begin(), p.end(), comp);
fout << fixed << setprecision(6) << divide(0, n - 1);
}