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