Как хранить точку и вектор в C++ для геометрии и какие операции сразу завести?
Каждый раз на олимпиаде пишу геометрию заново и путаюсь. Хочу один раз сделать аккуратную структуру точки/вектора, чтобы дальше всё (скалярное, косое, длина) считалось через неё. Какой минимальный набор операторов нужен и почему лучше держать координаты в long long, а не в double?
2 ответа
Точку и вектор удобно представлять одним типом: вектор — это просто разность двух точек. Базовый шаблон:
struct P {
long long x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
P operator+(const P& o) const { return {x + o.x, y + o.y}; }
long long cross(const P& o) const { return x * o.y - y * o.x; } // косое
long long dot(const P& o) const { return x * o.x + y * o.y; } // скалярное
long long len2() const { return x * x + y * y; } // квадрат длины
};
Ключевая идея: держи координаты целыми, пока можешь. Косое и скалярное произведение — это многочлены от координат, поэтому для целых входов они дают точный целый ответ без накопления ошибок. double вносит ошибку округления уже в простом сравнении a == b, и на стыковых тестах (точки на одной прямой, совпадающие площади) это даёт WA.
Все операции выше — O(1). Если координаты до 1e9, то cross доходит до ~1e18 — это влезает в long long (предел ~9.2e18), но int переполнится, поэтому long long обязателен.
Важный нюанс про переполнение в len2() и cross. Если координаты до 1e9 по модулю, то x*x ~ 1e18 — на грани, но ещё ок для long long. А вот если ты вычитаешь точки (a-b), координаты вектора могут стать до 2e9, и тогда cross доходит до ~8e18 — всё ещё влезает, но запас крошечный. При координатах до 1e9 это безопасно; если в задаче до 1e18 — нужны __int128 или нормировка. Поэтому всегда прикидывай максимум cross заранее: это самая частая причина «непонятного» WA в геометрии.