Тема: Площадь объединения прямоуголоников

Собственно, вот задача: http://informatics.mccme.ru/moodle/mod/ … terid=644.

Хочется узнать, решается ли она лучше, чем за O(N^3).

2

Re: Площадь объединения прямоуголоников

См. метод заметающей прямой, книгу Шеймос/Препарата (есть на этом сайте)

Re: Площадь объединения прямоуголоников

MBo пишет:

См. метод заметающей прямой, книгу Шеймос/Препарата (есть на этом сайте)

спасибо. какая сложность получится?

4

Re: Площадь объединения прямоуголоников

nlogn, при помощи дерева отрезков

5

Re: Площадь объединения прямоуголоников

Спасибо, искал тоже ответ на этот вопрос.

Работаю журналистом в одном из хороших женских сайтов, веду также свой сайт - ссылка на его у меня в контактах. Если кто заинтересован женскими статьями (о любви, об отношениях) заходите, читайте, оставляйте комменты.