Двойственность: точка становится прямой, а три точки на прямой - три прямые через точку

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

Как думаешь, как это проверить

Сорок точек на сетке 31 × 31. Есть ли среди них три на одной прямой - и сколько таких троек? Перебор троек - 9880 поворотов. Есть ли способ быстрее?

Вторая задача, на вид совсем другая. Шестьдесят тарифов, каждый - прямая стоимость = m · объём + c. Для каждого объёма от −20 до 20 надо найти самый дешёвый тариф. Перебор - 60 прямых на каждый запрос.

Ответь себе до чтения: что общего у этих задач? Ответ урока: обе - про прямые и точки, и двойственность переводит одну постановку в другую. Первая решается за 780 шагов, а во второй из 60 тарифов выигрывают только 5, и их находит цепочка Эндрю.

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

Словарь между двумя языками. Фраза «три точки лежат на одной прямой» на языке прямых звучит как «три прямые проходят через одну точку». Перевод точный для принадлежности и порядка «выше / ниже» - расстояния и углы он не сохраняет. Иногда задача на одном языке звучит запутанно, а на другом - знакомо, и тогда её переводят, решают и переводят ответ обратно.

Здесь словарь - одна формула, а знакомая задача, к которой часто приводит перевод, - выпуклая оболочка.

Механизм: формула, два свойства и конфигурация

Формула. Точка p = (a, b) переходит в прямую p*: y = a·x − b. Прямая l: y = m·x + c - в точку l* = (m, −c). Вертикальные прямые в эту схему не попадают - у них нет наклона, и двойственность для них не определена; обычно их избегают поворотом координат.

Свойство 1 - принадлежность. p лежит на l, то есть b = m·a + c. Образ-прямая p* в точке x = m имеет высоту a·m − b = −c - это ровно высота точки l*. Значит, l* лежит на p*.

Свойство 2 - порядок. p над l значит b > m·a + c, то есть −c > a·m − b: точка l* над прямой p*. Не только «на», но и «выше / ниже» переводится без искажений.

Отсюда следствие: точки p₁, p₂, p₃ на одной прямой l - значит, все три прямые p₁*, p₂*, p₃* проходят через точку l*. Исключение - вертикальная l: у трёх точек один x, их образы - параллельные прямые с одним наклоном, а у самой l образа нет.

Конфигурация прямых. n прямых в общем положении (нет параллельных и трёх через одну точку) делят плоскость на части. Вершин - точек пересечения - n(n − 1)/2. Каждая прямая разрезана остальными на n кусков - рёбер всего n². Граней n(n + 1)/2 + 1: каждая новая прямая, пересекая k − 1 прежних, проходит через k граней и каждую разрезает надвое. Строится конфигурация добавлением прямых по одной, и на добавление уходит O(n) - так говорит теорема о зоне: грани, которые задевает новая прямая, вместе имеют O(n) рёбер. Итого O(n²).

Правило

Двойственность (a, b) ↔ y = a·x − b сохраняет принадлежность и порядок «выше / ниже». Три точки на прямой ↔ три прямые через точку; нижняя огибающая прямых ↔ верхняя оболочка их образов (m, −c), то есть нижняя оболочка точек (m, c). Конфигурация n прямых имеет n(n − 1)/2 вершин, n² рёбер, n(n + 1)/2 + 1 граней и строится за O(n²).

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

Двойственно задача звучит так: есть ли в конфигурации прямых вершина, где сходятся три прямые? Конфигурацию можно построить за n². Тот же порядок даёт приём попроще, без построения: для каждой точки сгруппировать направления на остальные. Три точки на прямой - это две точки в одном направлении от третьей, причём направление берётся с точностью до знака: точки могут лежать и по разные стороны. Ключ dx · 1000 + dy различает направления, пока |dy| меньше 500 - здесь координаты до 30.

import random
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 nod(a, b):
    a = abs(a)
    b = abs(b)
    while b > 0:
        a, b = b, a % b
    return a

random.seed(2)
tochki = []
while len(tochki) < 40:
    p = [random.randint(0, 30), random.randint(0, 30)]
    if p not in tochki:
        tochki.append(p)
n = len(tochki)

troek = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if povorot(tochki[i], tochki[j], tochki[k]) == 0:
                troek = troek + 1
print(troek, schet[0])

# для каждой точки - направления к следующим, сокращённые на НОД
shagov = 0
troek2 = 0
for i in range(n):
    gruppy = {}
    for j in range(i + 1, n):
        dx = tochki[j][0] - tochki[i][0]
        dy = tochki[j][1] - tochki[i][1]
        g = nod(dx, dy)
        dx = dx // g
        dy = dy // g
        if dx < 0 or (dx == 0 and dy < 0):
            dx = -dx
            dy = -dy
        klyuch = dx * 1000 + dy
        gruppy[klyuch] = gruppy.get(klyuch, 0) + 1
        shagov = shagov + 1
    for s in gruppy.values():
        troek2 = troek2 + s * (s - 1) // 2
print(troek2, shagov)

71 9880
71 780

Перебор троек нашёл 71 тройку за 9880 поворотов. Группировка - те же 71 за 780 шагов: каждая пара обрабатывается один раз. Направление (dx, dy) сокращается на НОД и приводится к одному знаку - тогда направления «вправо-вверх на 2 и 4» и «вправо-вверх на 1 и 2» совпадают точно, без деления и без углов. Если в группе s точек, они дают s(s − 1)/2 троек с текущей точкой.

Это n² - и, по всей видимости, существенно быстрее нельзя. Задача «есть ли три точки на прямой» трудна для 3SUM (Гаджентаан и Овермарс, 1995): алгоритм за n^(2 − ε) дал бы такой же для задачи «есть ли три числа с нулевой суммой», которую никто не умеет решать существенно быстрее n² - известные улучшения выигрывают лишь логарифмические множители.

Разбор: самый дешёвый тариф и оболочка

Тариф - прямая y = m·x + c. Самый дешёвый при объёме x - нижняя огибающая прямых. Двойственно каждая прямая - точка (m, −c); удобнее сменить знак второй координаты и взять точку (m, c) - тогда «ниже» остаётся «ниже», и прямая выигрывает хоть где-то - строго дешевле остальных на каком-то интервале, - только если её точка - вершина нижней оболочки. Проверка «средняя из трёх прямых лишняя» - это поворот точек (m, c).

import random

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

def znachenie(p, x):
    return p[0] * x + p[1]

def poryadok(p):
    # наклон по убыванию, при равном наклоне - меньший сдвиг первым
    return [-p[0], p[1]]

random.seed(5)
pryamye = []
for i in range(60):
    pryamye.append([random.randint(-50, 50), random.randint(-500, 500)])

# нижняя огибающая min(m·x + c): прямая посередине лишняя,
# если поворот точек (m, c) трёх прямых подряд не отрицателен
stek = []
for p in sorted(pryamye, key=poryadok):
    if len(stek) > 0 and stek[-1][0] == p[0]:
        continue
    while len(stek) >= 2 and povorot(stek[-2], stek[-1], p) >= 0:
        stek.pop()
    stek.append(p)
print(len(pryamye), len(stek))

# запросы по возрастанию x: указатель идёт по огибающей вперёд
sovpalo = 0
k = 0
for x in range(-20, 21):
    while k + 1 < len(stek):
        if znachenie(stek[k + 1], x) > znachenie(stek[k], x):
            break
        k = k + 1
    luchshee = znachenie(pryamye[0], x)
    for p in pryamye:
        luchshee = min(luchshee, znachenie(p, x))
    if znachenie(stek[k], x) == luchshee:
        sovpalo = sovpalo + 1
print(sovpalo)

60 5
41

Из шестидесяти тарифов на огибающую попали пять - остальные дороже какого-нибудь из этих пяти при любом объёме. Запросы по возрастанию x обходятся указателем, который идёт по огибающей только вперёд, - как калиперы в прошлой главе. Все 41 ответ совпали с перебором.

Это известный приём под названием «трюк с выпуклой оболочкой»: в динамическом программировании, где переход - минимум из линейных функций, он заменяет перебор n вариантов логарифмом или константой. Без двойственности он выглядит фокусом; с ней - это цепочка Эндрю для точек (m, c).

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

Наклоны дробями. Группировать направления по dy / dx в float - значит разносить совпадающие направления по разным группам из-за округления. Сокращение на НОД точно.

Равные наклоны в огибающей. Две параллельные прямые - две точки с одним m: для минимума нужна меньшая c, и её надо поставить первой при сортировке. Если поставить первой большую c, на этом же наборе неверными выходят 7 ответов из 41.

Вертикальные прямые в двойственности. Их образа нет: у вертикали нет наклона. Если во входе они возможны, координаты слегка поворачивают или обрабатывают вертикали отдельно.

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

Огибающая прямых - выбор тарифа, лучшая стратегия при меняющемся параметре, ускорение ДП. Двойственность применяют в компьютерной графике: в задаче о выборке лучей «прямоугольник, через который проходит больше всего лучей» переходит в задачу о точках, а мера равномерности выборки - отклонение - считается через конфигурацию прямых. Конфигурации стоят и за задачами «найти прямую, которая делит точки пополам», «самый тонкий треугольник среди точек».

Теперь сам

1. Образ точки (3, 4) и образ прямой y = −x + 2. Лежит ли точка на прямой - и что это значит для образов?
2. Сколько граней у конфигурации из 5 прямых в общем положении?
3. Тарифы y = 3x, y = x + 4, y = −x + 12. Попадает ли средний тариф на огибающую?