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