Как определить взаимное расположение точки и окружности (внутри/на/снаружи) целочисленно?
Дана окружность центром (cx, cy) и радиусом r (всё целое) и точка (x, y). Нужно понять: точка внутри, на окружности или снаружи. Очевидно, можно сравнить расстояние с r, но не хочется ловить ошибки из-за sqrt. Как сделать точно?
2 ответа
Не извлекай корень — сравнивай квадраты. Расстояние от точки до центра в квадрате это dx*dx + dy*dy, и его сравниваем с r*r:
// -1 внутри, 0 на окружности, +1 снаружи
int pointVsCircle(long long cx, long long cy, long long r,
long long x, long long y) {
long long dx = x - cx, dy = y - cy;
long long d2 = dx * dx + dy * dy;
long long r2 = r * r;
return (d2 > r2) - (d2 < r2);
}
Идея: sqrt(d2) <=> r равносильно d2 <=> r2 (обе части неотрицательны), но сравнение квадратов точное в целых числах — никакого double, никакого epsilon, никакого риска, что sqrt(25) вернёт 4.9999999. Сложность O(1).
Этот приём «сравнивай квадраты вместо расстояний» — основной в геометрии: используй его везде, где нужно только сравнить или проверить попадание, а не получить само численное расстояние.
Грабля одна — переполнение. При координатах до 1e9 разности dx, dy до ~2e9, а dx*dx до ~4e18 — на грани long long, а сумма dx*dx + dy*dy до ~8e18 ещё влезает (предел ~9.2e18), но запас крошечный. Если координаты или радиус больше — бери __int128 для d2 и r2.
То же правило работает для «точка внутри круга описанного» (тест incircle через определитель 3×3 или 4×4) в задачах на триангуляцию Делоне, и для проверки пересечения двух окружностей: расстояние между центрами в квадрате сравниваешь с (r1+r2)^2 и (r1−r2)^2 — снова всё целочисленно, без sqrt.