Блог пользователя Planshetnik

Автор Planshetnik, 14 лет назад, По-русски
Задача такова, дано прямоугольное (белого цвета) поле на него мы ложим различные по цвету и размеру прямоугольники, после укладки нужно найти какова площадь каждого из цветов на поле (если посмотреть сверху на поле), это все вывести.

В обсуждениях пишут что можно set'ом heap'ом воспользоватся, честно говоря вообще не представляю как тут можно set использовать.
Подскажите плз.
Спасибо заранее. 
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Она решается секущей прямой + сетом.

Создаешь два типа событий: начало прямоугольника по X, конец прямоугольника по X, идешь по этим событиям секущей прямой, постоянно поддерживая set с текущими открытыми прямоугольниками вдоль Y. Также поддерживаем высоту суммарную высоту открытых прямгуольников для каждого цвета.

Когда обрабатываешь очередной событие, тебе надо уметь пересчитывать состояние set и суммарные высоты. Это делается какими-то шаманствами с lower_bound. Грубо говоря, если добавляемый прямоугольник ни с чем не пересекается в сете, то все хорошо, просто добавляем его высоту к его цвету. Если пересекается, то смотрим - то, с чем он пересекается, выше или ниже в плане слоя. В конце в любом случае добавляем его целиком в сет.

 

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно использовать простую и незатейливую кучу. Просто для каждой секущей так же пробегамся по событиям начала/конца прямоугольника и добавляем/удаляем номера прямоугольников в кучу. Добавить/удалить один элемент можно за логарифм. А текущий верхний прямоугольник будет на верху кучи. Соответственно получаем чистенький N*N*logN, причем с маленькими тратами на структуру даже в Java (т.к. для кучи можно обойтись без объектов).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Чуть ошибся, надо все же не кучу, а множество. Потому что надо добавлять и удалять элементы по значению.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Заведя дополнительную память, из кучи тоже можно удалять. Т.е. храним для каждого объекта где он лежит в куче.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, это проще.

      Я нуб :о(

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
если мне не изменяет память, я ее сдал двумерной sqrt-декомпозицией.