Проверка пересечения полуплоскостей на непустоту за $O(n)$
Решим за линейное время следующую задачу:
Задача: Даны $n$ полуплоскостей. Требуется найти точку, лежащую во всех этих полуплоскостях, либо сказать, что такой нет.
Задачу пересечения полуплоскостей можно решить за время $O(n \log n)$ различными способами. Они находят не только одну точку, но все множество пересечения. Мы же рассмотрим рандомизированный алгоритм, работающий за ожидаемое время $O(n)$.
Давайте будем добавлять полуплоскости по одной в случайном порядке, поддерживая самую высокую точку в множестве пересечения уже добавленных полуплоскостей (Если таких точек несколько, то самую левую из них. При этом изначально ограничим все квадратом $[-10^9, 10^9] \times [-10^9, 10^9]$ при помощи четырех полуплоскостей, чтобы не было проблем с тем, что эта точка бесконечно удалена).
Тогда если при добавлении новой полуплоскости эта точка лежит в очередной полуплоскости, то ничего не поменяется, потому что множество пересечения могло только уменьшиться, но при этом его верхняя точка сохранилась.
Если же эта точка не лежит в новой полуплоскости, то придется заново искать самую верхнюю точку. Заметим, что эта новая точка обязана лежать на прямой, высекающей новую полуплоскость. То есть нам надо найти самую высокую точку на прямой, лежащую в пересечении полуплоскостей. Но ведь все остальные полуплоскости высекают на этой прямой какие-то лучи. Поэтому нам надо найти самую высокую точку в пересечении лучей. Для этого надо отдельно посмотреть на все лучи, смотрящие вниз, и взять из них самый нижний (начинается в точке $A$). Аналогично взять все лучи, смотрящие вверх, и взять из них самый верхний. Проверить, что эти два луча пересекаются, и в таком случае взять точку $A$. Это можно сделать за линейное время.
Почему этот алгоритм работает за линейное время? Доказывается это точно так же, как и для поиска двух ближайших точек на плоскости. Самая верхняя левая точка лежит на пересечении двух прямых, высекающих полуплоскости. Тогда вероятность того, что случайно выбранная прямая лежит на краю равна $\frac{2}{k}$. Асимптотика алгоритма равна $\sum_{k = 1}^{n} k \cdot \frac{2}{k} = \sum_{k = 1}^{n} 2 = 2n = O(n)$.
Замечание: Если больше, чем две полуплоскости, пересекаются в одной точке, то легко заметить, что вероятность от этого становится только меньше. Либо эта точка и раньше уже была самой верхней левой, либо же вероятность правильно выбрать нужную прямую не больше $\frac{2}{k}$.