Cod sursa(job #2891010)

Utilizator ViAlexVisan Alexandru ViAlex Data 17 aprilie 2022 12:47:16
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<iomanip>
#include<cmath>

using namespace std;

const long long inf = 2e18 + 100;
struct position {
    int x, y;
};

struct node {
    position value;
    node *l, *r;

    explicit node(position _value) : value(_value), l(nullptr), r(nullptr) {

    }

    ~node() {
        delete l;
        delete r;
    }
};

long long distance(const position &a, const position &b) {
    long long diff_x = a.x - b.x;
    long long diff_y = a.y - b.y;
    return diff_x * diff_x + diff_y * diff_y;
}


node *root;

void insert(node *&here, position p, int depth) {
    if (here == nullptr) {
        here = new node(p);
    } else {
        bool go_left;
        if (depth % 2 == 0) {
            go_left = p.x <= here->value.x;
        } else {
            go_left = p.y <= here->value.y;
        }

        if (go_left) {
            insert(here->l, p, depth + 1);
        } else {
            insert(here->r, p, depth + 1);
        }
    }
}

long long nearest_neighbour(node *here, position p, int depth) {
    if (here == nullptr) {
        return inf;
    } else {

        bool go_left;
        if (depth % 2 == 0) {
            go_left = p.x <= here->value.x;
        } else {
            go_left = p.y <= here->value.y;
        }

        long long minimum;
        if (go_left) {
            minimum = nearest_neighbour(here->l, p, depth + 1);
        } else {
            minimum = nearest_neighbour(here->r, p, depth + 1);
        }

        minimum = min(minimum, distance(here->value, p));

        long long distance;
        if (depth % 2 == 0) {
            distance = p.x - here->value.x;
        } else {
            distance = p.y - here->value.y;
        }

        if (distance * distance <= minimum) {
            if (go_left) {
                minimum = min(minimum, nearest_neighbour(here->r, p, depth + 1));
            } else {
                minimum = min(minimum, nearest_neighbour(here->l, p, depth + 1));
            }
        }
        return minimum;
    }
}


void solve() {
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int n;
    position pos{0, 0};
    long long smallest = inf;
    in >> n;

    for (int i = 0; i < n; i++) {
        in >> pos.x >> pos.y;
        smallest = min(smallest, nearest_neighbour(root, pos, 0));
        insert(root, pos, 0);
    }
    out << fixed << setprecision(6) << sqrt(smallest);
}

int main() {
    solve();

    return 0;
}