Максимальное число пересекающихся прямоугольников

Question

Есть задача следующего содержания:

Задано на плоскости множество из N прямоугольников, стороны которых параллельны осям координат, при этом каждый прямоугольник задается координатами левой нижней и правой верхней его вершин. Составить алгоритм определения наибольшего натурального числа К, для которого существует точка плоскости, принадлежащая одновременно К прямоугольникам.

Проще говоря, надо найти место, где одновременно пересекаются больше всего прямоугольников.

Примечание: эффективным считается алгоритм, число действий которого пропорционально O(n²).

Мой код изначально выглядел так:

struct Rectangle
    {
        Point first;
        Point second;
    
        Rectangle(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0)
        {
            first.x = x1;
            first.y = y2;
            second.x = x2;
            second.y = y1;
        }
    
        // Переопределение координат
        // для задания через левую верхнюю
        // и правую нижнюю точки.
        void RedefineCoords()
        {
            swap(this->first.y, this->second.y);
            return;
        }
        
    };
    
    bool CheckIntersection(Rectangle a, Rectangle b)
    {
        return
            (a.first.x <= b.second.x &&
             a.second.x >= b.first.x &&
             a.first.y >= b.second.y &&
             a.second.y <= b.first.y);
    }
int main()
{
    int maxIntersections = 0;
    
        for (int i = 0; i < quantity - 1; i++)
        {
            int countIntersections = 0;
            for (int j = 0; j < quantity; j++)
            {
                if (CheckIntersection(rectangles[i], rectangles[j]))
                    countIntersections++;
            }
            if (countIntersections > maxIntersections)
                maxIntersections = countIntersections;
        }
    
        cout << maxIntersections << endl;
}

Но я понимаю, что так просто это не посчитать. Подскажите, пожалуйста, какой алгоритм стоит использовать (необязательно nlog n-оптимальный), чтобы решить эту задачу?

Answer 1

Не удивляйтесь, я полностью переписал ответ и алгоритм.

Заметим что пересечение любого количества прямоугольников содержит отрезок или точку на нижней стороне одного из них (доказывается по индукции). Через нижние стороны всех прямоугольников проведем прямые.

Каждую такую прямую пересечём с всеми прямоугольниками и найдём максимум пересечения. Максимум будем искать заметанием: левые и правые стороны прямоугольников отсортируем. По упорядоченному списку пройдемся: левая сторона - увеличиваем счётчик, правая - уменьшаем. Максимум счётчика - то что нам нужно. Конечно рассматриваются только прямоугольники, которые пересекаются с прямой.

Алгоритм работает за N^2: N прямых, на каждой 2N действий. Сортировка левых и правых сторон делается один раз заранее.

Код

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror rect_intersection.cpp

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

struct Rect {
    int x_min, x_max, y_min, y_max;
};

enum Edge { open, close };

struct Line {
    int v;
    Edge e;
    const Rect *r;
};

bool operator <(const Line &l1, const Line &l2) {
    return (l1.v < l2.v) || (l1.v == l2.v && l1.e < l2.e);
}

int main() {
    int n;
    std::cin >> n;
    std::vector<Rect> rects;
    for (int i = 0; i < n; ++i) {
        Rect r;
        std::cin >> r.x_min >> r.x_max >> r.y_min >> r.y_max;
        rects.push_back(r);
    }

    std::vector<Line> v_lines;
    for (const Rect &r : rects) {
        v_lines.push_back({r.x_min, Edge::open, &r});
        v_lines.push_back({r.x_max, Edge::close, &r});
    }
    std::sort(v_lines.begin(), v_lines.end());

    int max_k = 0;
    for (const Rect &r : rects) {
        const int y = r.y_min;

        int k = 0;
        for (int j = 0; j < 2 * n; ++j) {
            const Rect &r = *v_lines[j].r;
            if (r.y_min <= y && y <= r.y_max) {
                switch (v_lines[j].e) {
                case open:
                    ++k;
                    max_k = std::max(max_k, k);
                    break;
                case close:
                    --k;
                    break;
                }
            }
            // std::cout << k << ' ';
        }
        // std::cout << '\n';
    }
    std::cout << max_k << '\n';
}

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror rect_intersection.cpp
$ echo -e "2 0 2 0 2 1 3 1 3" | ./a.out
2

БЛОГ НА HUSL

Максимальное число пересекающихся прямоугольников

Ответы (1 шт):