Cod sursa(job #3239813)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 7 august 2024 18:10:03
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
///pentru simplitate poti lua toate punctele la distanta <= d, necontand partea si sa verifici primele 8 in sus sau ceva

#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>

#define double long double

using namespace std;

ifstream cin ("cmap.in");
ofstream cout ("cmap.out");

const double MAX = (double)(4e18);
const int N = 1e5;

struct point
{
    int x, y;
} a[N + 1];

int n, bulan = 8;

double dist (point a, point b)
{
    return sqrt(((double)(a.x - b.x) * (double)(a.x - b.x) + (double)(a.y - b.y) * (double)(a.y - b.y)));
}

inline double ab (double x)
{
    if (x < 0)return -x;
    return x;
}

bool cmp (const point &a, const point &b)
{
    return a.y < b.y;
}

double divide (int l, int r)
{
    if (l == r)
        return MAX;
    int mid = (l + r) >> 1;
    double left_ans = divide (l, mid);
    double right_ans = divide (mid + 1, r);
    double d = min (left_ans, right_ans);
    double center = (double)a[mid].x;
    for (int i = l; i <= mid; ++i)
        center = max (center, (double)a[i].x);
    sort (a + l, a + r + 1, cmp);
    vector <point> p;
    for (int i = l; i <= r; ++i)
        if (ab (center - a[i].x) <= d)
            p.push_back(a[i]);
    for (int i = 0; i < p.size(); ++i)
        for (int j = i + 1; j < min (i + bulan, (int)(p.size())); ++j)
        {
            if (d > dist (p[i], p[j]))
                d = dist (p[i], p[j]);
        }
    return d;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].y;
    sort (a + 1, a + n + 1, [](const point &a, const point &b)
    {
        return a.x < b.x;
    });
    cout << fixed << setprecision(6) << divide (1, n) << '\n';
    return 0;
}