30
правок
Изменения
Нет описания правки
}}
Что же делать с вертикальными линиями?
# Очевидный факт: в конечной выпуклой оболочке будет не более двух вертикальных прямых (левая и правая). Мы можем найти их за <tex>NlogN</tex> и пересечь Найдем все вертикальным прямые за <tex>O(N)</tex> с построенной . Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без них выпуклой оболочкойвсех вертикальных прямых, затем пересечм верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.
# Перейдем в однородное двойственное пространство.
