1

Тема: Пересечения Прямоугольников

Долгое время не могу решить задачу.
Дано 100 000 прямоугольников. Стороны параллельны осям координат. Все координаты целые и убираются в 4 байта. Нужно найти на сколько замкнутых фигур разбивают плоскость эти прямоугольники и найти площадь наибольшей фигуры. за N^2 не катит. Думал над деревом отрезков, но не могу придумать, как его применить.

Помогите, пожалуйста..

2

Re: Пересечения Прямоугольников

Что есть фигура - объединение, пересечение? Некоторые задачи с наборами прямоугольников рассматриваются в книге Препарата, Шеймос

3

Re: Пересечения Прямоугольников

нужно учитывать все фигуры, которые образуются при пересечении прямоугольников.

4

Re: Пересечения Прямоугольников

Два квадрата с координатами (0,0)-(2,2) и (-1,-1)-(1,1). Что должно быть в результате - 1, 3, или 7?

5

Re: Пересечения Прямоугольников

Два квадрата с координатами (0,0)-(2,2) и (-1,-1)-(1,1)

ответ
3 фигуры
и максимальная площадь фигуры тоже 3