21/11/2024 20:09:53

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

591. Лабиринт

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Археолог закончил исследование пирамиды и переехал на Кипр, где стал руководить раскопками сооружения, от которого осталось несколько стен.

Чтобы быстро перемещаться по месту раскопок и не заблудиться в этом лабиринте из стен, ему необходима программа для КПК, определяющая кратчайший путь между двумя заданными точками.

В первой строке ввода содержатся 5 целых чисел `N`, `x_a`, `y_a`, `x_b`, `y_b` (`1\ ≤\ N\ ≤\ 50`, `0\ ≤\ x_a,\ y_a,\ x_b,\ y_b\ ≤1000`) – количество стен и координаты начальной и конечной точки пути. Далее следует `N` строк, в каждой строке 4 целых числа в диапазоне от 0 до 1000 – координаты концов `i`-й стены. Стены имеют ненулевую длину, не пересекаются, но могут соприкасаться краями. Начальная и конечная точка пути не попадают ни на одну из стен.

Разрешается идти вплотную к стене, но нельзя перелезать через стену или проходить сквозь нее или место стыковки стен.

Вывести длину кратчайшего пути с точностью `10^{-3}`. Если пройти невозможно, то вывести сообщение "IMPOSSIBLE".

Пример ввода

2 10 20 40 5
20 0 100 0
20 0 20 50

Пример вывода

80.867

12/10/2007	Личное первенство Южного Урала (I)
16/07/2018	Лето 2018 - 10 (E)
07/10/2023	Тренировка 1 (проводит gribanov) (H)