Задача 1HardГеометрияГрафыСистема непересекающихся множествDFS
Путь через квадрат с круглыми препятствиями
Условие задачи
Дан единичный квадрат с координатами от (0, 0) до (1, 1).
Внутри или около квадрата расположены круги-препятствия. Каждый круг задан как [x, y, r]: центр и радиус.
Нужно определить, существует ли путь из любой точки левой стороны квадрата в любую точку правой стороны квадрата.
Ограничения:
- нельзя заходить внутрь кругов;
- нельзя касаться кругов;
- нельзя выходить за пределы квадрата;
- касание кругов друг с другом или с границей считается блокировкой.
Сигнатура
def can_cross_square(circles: list[list[float]]) -> bool:Идея
Путь слева направо невозможен, если круги образуют непрерывный барьер от верхней стороны квадрата до нижней стороны квадрата.
Ваше решение
Консоль
Нажмите «Запустить проверки» или Ctrl+Enter