Почему вычислительную геометрию надёжнее считать в целых числах, а не в double с epsilon?
В разных разборах вижу противоречие: одни пишут всё в long long, другие заводят const double eps = 1e-9 и сравнивают через него. Почему целые предпочтительнее и в каких случаях double действительно опасен? Хочу понять, чтобы не ловить WA.
2 ответа
Ключевая мысль: большинство геометрических примитивов (ориентация, площадь, пересечение, сравнение углов) сводятся к знаку многочлена от координат — cross, dot, разности. Если входные координаты целые, эти знаки можно вычислить точно в long long/__int128, без какой-либо ошибки.
Как только ты переходишь в double, появляется ошибка округления (≈1e-15 относительно). На «вырожденных» тестах — три точки почти на одной прямой, две площади почти равны, точка ровно на границе — эта ошибка может перевернуть знак, и orient соврёт. Авторы задач специально такие тесты ставят.
С eps две беды: его трудно подобрать (слишком мал — ловишь ложные неравенства; слишком велик — склеиваешь разные значения), и сравнение через eps не транзитивно: a≈b и b≈c не дают a≈c. Это ломает сортировки и set.
Правило: держи координаты целыми сколько можешь, переходи в double только там, где без деления/корня не обойтись (координаты точки пересечения, расстояние). Все решающие сравнения — до перехода, в целых.
Когда double всё-таки неизбежен (вход — дробные координаты, или нужны длины/углы), минимизируй накопление ошибки: сравнивай не a == b, а fabs(a-b) < eps, и подбирай eps под масштаб задачи (например, 1e-9 при координатах до 1e6, но крупнее при больших значениях). Избегай вычитания близких больших чисел — это catastrophic cancellation, главный источник потери точности.
И помни про long double: на олимпиадах он часто даёт лишние 3-4 значащие цифры почти бесплатно и спасает пограничные тесты. Но это лечение симптомов — если вход целый, правильное лечение — вообще не выходить из целых чисел.