work2/task6.cpp - develop - novd7/algirithms_sem2

work2/task6.cpp
152 строки5 KB
Новиков Владимир
work 2
03 апр 2026, 22:39
03 апр 2026, 22:3904518aa
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Точка (x, y)
struct Point {
    int x, y;
};

// Узел "range tree"
struct Node {
    int xKey;    // Ключ по оси X (например, x "центральной" точки
    vector<Point> yPoints;  // Все точки поддерева, отсортированные по Y
    Node* left;    // Левое поддерево
    Node* right;    // Правое поддерево
};

// Построение упрощённого range tree
Node* buildRangeTree(vector<Point> points) {
    if (points.empty()) return nullptr;

    // Сортируем входные точки по X
    sort(points.begin(), points.end(),
    [](const Point &a, const Point &b){
    return a.x < b.x;
    });

    // Выбираем "медиану" по X
    int mid = points.size() / 2;
    // Создаём новый узел
    Node* node = new Node;
    node->xKey = points[mid].x;
    node->left = nullptr;
    node->right = nullptr;

    // Сортируем ВЕСЬ текущий набор points по Y и сохраняем
    sort(points.begin(), points.end(),
        [] (const Point &a, const Point &b){
        return a.y < b.y;
    });

    node->yPoints = points;

    // Готовим вектора для левого и правого поддерева
    vector<Point> leftPoints, rightPoints;
    for (int i = 0; i < (int)points.size(); i++) {
        if (i == mid) continue; // пропустим "центральную" точку
        if (points[i].x <= node->xKey) {
            leftPoints.push_back(points[i]);
        } else {
            rightPoints.push_back(points[i]);
        }
    }

    // Рекурсивно строим левое и правое поддеревья
    node->left = buildRangeTree(leftPoints);
    node->right = buildRangeTree(rightPoints);

    return node;
}

// Поиск точек в прямоугольнике [x1..x2] × [y1..y2]
void queryRangeTree(Node* root,
    int x1, int x2,
    int y1, int y2,
    vector<Point> &result)
{
    if (!root) return;

    // Случай: xKey < x1 — идём только в правое поддерево
    if (root->xKey < x1) {
        queryRangeTree(root->right, x1, x2, y1, y2, result);
    }

    // xKey > x2 — идём только в левое поддерево
    else if (root->xKey > x2) {
        queryRangeTree(root->left, x1, x2, y1, y2, result);
    }

    else {
        // xKey в [x1..x2], значит:
        // 1) Отбираем подходящие по Y точки из текущего узла.
        // 2) Рекурсивно обходим и левое, и правое поддерево.

        // Точки в текущем узле отсортированы по Y
        const auto &vecY = root->yPoints;

        // Через бинарный поиск найдём границы по Y
        auto lower = lower_bound(vecY.begin(), vecY.end(), Point{0, y1},
            [](const Point &a, const Point &b){
            return a.y < b.y;
        });

        auto upper = upper_bound(vecY.begin(), vecY.end(), Point{0, y2},
            [](const Point &a, const Point &b){
            return a.y < b.y;
        });

        // Отфильтруем ещё и по X
        for (auto it = lower; it != upper; ++it) {
            if (it->x >= x1 && it->x <= x2) {
                result.push_back(*it);
            }
        }

        // Идём влево и вправо
        queryRangeTree(root->left, x1, x2, y1, y2, result);
        queryRangeTree(root->right, x1, x2, y1, y2, result);
    }
}

int main() {
    vector<Point> points = {
        {1,4}, {2,2}, {3,6}, {5,3}, {6,7}, {7,1}, {8,4}
    };

    // Строим дерево
    Node* root = buildRangeTree(points);
    // Диапазон для поиска
    int x1 = 2, x2 = 6;
    int y1 = 2, y2 = 5;

    // Выполняем запрос
    vector<Point> answer;
    queryRangeTree(root, x1, x2, y1, y2, answer);

    // Убираем возможные дубликаты
    sort(answer.begin(), answer.end(),
        [](const Point &a, const Point &b){
        if (a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    });

    answer.erase(unique(answer.begin(), answer.end(),
        [](const Point &a, const Point &b){
        return (a.x == b.x && a.y == b.y);
    }),
    answer.end());

    // Выводим уникальный результат
    cout << "Найденные точки в диапазоне [" 
    << x1 << "..." << x2 << "] " << "[" 
    << y1 << "..." << y2 << "]\n";

    for (auto &p : answer) {
        cout << "(" << p.x << ", " << p.y << ") \n";
    }

    return 0;
}