← Все вопросы
Почему сравнение double через eps опасно в геометрии и как минимизировать вред?
9
Все говорят «не сравнивай double напрямую, используй eps». Но я несколько раз ловил WA именно из-за неудачного eps. В чём конкретно опасность сравнения с epsilon и какие правила помогают не выстрелить себе в ногу, когда double всё-таки неизбежен?
2 ответа
14
✓ Принятый ответ — помог автору
Опасностей у eps-сравнения несколько:
- Не транзитивно. Из
|a−b|<epsи|b−c|<epsне следует|a−c|<eps. Это ломает сортировки,set, бинпоиск: компаратор перестаёт быть строгим порядком, и поведение становится undefined (вплоть до падения). - Зависит от масштаба. Фиксированный
eps=1e-9хорош при координатах до 1e6, но при координатах до 1e9 ошибка округления самих чисел уже больше eps → ложные «равенства». А при крошечных значениях, наоборот, eps склеит разные числа. - Подбор наугад. Слишком мал — ловишь фантомные неравенства; слишком велик — теряешь реальные различия. Идеального eps часто нет.
Главное правило: если вход целочисленный — не уходи в double для решающих сравнений вообще. Ориентацию, пересечение, площадь, сравнение углов считай в long long/__int128 через cross/dot — там сравнение точное и транзитивное.
7
Когда double неизбежен (дробный вход, длины, тригонометрия), минимизируй вред:
- Относительный eps, а не абсолютный: сравнивай
|a−b| <= eps * max(1.0, |a|, |b|), чтобы порог рос с масштабом чисел. long doubleдаёт лишние значащие цифры почти бесплатно — часто спасает пограничные тесты.- Избегай вычитания близких больших чисел (catastrophic cancellation) — переформулируй выражение, чтобы вычитать малое из малого.
- Никогда не строй компаратор сортировки на eps-равенстве — для сортировки используй точное
<без зоны «равно», а eps применяй только в финальных да/нет-проверках. - Если можно домножить, чтобы избавиться от деления — домножай и сравнивай целые произведения крест-накрест (
a/b < c/d→a*d < c*bс учётом знаков). Это превращает дробное сравнение в точное целое.
Ваш ответ
Войдите, чтобы ответить на вопрос.