Поиск пересечения полуплоскостей с точкой внутри
Алгоритмы нахождения пересечения полуплоскостей достаточно сложные, поэтому стоит пользоваться ситуациями, когда задачу нужно решать не в общем случае. К примеру, если все полуплоскости «смотрят вниз», то это уже задача Convex Hull Trick. Если нужно лишь проверить пересечение полуплоскостей на непустоту, то это можно сделать при помощи линейного рандомизированного алгоритма. В этой главе же мы рассмотрим ситуацию, когда нам известно, что какая-то точка $P$ обязательно лежит строго внутри пересечения полуплоскостей.
Замечание: Обратите внимание, что точка должна лежать строго внутри, поэтому нельзя просто сначала найти точку на границе при помощи рандомизированного линейного алгоритма, а потом запустить алгоритм из этой главы.
Пусть точка $P$ лежит в пересечении полуплоскостей. Тогда давайте сначала переместим точку $P$ в начало координат. Все полуплоскости тоже сдвинем на вектор $-P$. Теперь начало координат лежит в пересечении полуплоскостей. Давайте все прямые вида $ax + by + c = 0$ заменим на точки $\left( \frac{a}{c}, \frac{b}{c} \right)$. Теперь мы перешли к двойственной задаче, и у полученного набора точек нужно найти выпуклую оболочку, что уже намного проще. После этого мы найдем список индексов прямых, которые образуют пересечение полуплоскостей.