Задача такова, дано прямоугольное (белого цвета) поле на него мы ложим различные по цвету и размеру прямоугольники, после укладки нужно найти какова площадь каждого из цветов на поле (если посмотреть сверху на поле), это все вывести.
В обсуждениях пишут что можно set'ом heap'ом воспользоватся, честно говоря вообще не представляю как тут можно set использовать.
Подскажите плз.
Спасибо заранее.
Она решается секущей прямой + сетом.
Создаешь два типа событий: начало прямоугольника по X, конец прямоугольника по X, идешь по этим событиям секущей прямой, постоянно поддерживая set с текущими открытыми прямоугольниками вдоль Y. Также поддерживаем высоту суммарную высоту открытых прямгуольников для каждого цвета.
Когда обрабатываешь очередной событие, тебе надо уметь пересчитывать состояние set и суммарные высоты. Это делается какими-то шаманствами с lower_bound. Грубо говоря, если добавляемый прямоугольник ни с чем не пересекается в сете, то все хорошо, просто добавляем его высоту к его цвету. Если пересекается, то смотрим - то, с чем он пересекается, выше или ниже в плане слоя. В конце в любом случае добавляем его целиком в сет.
Да, это проще.
Я нуб :о(
можно подробнее?