Изменения
→Использование персистентных структур данных для решения геометрических задач=
Сведем задачу к одномерной. Прямая проходит через точку <tex>A</tex>. Для того, чтобы найти в каком отрезке лежит эта точка, нужно точки-границы отрезков хранить отсортированными по возрастанию и найти между какими двумя точками лежит точка <tex>A</tex>. Это можно сделать бинпоиском. Если этот отрезок принадлежит какому-то из данных многоугольников, то значит и точка лежит внутри этого многоугольника.
Построим [[Дерево поиска, наивная реализация|сбалансированное дерево поиска]], в котором будем хранить точки, которые являются границами отрезков, но не в виде чисел, а как линейные функции вида <tex>y=kx+b</tex>. Для каждой вершины дерева ее ключ – — это линейная функция.
При переходе из одной полосы в другую будем обрабатывать события. Это могут быть операции добавления, удаления, замены элементов в дерево.
Чтобы найти точку внутри полосы будем подставлять <tex>x</tex>-координату точки-запроса в линейные функции и найдем в двоичном дереве место, где находится точка, затем определим, в каком многоугольнике лежит точка-запрос.
Итого обрабатывается n событий, каждое за <tex>log\ n</tex> и <tex>m</tex> запросов, также каждый за <tex>log\ n</tex>. Общее время работы алгоритма <tex>nlogn\log\ n</tex> <tex>+</tex> <tex>mlogm\log\ n</tex>.
При решении ''online''-задачи вместо обычного двоичного дерева нужно поддерживать частично персистентное дерево. Будем идти слева направо и поддерживать персистентное дерево поиска. Тогда для каждой полосы у нас будет своя версия дерева.
