DISJOINT
SET UNION
Связываем пересекающиеся части кругов и границы TOP/BOTTOM. Ранний выход, если они оказались в одной компоненте.
Иногда кратчайший путь к ответу — вообще не искать путь. Вместо пикселей и догадок — топология, точная арифметика и проверяемый код.
Я перевёл задачу поиска маршрута в проверку связности препятствий. Вместо перебора траекторий алгоритм выясняет, появилась ли непрерывная цепочка кругов от верхней границы прямоугольника до нижней.
Важны не только скорость и верный ответ, но и граничные случаи: касания, внешние центры и пересечения за пределами прямоугольника. Поэтому геометрические проверки выполняются точно, а четыре алгоритма можно сравнить на одних данных.
Перетаскивайте круги, меняйте радиусы, переключайте алгоритмы и наблюдайте, как вычисление превращается в доказательство.
Исходные координаты и круги.
Важно: True/False рассчитывается точной целочисленной геометрией. Линия найденного маршрута — дополнительная дискретная иллюстрация (A* + проверка отрезков), а не часть доказательства; узкая допустимая дорожка может не отобразиться на сетке.
Четыре способа анализа одной геометрической задачи — от обхода графа до пространственного отсечения. Переключатели выполняют реальный код.
Связываем пересекающиеся части кругов и границы TOP/BOTTOM. Ранний выход, если они оказались в одной компоненте.
Начинаем со всех кругов, касающихся верхней стороны, и проверяем достижимость нижней. Перебор соседей — по запросу.
Тот же геометрический граф, но поиск в глубину. Удобно для сравнения порядка исследования и проверки связности.
Сортируем круги по X и отбрасываем пары с заведомо несовместимыми проекциями. На оставшихся работает тот же точный предикат и DSU.
Для конечного набора замкнутых дисков в прямоугольнике отсутствие пути от левой стороны к правой эквивалентно существованию связной цепочки препятствий от верхней стороны до нижней.
⌁Два полных круга могут касаться за пределами области. Поэтому проверяем не просто distance ≤ r₁ + r₂, а непустоту D₁ ∩ D₂ ∩ R с целочисленными сравнениями — без округления и epsilon.
Python с произвольной точностью целых; TypeScript и JavaScript с BigInt. Исходный код можно копировать и запускать отдельно.
Проверяются исходные примеры и случаи, в которых наивные реализации обычно ломаются: касания, нулевой радиус, внешние центры и большие числа.