Cod sursa(job #3239817)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 7 august 2024 18:32:23
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#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;
    const operator < (const point &a)const{
        return x < a.x;
    }
} a[N + 1], aux[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;
}

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);
    int st = l, dr = mid + 1, k = 0;
    while (st <= mid && dr <= r)
    {
        if (a[st].y < a[dr].y)
            aux[++k] = a[st++];
        else if (a[st].y > a[dr].y)
            aux[++k] = a[dr++];
        else
            aux[++k] = a[st++], aux[++k] = a[dr++];
    }
    while (st <= mid)aux[++k] = a[st], st++;
    while (dr <= r)aux[++k] = a[dr], dr++;
    for (int i = 1; i <= k; ++i)
        a[i + l - 1] = aux[i];
    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);
    cout << fixed << setprecision(6) << divide (1, n) << '\n';
    return 0;
}