Косое (векторное) произведение на плоскости: что значит его знак и как определить ориентацию трёх точек?
Постоянно вижу в разборах функцию cross и фразу «точка C левее/правее прямой AB». Как через косое произведение определить, поворачивает ли путь A→B→C налево, направо или идёт прямо? Нужна каноничная функция ориентации.
2 ответа
Косое произведение векторов AB и AC равно (B-A) × (C-A). Его знак показывает взаимное расположение:
> 0— C слева от направленной прямой AB (поворот A→B→C против часовой стрелки, левый);< 0— C справа (поворот по часовой, правый);== 0— три точки коллинеарны (лежат на одной прямой).
// 1 = левый поворот (CCW), -1 = правый (CW), 0 = коллинеарны
int orient(const P& a, const P& b, const P& c) {
long long v = (b - a).cross(c - a);
return (v > 0) - (v < 0);
}
Это фундаментальный примитив всей вычислительной геометрии: на нём строятся пересечение отрезков, выпуклая оболочка, проверка точки в многоугольнике. Работает в целых числах — точно, без epsilon. Сложность O(1).
Геометрически |cross| — это удвоенная площадь треугольника ABC, поэтому знак напрямую связан с тем, «с какой стороны» лежит C.
Главная грабля — переполнение. (b-a).cross(c-a) при координатах до 1e9 доходит до ~8e18, на пределе long long. Если координаты больше — бери __int128:
int orient(const P& a, const P& b, const P& c) {
__int128 v = (__int128)(b.x-a.x)*(c.y-a.y) - (__int128)(b.y-a.y)*(c.x-a.x);
return (v > 0) - (v < 0);
}
И ещё: знак зависит от направления прямой. orient(a,b,c) и orient(b,a,c) противоположны по знаку — поменял местами A и B, поменялся смысл «лево/право». Всегда фиксируй порядок аргументов.