# Переход к шагу 5. Шаг

Переход к шагу 5. Шаг 4. Точка t не является внутренней точкой Q2. Если «смотреть» из точки t, то многоугольник Q2 лежит в клине с углом, меньшим или равным ?. Этот клин определяем двумя вершинами u и v многоугольника Q2, которые находим за один обход вершин многоугольника Q2. Вершины u и v разбивают границу Q2 на две цепочки вершин, монотонные относительно изменения полярного угла с началом в точке t. При движении по одной цепочке угол увеличивается, при движении по другой - уменьшается. Одну из этих цепочек удаляем (ее точки являются внутренними относительно строящейся оболочки). Другая цепочка и граница Q1 являются упорядоченными списками, содержащими не более N вершин. За время, пропорциональное O(N), их можно соединить в один список вершин, упорядоченный по полярному углу относительно точки t. Шаг 5. К полученному списку точек применяем метод обхода Грэхема. Затраты времени пропорциональны O(N). Итак, утверждение. Выпуклая оболочка объединения двух выпуклых многоугольников находится

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа