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