Pagini recente » Cod sursa (job #1567936) | Cod sursa (job #2583843) | Cod sursa (job #3208454) | Cod sursa (job #2612464) | Cod sursa (job #3182607)
#include <set>
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#define INF 1e9
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
double sq(const int &x) { return x * x; }
double dist(const pii &point_a, const pii &point_b)
{
return sqrt(sq(point_a.first - point_b.first) + sq(point_a.second - point_b.second));
}
double brute_force_closest_distance(vector <pii> &points, int l, int r)
{
double min_distance = 5e9;
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++)
min_distance = min(min_distance, dist(points[i], points[j]));
return min_distance;
}
double closest_distance(vector <pii> &points, int l, int r)
{
if (r - l + 1 <= 3)
{
return brute_force_closest_distance(points, l, r);
}
int m = (r + l) / 2;
double d1 = closest_distance(points, l, m);
double d2 = closest_distance(points, m + 1, r);
double d = min(d1, d2);
vector <pii> d_range_points;
// x coord. has to be between m - d & m + d
for (int i = l; i <= r; i++)
if (points[i].first >= points[m].first - d && points[i].first <= points[m].first + d)
{
d_range_points.push_back(points[i]);
}
sort(d_range_points.begin(), d_range_points.end(), [&](const pii &a, const pii &b){
if (a.second == b.second) return a.first < b.first; else
return a.second < b.second;
});
int d_range_points_sz = (int)d_range_points.size();
for (int i = 0; i < d_range_points_sz; i++)
for (int j = i + 1; j < min(d_range_points_sz, i + 8); j++)
d = min(d, dist(d_range_points[i], d_range_points[j]));
return d;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int n;
cin >> n;
vector <pii> points(n);
for (int i = 0; i < n; i++) cin >> points[i].first >> points[i].second;
sort(points.begin(), points.end());
cout << setprecision(7) << fixed;
cout << closest_distance(points, 0, n - 1);
return 0;
}