Изменения

Перейти к: навигация, поиск

Персистентные структуры данных

1 байт добавлено, 07:48, 5 апреля 2015
Использование персистентных структур данных для решения геометрических задач
Персистентные структуры данных используются при решении геометрических задач. Примером может служить Point loctaion problem — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.
Сначала рассмотрим решение ''onlineoffline''-задачи.
Пусть дан набор многоугольников, они не пересекаются, но могут иметь общие вершины, суммарное число вершин — <tex>n</tex>.
Запрос: точка <tex>(x,y)</tex>. Вернуть нужно многоугольник, в котором она находится. Количество точек <tex>m</tex>.
Анонимный участник

Навигация