Сортировка и стек: обход Грэхема и цепочка Эндрю

Если ты умеешь строить оболочку сортировкой и стеком, знаешь, почему стековая часть линейна, и понимаешь, что меняет «снимать при нуле» против «не снимать», листай до «Теперь сам».

Как думаешь, сколько поворотов

Те же двенадцать гвоздей, что в прошлом уроке. Заворачивание подарка потратило на них 77 поворотов, а на восьмидесяти точках параболы - 6320. Теперь точки сначала сортируются, а потом обрабатываются по одной, и каждая решает судьбу нескольких предыдущих.

Ответь себе до чтения: сколько поворотов понадобится на восьмидесяти точках параболы, где все точки - вершины? Сортировка подсказывает «примерно n · log n», но повороты считаются уже после неё. Ответ: 156, то есть 2n − 4. Повороты растут линейно, и главную цену платит сортировка.

На что это похоже

Очередь в гардероб с номерками по росту. Ты идёшь вдоль шеренги людей слева направо и строишь «линию подбородков» снизу: каждый новый человек сравнивается с двумя последними в линии. Если новый так низко, что предыдущий торчит над прямой от позапрошлого к новому, предыдущего вычёркивают - он уже никогда не окажется на нижней границе. Вычеркнутый не возвращается, поэтому каждый человек вычёркивается не больше одного раза.

Механизм: две цепочки и снятие со стека

После сортировки самая левая и самая правая точки - вершины оболочки. Они делят её на нижнюю цепочку (от левой к правой по низу) и верхнюю (обратно по верху). Нижнюю строят проходом слева направо:

niz = []
для p по возрастанию (x, y):
    пока в niz хотя бы две точки и поворот(niz[-2], niz[-1], p) <= 0:
        снять niz[-1]              она не вершина нижней цепочки
    положить p

Почему снятая точка точно не вершина. Нижняя цепочка, пройденная слева направо, - это обход против часовой стрелки, и на каждой её вершине поворот налево. Если для niz[-2], niz[-1] и новой p поворот направо, точка niz[-1] лежит над отрезком от niz[-2] до p - внутри будущей оболочки (при нулевом повороте - на этом отрезке). И позже на нижнюю границу она не вернётся: следующие точки правее, и нижняя граница над её x может только опуститься.

Верхняя цепочка - тот же проход в обратном порядке, справа налево. Оболочка - нижняя цепочка без последней точки плюс верхняя без последней: концы у них общие.

Почему линейно после сортировки. В каждую цепочку точка кладётся один раз и снимается не больше одного раза. Каждый поворот либо снимает точку, либо завершает цикл пока для текущей p. Значит, поворотов не больше (число снятий) + (число точек), то есть не больше 2n на цепочку. Это амортизированный довод: отдельная точка может снять много предыдущих, но все снятия вместе не превосходят n.

Грэхем и Эндрю. Обход Грэхема (1972) сортирует точки по углу вокруг самой нижней и строит оболочку одним стеком. Эндрю (1979) сортирует по x и строит две цепочки. Стек и довод одинаковые, но сортировка по координате не требует ни углов, ни особого сравнения точек на одном луче. Поэтому на практике чаще пишут Эндрю.

Правило

Отсортируй точки по (x, y). Нижняя цепочка: проход слева направо со стеком, где перед каждой новой точкой снимаешь верхнюю, пока поворот последних двух с новой не положителен. Верхняя - тот же проход справа налево. Оболочка - склейка цепочек без повторных концов. Время O(n · log n) на сортировку плюс O(n) на стеки. Условие снятия <= 0 выбрасывает точки на рёбрах, < 0 - оставляет их.

Разбор: гвозди и парабола

schet = [0]

def povorot(a, b, c):
    schet[0] = schet[0] + 1
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def endryu(tochki):
    t = sorted(tochki)
    niz = []
    for p in t:
        while len(niz) >= 2 and povorot(niz[-2], niz[-1], p) <= 0:
            niz.pop()
        niz.append(p)
    verh = []
    for p in t[::-1]:
        while len(verh) >= 2 and povorot(verh[-2], verh[-1], p) <= 0:
            verh.pop()
        verh.append(p)
    return niz[:-1] + verh[:-1]

gvozdi = [[2, 1], [6, 0], [9, 3], [4, 4], [7, 6], [1, 5],
          [3, 8], [5, 2], [8, 8], [0, 3], [6, 5], [4, 7]]
print(endryu(gvozdi), schet[0])
for n in [20, 40, 80, 160]:
    parabola = []
    for x in range(n):
        parabola.append([x, x * x])
    schet[0] = 0
    h = len(endryu(parabola))
    print(n, h, schet[0])

[[0, 3], [2, 1], [6, 0], [9, 3], [8, 8], [3, 8], [1, 5]] 34
20 20 36
40 40 76
80 80 156
160 160 316

Оболочка гвоздей та же, что у заворачивания, и в том же порядке: от самой левой точки против часовой стрелки. Поворотов 34 вместо 77. На параболе вершин столько же, сколько точек, а поворотов 2n − 4: нижняя цепочка добавляет точки без единого снятия (на параболе каждый следующий поворот налево), а верхняя, наоборот, снимает каждую точку сразу - от правого конца до левого вся парабола под хордой. Сравни с прошлым уроком: на 80 точках 156 поворотов против 6320.

Цена сортировки движок честно добавляет к шагам, но и она - n · log n, а не n². Отсюда весь выигрыш: сортировка один раз расставила точки так, что каждая следующая проверяется только с вершиной стека.

Разбор: точки на рёбрах и одна прямая

Что считать вершиной, если три точки лежат на ребре подряд? Обычно - только концы ребра. Иногда - все точки на границе: например, если надо перечислить столбы забора, а не углы участка. Это решает одно условие снятия.

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def endryu(tochki, strogo):
    t = sorted(tochki)
    niz = []
    for p in t:
        while len(niz) >= 2:
            z = povorot(niz[-2], niz[-1], p)
            if z < 0 or (strogo and z == 0):
                niz.pop()
            else:
                break
        niz.append(p)
    verh = []
    for p in t[::-1]:
        while len(verh) >= 2:
            z = povorot(verh[-2], verh[-1], p)
            if z < 0 or (strogo and z == 0):
                verh.pop()
            else:
                break
        verh.append(p)
    return niz[:-1] + verh[:-1]

kvadrat = [[0, 0], [2, 0], [4, 0], [4, 2], [4, 4],
           [2, 4], [0, 4], [0, 2], [2, 2]]
print(endryu(kvadrat, True))
print(endryu(kvadrat, False))
print(endryu([[1, 1], [3, 1], [3, 1], [2, 3]], True))
print(endryu([[0, 0], [1, 1], [2, 2], [3, 3]], True))
print(endryu([[0, 0], [1, 1], [2, 2], [3, 3]], False))

[[0, 0], [4, 0], [4, 4], [0, 4]]
[[0, 0], [2, 0], [4, 0], [4, 2], [4, 4], [2, 4], [0, 4], [0, 2]]
[[1, 1], [3, 1], [2, 3]]
[[0, 0], [3, 3]]
[[0, 0], [1, 1], [2, 2], [3, 3], [2, 2], [1, 1]]

Квадрат с серединами сторон и центром. Со снятием при нуле - четыре угла. Без снятия при нуле - восемь точек границы, центра нет: у него поворот строго отрицательный. Повторная точка (3, 1) не помешала: после сортировки две копии стоят рядом, поворот через нулевой вектор равен нулю, и строгий вариант снимает лишнюю копию.

Последние две строки - ловушка. Все точки на одной прямой. Строгий вариант честно отвечает «оболочка - отрезок от (0, 0) до (3, 3)». Нестрогий возвращает средние точки дважды: нижняя цепочка оставила их по пути туда, верхняя - по пути обратно. Если тебе нужны точки на границе, этот случай - все точки на одной прямой - приходится обрабатывать отдельно.

Что ломается без этого

< вместо <= без мысли о прямой. На вырожденном входе оболочка выходит с повторами, и следующий шаг - площадь, обход, вращающиеся калиперы - получает вырожденный многоугольник: вершины повторяются, рёбра идут по прямой туда и обратно, площадь ноль. А набор из одной точки цепочка Эндрю превращает в пустой список - его, как и повторы, обрабатывают отдельно.

Сортировка по x без y. Точки с одинаковым x встают в порядке входа, и цепочки начинаются и кончаются не в тех точках. На входе (4, 1), (4, 3), (0, 1), (0, 0), (4, 0), (1, 0) оболочка теряет вершину (4, 3) и получает лишнюю (4, 1). Сравнение пар (x, y) - сортировка списков в Python - закрывает это даром.

Угол через atan2 в обходе Грэхема. Сортировка по дробному углу ставит точки на одном луче в случайном порядке. Сравнивать направления надо поворотом, а проще - взять Эндрю, где углов нет вовсе.

Зачем это в работе

Это та оболочка, которую ты напишешь сам, когда библиотеки под рукой нет: на олимпиаде, на собеседовании, во встроенной системе. Двадцать строк, n · log n, и все решения - через поворот, то есть точно на целых координатах. Тот же приём - стек, в котором новый элемент снимает «бесполезные» старые, - встречается в алгоритмах на массивах: ближайший меньший элемент, максимум в окне.

Теперь сам

1. Отсортированные точки (0, 0), (1, 2), (2, 1), (3, 3), (4, 0). Как меняется стек нижней цепочки?
2. Почему на случайных точках в квадрате цепочке Эндрю всё равно нужно n · log n, хотя вершин оболочки мало?
3. Нижняя цепочка точек (0, 0), (1, −1), (2, −1), (3, 0) при строгом и нестрогом снятии?