главная новое лучшее написать

linesweep


3

Ссылка на задачу — 3394. Check if Grid can be Cut into Sections.

📌 Описание задачи

Дано квадратное поле n×n, в котором размещены непересекающиеся прямоугольники.
Необходимо определить, можно ли сделать две горизонтальные или две вертикальные разрезки, чтобы:

Если такие разрезки возможны, вернуть true, иначе — false.

Пример

💡 Идея

Поскольку прямоугольники не пересекаются, возможные разрезки должны полностью разделять их на независимые группы.
Мы спроектируем прямоугольники на каждую ось. Если полученные отрезки отсортировать по координатам и просканировать их, можно определить количество неперекрывающихся сегментов, это позволит понять, возможно ли корректное разбиение.

Читать дальше →

ответить