Почему опасно сравнивать полярные углы через atan2 и как это ломает выпуклую оболочку Грэхема?
Реализовал оболочку Грэхема: сортирую точки по полярному углу через atan2(y, x), потом строю стек. На случайных тестах работает, но на одном падает в WA. Подозреваю сортировку по atan2. В чём именно опасность и как переписать сортировку, чтобы не было проблем с точностью?
2 ответа
atan2 возвращает double, и в этом корень проблемы. Две точки, лежащие на одном луче из центра (коллинеарные, одинаковый истинный угол), могут получить чуть разные значения atan2 из-за округления. Тогда компаратор сочтёт их «разными по углу» и поставит в произвольном порядке — а для Грэхема порядок коллинеарных точек критичен: при равных углах ближняя/дальняя должны идти в строго определённой последовательности, иначе стек снимет не те вершины и оболочка построится неверно.
Правильно — сравнивать углы через косое произведение, целочисленно, без вычисления самого угла:
P O; // опорная точка (нижняя-левая)
bool byAngle(const P& a, const P& b) {
long long c = (a - O).cross(b - O);
if (c != 0) return c > 0; // a раньше b по углу (точно, в целых)
return (a - O).len2() < (b - O).len2(); // равный угол: ближе раньше
}
Поскольку для Грэхема опорная точка — нижняя (минимум по y, потом по x), все остальные точки лежат в верхней полуплоскости, и одного cross хватает на весь диапазон углов без деления на полуплоскости. Сравнение точное, транзитивное, без epsilon. Сортировка O(n log n).
Дополнительная грабля Грэхема именно на коллинеарных точках последнего угла. Даже с правильным целочисленным компаратором классическая реализация требует особой обработки точек, коллинеарных с опорной на крайнем луче — иначе они могут «срезаться» неверно. Многие поэтому вообще переходят на monotone chain Эндрю: он сортирует просто по координатам (x, потом y), а не по углу, и поэтому свободен и от atan2, и от возни с опорной точкой — та же асимптотика O(n log n), но кода меньше и граничные случаи проще.
Если всё же остаёшься на Грэхеме: опорную точку выбирай детерминированно (строгий минимум по (y, x)), коллинеарные с опорной точки на последнем ребре обрабатывай явно, и помни про __int128 в cross при больших координатах. Но мой практический совет — для оболочки бери Эндрю, а сортировку по полярному углу через cross оставь для задач, где угол нужен сам по себе (радиальная развёртка, видимость).