Cod sursa(job #2891140)

Utilizator ViAlexVisan Alexandru ViAlex Data 17 aprilie 2022 17:51:07
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.58 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>

using namespace std;

const long long inf = 2e18 + 100;
const int invalid = 1e9 + 200;
const int mx = 4e5 + 100;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char *nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser &operator>>(int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser &operator>>(long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

struct position {
    int x, y;

    position() : x(invalid), y(invalid) {

    }

    position(int _x, int _y) : x(_x), y(_y) {

    }
};

bool operator==(const position &a, const position &b) {
    return a.x == b.x && a.y == b.y;
}

bool operator!=(const position &a, const position &b) {
    return a.x != b.x || a.y != b.y;
}


bool compare_x(const position &a, const position &b) {
    return a.x < b.x;
}

bool compare_y(const position &a, const position &b) {
    return a.y < b.y;
}

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;
}

position positions[mx], tree[mx], null_node;
int maximum_depth = 0;
vector<position> order;


void build(int l, int r, int depth) {
    if (l > r)
        return;
    if (l == r) {
        order.push_back(positions[l]);
        return;
    } else {
        if (depth % 2 == 0) {
            sort(positions + l, positions + r + 1, compare_x);
        } else {
            sort(positions + l, positions + r + 1, compare_y);
        }

        int middle = (l + r) / 2;
        order.push_back(positions[middle]);
        build(l, middle - 1, depth + 1);
        build(middle + 1, r, depth + 1);
    }
}

void insert(int node, position p, int depth) {
    maximum_depth = max(maximum_depth, depth);
    if (tree[node] == null_node) {
        tree[node] = p;
    } else {
        bool go_left;
        if (depth % 2 == 0) {
            go_left = p.x <= tree[node].x;
        } else {
            go_left = p.y <= tree[node].y;
        }

        if (go_left) {
            insert(node * 2, p, depth + 1);
        } else {
            insert(node * 2 + 1, p, depth + 1);
        }
    }
}


long long nearest_neighbour(int node, position p, int depth) {
    if (tree[node] == null_node) {
        return inf;
    } else {
        bool go_left;
        if (depth % 2 == 0) {
            go_left = p.x <= tree[node].x;
        } else {
            go_left = p.y <= tree[node].y;
        }

        long long minimum;
        if (go_left) {
            minimum = nearest_neighbour(node * 2, p, depth + 1);
        } else {
            minimum = nearest_neighbour(node * 2 + 1, p, depth + 1);
        }

        minimum = min(minimum, distance(tree[node], p));

        long long distance;
        if (depth % 2 == 0) {
            distance = p.x - tree[node].x;
        } else {
            distance = p.y - tree[node].y;
        }

        if (distance * distance <= minimum) {
            if (go_left) {
                minimum = min(minimum, nearest_neighbour(node * 2 + 1, p, depth + 1));
            } else {
                minimum = min(minimum, nearest_neighbour(node * 2, p, depth + 1));
            }
        }
        return minimum;
    }
}


void solve() {
    InParser in("cmap.in");
    ofstream out("cmap.out");

    int n;
    long long smallest = inf;
    in >> n;
    order.reserve(n);
    for (int i = 0; i < n; i++) {
        in >> positions[i].x >> positions[i].y;
    }

    build(0, n - 1, 0);
    for (int i = 0; i < n; i++) {
        smallest = min(smallest, nearest_neighbour(1, order[i], 0));
        insert(1, order[i], 0);
    }
    out << fixed << setprecision(6) << sqrt(smallest);
}

int main() {
    solve();

    return 0;
}