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

Скалярное произведение двух векторов — число:

$$(\vec{a}, \vec{b}) = |\vec{a}| \cdot |\vec{b}| \cdot \cos\alpha = a_x b_x + a_y b_y$$

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

Скалярное произведение симметрично: $(\vec{a}, \vec{b}) = (\vec{b}, \vec{a})$. Косинусу безразлично направление угла, потому что $\cos(-\alpha) = \cos\alpha$.

Геометрический смысл

Величина $|\vec{b}| \cos\alpha$ — длина проекции $\vec{b}$ на направление $\vec{a}$ (со знаком). Значит,

$$(\vec{a}, \vec{b}) = |\vec{a}| \cdot (\text{проекция } \vec{b} \text{ на } \vec{a})$$

Отсюда — вся польза.

Знак

знак $(\vec{a}, \vec{b})$	угол	смысл
положительный	меньше $90°$	смотрят «в одну сторону»
ноль	ровно $90°$	перпендикулярны
отрицательный	больше $90°$	смотрят «в разные стороны»

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

if (a * b == 0) { /* перпендикулярны */ }
if (a * b > 0)  { /* смотрят в одну сторону */ }

(В шаблоне скалярное произведение обычно вешают на operator*.)

Косинус и угол

Из определения сразу получается косинус:

$$\cos\alpha = \frac{a_x b_x + a_y b_y}{|\vec{a}| \cdot |\vec{b}|}$$

Соблазн взять acos от этого и получить угол. Так делать можно, но с оговоркой: acos возвращает значение от $0$ до $\pi$, то есть теряет знак угла. Развёрнут ли $\vec{b}$ относительно $\vec{a}$ влево или вправо, по косинусу не узнать.

Правильный способ — функция atan2, которая берёт оба произведения сразу:

long double angle = atan2(a % b, a * b);   // векторное, затем скалярное

Она возвращает угол от $-\pi$ до $\pi$, со знаком, и не требует ручного разбора случаев. Порядок аргументов запомнить легко: сначала то, что отвечает за синус (векторное), потом за косинус (скалярное).

Есть и вторая причина не считать угол без нужды: acos теряет точность у краёв диапазона, а из-за погрешности аргумент вообще может оказаться чуть больше единицы, и функция вернёт NaN. Если задача не просит угол явно — не считайте его.

Проекция точки

Проекция вектора $\vec{v}$ на направление $\vec{u}$:

$$\text{proj} = \frac{(\vec{u}, \vec{v})}{|\vec{u}|^2} \cdot \vec{u}$$

Знаменатель — квадрат длины, а не длина: одно деление вместо корня и нормировки.

Этим считается проекция точки на прямую и, через неё, симметричная точка.

Целые числа

Если координаты целые, скалярное произведение целое — никаких потерь точности. Считайте его в long long: при координатах до $10^9$ произведение доходит до $10^{18}$, и int переполнится молча.

Это одна из самых частых ошибок в геометрии: шаблон, написанный когда-то с int, годами работает и однажды даёт неверный ответ на большом тесте.

Что оно не умеет

Скалярное произведение не различает «слева» и «справа». Векторы $\vec{b}$ и его отражение относительно $\vec{a}$ дают одинаковое скалярное произведение — угол-то по модулю тот же.

Для стороны нужно векторное произведение. Вместе они полностью определяют взаимное расположение двух векторов.