Как сортировать точки по полярному углу через cross, а не через atan2?
Для алгоритма Грэхема и подобных нужно отсортировать точки по углу относительно центра. Очевидное решение — atan2(y, x), но это double и потенциальные проблемы с точностью. Как сравнивать углы через косое произведение, целочисленно?
2 ответа
Идея: вместо вычисления самого угла сравнивай два вектора напрямую через cross. a × b > 0 означает, что a по углу раньше b (b левее a). Но cross различает направления только в пределах полуоборота, поэтому сначала делим точки на две половины (верхнюю и нижнюю) по знаку, а внутри половины сравниваем косым произведением:
int half(const P& p) { // 0 для верхней полуплоскости, 1 для нижней
return (p.y < 0 || (p.y == 0 && p.x < 0)) ? 1 : 0;
}
bool byAngle(const P& a, const P& b) {
int ha = half(a), hb = half(b);
if (ha != hb) return ha < hb; // разные полуплоскости
long long c = a.cross(b);
if (c != 0) return c > 0; // a левее b -> a раньше
return a.len2() < b.len2(); // одинаковый угол: ближе раньше
}
Функция half обеспечивает корректный порядок через все 360°, а cross сравнивает внутри полуоборота точно в целых числах. При коллинеарных векторах (один угол) добавляем тай-брейк по длине. Сортировка — O(n log n), сравнение O(1).
Почему не atan2: он возвращает double, и два разных вектора с одинаковым углом могут дать чуть отличающиеся значения из-за округления — сортировка станет нестабильной и порядок «поплывёт» на коллинеарных точках. На стресс-тестах это даёт WA в выпуклой оболочке Грэхема.
Целочисленное сравнение через cross точное и детерминированное. Единственная грабля — переполнение cross при больших координатах (бери __int128) и аккуратность с центром: если сортируешь не относительно нуля, а относительно точки O, сначала вычти O из всех точек, иначе half и cross посчитаются неверно. Точку-центр в сортировку не включай.