Векторное произведение

Векторное произведение на плоскости — тоже число (в трёхмерии это вектор, отсюда название):

$$[\vec{a}, \vec{b}] = |\vec{a}| \cdot |\vec{b}| \cdot \sin\alpha = a_x b_y - a_y b_x$$

В отличие от скалярного, оно антисимметрично: $[\vec{a}, \vec{b}] = -[\vec{b}, \vec{a}]$, потому что $\sin(-\alpha) = -\sin\alpha$.

Именно эта асимметрия и делает его полезным: знак различает стороны.

Знак

знак $[\vec{a}, \vec{b}]$	смысл
положительный	$\vec{b}$ слева от $\vec{a}$, поворот против часовой
ноль	векторы коллинеарны (сонаправлены или противоположны)
отрицательный	$\vec{b}$ справа от $\vec{a}$, поворот по часовой

Формулировка «слева» означает: встав в начало и глядя вдоль $\vec{a}$, до $\vec{b}$ ближе повернуться влево, чем вправо.

Это второе из двух главных применений: проверка коллинеарности и определение стороны.

Вместе со скалярным

Два произведения вместе однозначно определяют, где находится один вектор относительно другого:

скалярное	векторное	расположение
$> 0$	$> 0$	впереди слева
$> 0$	$= 0$	ровно вперёд
$> 0$	$< 0$	впереди справа
$= 0$	$> 0$	ровно налево
$= 0$	$< 0$	ровно направо
$< 0$	$> 0$	назад и влево
$< 0$	$= 0$	ровно назад
$< 0$	$< 0$	назад и вправо

Восемь случаев, и все различаются двумя сравнениями с нулём. Задача «в какую сторону повернул объект» решается прямо по этой таблице.

Связь между произведениями

Обозначим $\vec{b}^{\,\perp}$ вектор $\vec{b}$, повёрнутый на $-90°$, то есть $(b_y, -b_x)$. Тогда

$$[\vec{a}, \vec{b}] = (\vec{a}, \vec{b}^{\,\perp})$$

Проверяется подстановкой: $(\vec{a}, (b_y, -b_x)) = a_x b_y - a_y b_x$. Проверено численно на двухстах тысячах случайных пар — тождество выполняется.

Смысл: это одно и то же произведение, просто второй аргумент повёрнут на прямой угол. Отсюда и совпадение картинок из предыдущей статьи, сдвинутое на четверть оборота.

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

Площадь

Модуль векторного произведения — площадь параллелограмма на векторах $\vec{a}$ и $\vec{b}$. Значит, площадь треугольника:

$$S_{ABC} = \frac{1}{2}\bigl|[\vec{AB}, \vec{AC}]\bigr|$$

Никаких высот и синусов — одна формула по координатам. И, что важно, без деления, если убрать двойку: удвоенная площадь треугольника с целыми координатами всегда целая.

Отсюда же площадь многоугольника (формула площади Гаусса):

long long doubledArea = 0;
for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    doubledArea += p[i] % p[j];   // векторное произведение
}
// площадь = |doubledArea| / 2

Знак суммы говорит об ориентации обхода: положительный — против часовой стрелки, отрицательный — по часовой. Это часто требуется отдельно.

Формула работает для любого несамопересекающегося многоугольника, в том числе невыпуклого.

Где применяется

Три точки на одной прямой? $[\vec{AB}, \vec{AC}] = 0$.

По какую сторону от прямой лежит точка? Знак $[\vec{AB}, \vec{AP}]$. Это основа проверки пересечения отрезков.

Выпуклая оболочка. На каждом шаге проверяют, поворачивает ли очередная точка влево; если нет, предыдущую выбрасывают. Проверка — знак векторного произведения.

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

Сравнение по углу. Сортировка точек вокруг центра делается компаратором на векторных произведениях, без вычисления самих углов, — и это точнее и быстрее, чем через atan2.

Целые числа

Как и скалярное, векторное произведение целых координат целое. long long обязателен: при координатах до $10^9$ значение доходит до $2 \cdot 10^{18}$, то есть впритык к границе типа.

Если координаты могут быть до $10^{18}$ (например, после разности), нужен __int128 — либо переход к другой формулировке задачи.

Главное преимущество целых координат здесь в том, что сравнение с нулём точное. Никаких эпсилонов, никаких «почти коллинеарны». Поэтому в геометрии всегда стоит спросить себя, нельзя ли обойтись без вещественных чисел.