Тема: Площадь объединения прямоуголоников
Собственно, вот задача: http://informatics.mccme.ru/moodle/mod/ … terid=644.
Хочется узнать, решается ли она лучше, чем за O(N^3).
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Площадь объединения прямоуголоников
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Собственно, вот задача: http://informatics.mccme.ru/moodle/mod/ … terid=644.
Хочется узнать, решается ли она лучше, чем за O(N^3).
См. метод заметающей прямой, книгу Шеймос/Препарата (есть на этом сайте)
См. метод заметающей прямой, книгу Шеймос/Препарата (есть на этом сайте)
спасибо. какая сложность получится?
nlogn, при помощи дерева отрезков
Спасибо, искал тоже ответ на этот вопрос.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Площадь объединения прямоуголоников