Cod sursa(job #3182603)

Utilizator SilviuIIon Silviu SilviuI Data 9 decembrie 2023 10:57:05
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#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){
        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 + 7); 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;
}