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