Точки, векторы и произведения

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

Вектор — направленный отрезок, задаваемый разностью координат концов; над векторами определены скалярное и векторное (в 2D — псевдоскалярное) произведения.

Зачем это в олимпиадах

Геометрические задачи — отдельный, технически коварный класс олимпиад: выпуклые оболочки, пересечения, площади, принадлежность точки многоугольнику. Почти всё в 2D-геометрии сводится к двум операциям над векторами: скалярному произведению (отвечает за углы и проекции) и псевдоскалярному (косому, отвечает за площади и ориентацию). Освоив их, вы решаете большинство геометрических задач целочисленной арифметикой, без тригонометрии и без накопления ошибок плавающей точки. Это критично: геометрия на float — главный источник «почти правильных» решений, которые получают WA.

Точки и векторы

Точку на плоскости задаём парой координат (x, y). Вектор из точки A в точку B — это разность B − A = (B.x − A.x, B.y − A.y). Векторы складывают покоординатно и умножают на число. Длина вектора (x, y) равна √(x2+y2), но на олимпиадах длину стараются не извлекать (корень — это float), а сравнивать квадраты длин, оставаясь в целых числах.

def sub(A, B):
    return (A[0] - B[0], A[1] - B[1])     # вектор B->A

def dist2(A, B):
    dx, dy = A[0] - B[0], A[1] - B[1]
    return dx * dx + dy * dy               # квадрат расстояния (целое!)

A, B = (1, 2), (4, 6)
print(sub(B, A))           # вектор из A в B
print(dist2(A, B))         # 9 + 16 = 25 = 5^2
import math
print(math.isqrt(dist2(A, B)))   # 5 — точное расстояние (квадрат точный)

Вывод:

(3, 4)
25
5

Скалярное произведение

Скалярное произведение векторов a = (a₁, a₂) и b = (b₁, b₂) равно a·b = a₁b₁ + a₂b₂ = |a||b|cosθ, где θ — угол между ними.

Скалярное произведение отвечает за углы. Его знак говорит, острый угол или тупой: a·b > 0 — угол острый, < 0 — тупой, = 0 — векторы перпендикулярны. Это позволяет проверять перпендикулярность и оценивать «направленность» без вычисления самого угла.

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

print(dot((1, 0), (0, 1)))     # 0 -> перпендикулярны
print(dot((1, 1), (1, 0)))     # 1 -> острый угол
print(dot((1, 0), (-1, 1)))    # -1 -> тупой угол

Вывод:

0
1
-1

Псевдоскалярное (косое) произведение

Псевдоскалярное произведение (косое, z-компонента векторного) векторов a и b равно a × b = a₁b₂ − a₂b₁ = |a||b|sinθ.

Это, пожалуй, самая важная операция 2D-геометрии. Её модуль равен площади параллелограмма на векторах a и b, а знак задаёт ориентацию: a × b > 0, если b повёрнут от a против часовой стрелки (левый поворот); < 0 — по часовой (правый); = 0 — векторы коллинеарны (лежат на одной прямой). Косое произведение отвечает на вопрос «в какую сторону поворачивает путь», не вычисляя углов.

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

print(cross((1, 0), (0, 1)))    # 1 > 0 -> поворот влево (против часовой)
print(cross((1, 0), (0, -1)))   # -1 < 0 -> поворот вправо (по часовой)
print(cross((1, 1), (2, 2)))    # 0 -> коллинеарны

Вывод:

1
-1
0

Ориентация трёх точек

Главное применение косого произведения — определить, как расположены три точки A, B, C: лежат ли они «левым поворотом», «правым» или на одной прямой. Берём векторы AB и AC и считаем их косое произведение. Знак — это ориентация. Эта функция — кирпич для выпуклой оболочки, проверки пересечений, площади.

def orientation(A, B, C):
    # косое произведение векторов AB и AC
    val = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    if val > 0:
        return 1       # против часовой (левый поворот)
    elif val < 0:
        return -1      # по часовой (правый поворот)
    return 0           # коллинеарны

print(orientation((0, 0), (4, 0), (0, 3)))    # 1: левый поворот
print(orientation((0, 0), (4, 0), (0, -3)))   # -1: правый поворот
print(orientation((0, 0), (2, 2), (4, 4)))    # 0: на одной прямой

Вывод:

1
-1
0

Все три операции выше — целочисленные, если координаты целые. Это золотое правило олимпиадной геометрии: избегайте float, где можно. Косое и скалярное произведения, сравнение квадратов длин — всё считается точно в int, и Python с его длинными целыми никогда не переполнится (в C++ берегитесь: произведение координат до 10⁹ требует long long).

Разбор задачи: угол между векторами и сортировка по углу

Связка скалярного и косого произведений даёт полный контроль над углами без тригонометрии. Косое произведение определяет знак синуса (по какую сторону), скалярное — знак косинуса (вперёд/назад). Вместе они однозначно задают четверть, в которой лежит вектор, что позволяет сортировать точки по полярному углу целочисленно — ключевой шаг построения выпуклой оболочки и заметания. Сравним два вектора: какой «раньше» при обходе против часовой стрелки от положительного направления оси X.

def half(v):
    # 0 для верхней полуплоскости (включая +X), 1 для нижней
    return 0 if (v[1] > 0 or (v[1] == 0 and v[0] > 0)) else 1

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

def polar_less(a, b):
    # a раньше b по полярному углу против часовой от +X?
    ha, hb = half(a), half(b)
    if ha != hb:
        return ha < hb            # верхняя полуплоскость идёт раньше нижней
    return cross(a, b) > 0       # внутри полуплоскости — по знаку косого

vectors = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1)]
import functools
ordered = sorted(vectors, key=functools.cmp_to_key(
    lambda a, b: -1 if polar_less(a, b) else 1))
print(ordered)

Вывод:

[(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1)]

Векторы выстроились по возрастанию полярного угла: от +X против часовой стрелки через верхнюю полуплоскость, затем через нижнюю. Деление на полуплоскости (half) нужно потому, что косое произведение само по себе не отличает углы, различающиеся на 180°. Вся сортировка — целочисленная, без atan2 и его погрешностей. Это фундамент алгоритма Грэхема для выпуклой оболочки.

Подводные камни

• Не путайте произведения. Скалярное (a₁b₁+a₂b₂) — про углы; косое (a₁b₂−a₂b₁) — про площадь и ориентацию.
• float — враг. Длины и углы через sqrt/atan2 накапливают ошибку. Где можно, сравнивайте квадраты и используйте знак косого произведения.
• Переполнение в C++. Произведение больших координат выходит за int; берите long long. В Python проблемы нет.
• Порядок аргументов в косом. a×b = −(b×a): перестановка меняет знак (и смысл ориентации).

Итог

• Вектор — разность координат; расстояние сравнивайте по квадрату (целое).
• Скалярное a·b=a₁b₁+a₂b₂: знак — острый/тупой угол, ноль — перпендикулярность.
• Косое a×b=a₁b₂−a₂b₁: модуль — площадь параллелограмма, знак — ориентация.
• Ориентация трёх точек через знак косого произведения AB×AC — целочисленно и точно.