Cod sursa(job #2974411)

Utilizator IanisBelu Ianis Ianis Data 4 februarie 2023 01:44:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif

typedef int64_t ll;

const int NMAX = 1e5+5;
const ll INF = 4e18;

struct Point {
    int x, y;
    bool operator<(const Point &p) {
        return y < p.y || (y == p.y && x < p.x);
    } 
    bool operator>(const Point &p) {
        return !(*this < p);
    }
};

int n;
Point a[NMAX], aux[NMAX], v[NMAX];

ll dist(const Point &a, const Point &b) {
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return 1ll * dx * dx + 1ll * dy * dy;
}

void read() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
}

bool cmp(const Point &a, const Point &b) {
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void merge(int l, int r) {
    for (int i = l; i <= r; i++)
        aux[i] = a[i];
    int mid = (l + r) / 2;
    int i = l;
    int j = mid + 1;
    int last = l;
    while (i <= mid && j <= r) {
        if (aux[i] < aux[j])
            a[last++] = aux[i], i++;
        else
            a[last++] = aux[j], j++;
    }
    for (; i <= mid; i++)
        a[last++] = aux[i];
    for (; j <= r; j++)
        a[last++] = aux[j];
}

ll divide(int l, int r) {
    if (l >= r)
        return INF;
    int len = r - l + 1;
    if (len <= 2) {
        if (a[l] > a[l + 1])
            swap(a[l], a[l + 1]);
        return dist(a[l], a[l + 1]);
    }
    
    int mid = (l + r) / 2;
    ll s = min(divide(l, mid), divide(mid + 1, r));
    
    merge(l, r);

    int vcnt = 0;
    for (int i = l; i <= r; i++)
        if (abs(a[i].x - a[mid].x) <= s)
            v[++vcnt] = a[i];

    for (int i = 1; i <= vcnt; i++)
        for (int j = i + 1; j <= vcnt && (j - i) < 8; j++) {
            s = min(s, dist(v[i], v[j]));
        }

    return s;
}

int main() {
    read();
    sort(a + 1, a + n + 1, cmp);
    fout << setprecision(6) << fixed << sqrt(divide(1, n));
    return 0;
}