91
правка
Изменения
→Последовательный алгоритм
Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас <tex>O(log(n))</tex>. Таким образом, алгоритм нахождения общей касательной будет работать за <tex>O(log^2(n))</tex>.
Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за <tex>O(n)<\/tex>. Задача решена.
==Параллельный алгоритм==
