Quadtree Point-in-Bounding-Boxes Query

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>

constexpr int MAX_BOXES_PER_NODE = 16;
constexpr int MAX_TREE_DEPTH = 20;

struct BoundingBox {
    double minX, minY, maxX, maxY;
    std::size_t id;

    BoundingBox(double x0, double y0, double x1, double y1, std::size_t idx)
        : minX(x0), minY(y0), maxX(x1), maxY(y1), id(idx) {}

    // check if point is inside this box
    bool contains(double x, double y) const {
        return x >= minX && x <= maxX && y >= minY && y <= maxY;
    }

    // check if this box intersects with another rectangle
    bool intersects(double x0, double y0, double x1, double y1) const {
        return !(maxX < x0 || minX > x1 || maxY < y0 || minY > y1);
    }
};

struct QuadTreeNode {
    double minX, minY, maxX, maxY;
    std::vector<BoundingBox> boxes;
    QuadTreeNode* children[4] = {nullptr, nullptr, nullptr, nullptr};

    QuadTreeNode(double x0, double y0, double x1, double y1)
        : minX(x0), minY(y0), maxX(x1), maxY(y1) {}

    ~QuadTreeNode() {
        for (int i = 0; i < 4; i++) {
            delete children[i];
        }
    }

    // check if this node has no children
    bool isLeaf() const {
        return children[0] == nullptr;
    }

    // split this node into 4 quadrants
    void subdivide() {
        double midX = (minX + maxX) / 2.0;
        double midY = (minY + maxY) / 2.0;

        children[0] = new QuadTreeNode(minX, midY, midX, maxY);  // NW
        children[1] = new QuadTreeNode(midX, midY, maxX, maxY);  // NE
        children[2] = new QuadTreeNode(minX, minY, midX, midY);  // SW
        children[3] = new QuadTreeNode(midX, minY, maxX, midY);  // SE
    }

    // add a bounding box to the quadtree
    void insert(const BoundingBox& box, int depth = 0) {
        if (!box.intersects(minX, minY, maxX, maxY)) {
            return;
        }

        if (isLeaf()) {
            boxes.push_back(box);

            if (boxes.size() > MAX_BOXES_PER_NODE && depth < MAX_TREE_DEPTH) {
                subdivide();

                std::vector<BoundingBox> remainingBoxes;
                for (const auto& b : boxes) {
                    bool distributed = false;
                    for (int i = 0; i < 4; i++) {
                        if (b.intersects(children[i]->minX, children[i]->minY,
                                       children[i]->maxX, children[i]->maxY)) {
                            children[i]->insert(b, depth + 1);
                            distributed = true;
                        }
                    }
                    if (!distributed) {
                        remainingBoxes.push_back(b);
                    }
                }
                boxes = remainingBoxes;
            }
        } else {
            for (int i = 0; i < 4; i++) {
                children[i]->insert(box, depth + 1);
            }
        }
    }

    // check if point is inside any box in this subtree
    bool queryPoint(double x, double y) const {
        if (x < minX || x > maxX || y < minY || y > maxY) {
            return false;
        }

        for (const auto& box : boxes) {
            if (box.contains(x, y)) {
                return true;
            }
        }

        if (!isLeaf()) {
            for (int i = 0; i < 4; i++) {
                if (children[i]->queryPoint(x, y)) {
                    return true;
                }
            }
        }

        return false;
    }
};

class QuadTree {
private:
    QuadTreeNode* root;

public:
    QuadTree(double minX, double minY, double maxX, double maxY) {
        root = new QuadTreeNode(minX, minY, maxX, maxY);
    }

    ~QuadTree() {
        delete root;
    }

    // add a box to the quadtree
    void insert(const BoundingBox& box) {
        root->insert(box);
    }

    // check if point is in any dangerous region
    bool queryPoint(double x, double y) const {
        return root->queryPoint(x, y);
    }
};

int main(int argc, char** argv) {
    const char* path;
    double qx, qy;

    if (argc == 4) {
        path = argv[1];
        qx = std::atof(argv[2]);
        qy = std::atof(argv[3]);
    } else if (argc == 3) {
        path = "info.txt";
        qx = std::atof(argv[1]);
        qy = std::atof(argv[2]);
    } else {
        return 1;
    }

    std::ifstream fin(path);
    if (!fin) {
        std::cout << "false\n";
        return 0;
    }

    std::vector<BoundingBox> boxes;
    boxes.reserve(1024);

    double x0, y0, x1, y1;
    std::size_t idx = 0;
    double minX = 1e9, minY = 1e9, maxX = -1e9, maxY = -1e9;

    while (fin >> x0 >> y0 >> x1 >> y1) {
        if (x0 > x1) std::swap(x0, x1);
        if (y0 > y1) std::swap(y0, y1);

        boxes.emplace_back(x0, y0, x1, y1, idx++);

        minX = std::min(minX, x0);
        minY = std::min(minY, y0);
        maxX = std::max(maxX, x1);
        maxY = std::max(maxY, y1);
    }

    if (boxes.empty()) {
        std::cout << "false\n";
        return 0;
    }

    double padding = std::max(maxX - minX, maxY - minY) * 0.1;
    QuadTree qt(minX - padding, minY - padding, maxX + padding, maxY + padding);

    for (const auto& box : boxes) {
        qt.insert(box);
    }

    bool exists = qt.queryPoint(qx, qy);
    std::cout << (exists ? "true" : "false") << std::endl;
    return 0;
}