Выпуклая ОболочкаConvex Hull

Точки сортируются по x (один раз, O(n log n)) и делятся вертикальной линией на левую и правую половины. Рекурсивно строится выпуклая оболочка каждой половины — обе оболочки в итоге получаются в виде выпуклых многоугольников, обходимых против часовой стрелки. Базовый случай — до 3 точек, тривиальная оболочка (сама точка, отрезок или треугольник). Всё нетривиальное содержание алгоритма — в шаге слияния: как объединить две уже построенные оболочки, левую и правую, в одну общую оболочку всех точек.Points are sorted by x (once, O(n log n)) and split by a vertical line into left and right halves. Each half's convex hull is built recursively — both hulls end up as convex polygons traversed counterclockwise. The base case is up to 3 points, a trivial hull (a single point, a segment, or a triangle). All the algorithm's non-trivial content is in the merge step: how to combine two already-built hulls, left and right, into one shared hull of all the points.

Поскольку левая оболочка целиком лежит левее правой, объединённую оболочку можно получить, соединив их ровно двумя отрезками — верхней и нижней "касательной" (bridge/tangent): прямыми, которые касаются обеих оболочек так, что все остальные точки обеих оболочек лежат по одну сторону от каждой из этих прямых. После нахождения обеих касательных итоговая оболочка обходится так: часть левой оболочки от точки верхней касательной до точки нижней касательной (по одной дуге), затем через нижнюю касательную на правую оболочку, часть правой оболочки от нижней касательной до верхней, и обратно через верхнюю касательную — все точки, оказавшиеся строго между этими дугами внутри объединённого контура, отбрасываются как внутренние. Найти обе касательные можно за линейное время: начиная с самой правой точки левой оболочки и самой левой точки правой оболочки, поочерёдно "проворачивать" точку на одной оболочке, пока прямая не перестанет пересекать оболочку с другой стороны — классический линейный обход (walk), а не полный перебор пар точек. Итоговое рекуррентное соотношение T(n) = 2T(n/2) + O(n) даёт по Master theorem (2.1.2) O(n log n) — та же асимптотика, что и у ближайшей пары точек, при принципиально другом механизме слияния.Since the left hull lies entirely to the left of the right hull, the combined hull can be obtained by connecting them with exactly two segments — the upper and lower "bridge" (tangent) lines: lines that touch both hulls such that all remaining points of both hulls lie on one side of each line. Once both tangents are found, the resulting hull is traced as follows: the part of the left hull from the upper-tangent point to the lower-tangent point (one arc), then across the lower tangent onto the right hull, the part of the right hull from the lower tangent back to the upper tangent, and back across the upper tangent — any points that end up strictly between these arcs, inside the merged outline, are discarded as interior points. Both tangents can be found in linear time: starting from the rightmost point of the left hull and the leftmost point of the right hull, alternately "walk" the point on one hull forward until the line no longer crosses the other hull — a classic linear walk, not a brute-force scan over all point pairs. The resulting recurrence T(n) = 2T(n/2) + O(n) gives O(n log n) by the Master theorem (2.1.2) — the same asymptotics as closest pair of points, via a fundamentally different merge mechanism.

// left, right — оболочки в CCW-порядке, left целиком левее right// left, right — hulls in CCW order, left entirely to the left of right
Polygon mergeHulls(const Polygon& left, const Polygon& right) {
    auto [i, j] = findUpperTangent(left, right);   // линейный walk, не перебор// a linear walk, not a scan
    auto [k, l] = findLowerTangent(left, right);

    Polygon result;
    // дуга левой оболочки от верхней касательной до нижней// the left hull's arc from the upper to the lower tangent
    for (int p = i; ; p = (p + 1) % left.size()) {
        result.push_back(left[p]);
        if (p == k) break;
    }
    // дуга правой оболочки от нижней касательной до верхней// the right hull's arc from the lower to the upper tangent
    for (int p = l; ; p = (p + 1) % right.size()) {
        result.push_back(right[p]);
        if (p == j) break;
    }
    return result;                                 // O(n) на слияние, T(n)=2T(n/2)+O(n)// O(n) to merge, T(n)=2T(n/2)+O(n)
}

Точки на плоскости — демонстрация проигрывает разбиение по x, построение оболочки каждой половины рекурсивно, и итоговое слияние в общую оболочку (точки, оказавшиеся внутри объединённого контура, гаснут). Слияние на диаграмме показано как единый шаг «получена общая оболочка» — сама схема линейного поиска касательных описана в тексте и коде выше.Points in the plane — the demo auto-plays the split by x, building each half's hull recursively, and the final merge into one combined hull (points that end up inside the merged outline fade out). The merge is shown on the diagram as a single "combined hull obtained" step — the linear tangent-search scheme itself is described in the text and code above.