Предположим, что верхняя и нижняя стороны прямоугольника фиксированы и нам осталось только выбрать левую и правую стороны. Тогда мы за О(К) можем найти список всех прямоугольников, которые попадают в нашу полосу, а так же список всех прямоугольников, у которых только часть попадает в полосу. Тогда мы можем представить это в виде отсортированного набора отрезков [l,r], где l и r - икс координаты левой и правой сторон прямоугольника.
Если какие-то отрезки в нашем наборе имеют общую точку - склеим их в один большой отрезок и запомним что теперь в нем на самом деле два отрезка. Таким образом, после того как мы склеили все отрезки, у нас получится какой-то набор отрезков, для каждого из которых известно количество прямоугольников, которые им покрываются (если в нем есть прямоугольник, который не лежит полностью в нашей полосе, то будем считать что такой отрезок содержит бесконечное количество прямоугольников). Теперь мы можем пройти по всем свободным отрезкам (находящимся между соседними отрезками из нашего набора) и посчитать количество способов покрыть их отрезком в котором лежит не более трех объектов (для этого будем помнить только те свободные отрезки, которые отделены от текущего не более чем тремя объектами).
Таким образом, мы уже имеем решение за O(N2K): перебрать все возможные горизонтальные полосы и в каждой за О(К) посчитать количество прямоугольников, которые покрывают от 1 до 3 объектов. Заметим, что если, например, верхняя сторона полосы не прилегает ни к какому из объектов, то мы можем ее сдвинуть вверх либо вниз и ответ для полосы не изменится. Следовательно, можно перебирать в качестве границ полосы только те строки, в которых есть хотя бы одна клетка, принадлежащая объекту, а затем домножать полученный ответ на расстояния до ближайших "не пустых" строк снизу и сверху.
Таким образом, мы получили решение работающее за O(K3) и не зависящее ни от размеров поля, ни от ограничения на максимальное количество покрываемых объектов.
Комментарии (1)
0
