228
правок
Изменения
→update
*Спускаемся по <tex> D </tex> до соответвствующих трапецоидов.
*Вместо них добавляем новые ключи как показано на картинке.
Заметим, что не нужно каждый раз хранить все трапецоиды, которые пересек отрезок. Можно менять структуру во время поиска этих трапецоидов.
Если идти по отрезку слева направо, то как только отрезок пересек очередное вертикальное дополнение новый трапецоид левее этого дополнения заканчивается и больше изменяться не будет. Мы можем сразу поменять структуру.
Таким образом, сложный случай сводится к простому.
==Случай коллизии==
