eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Робот

Робот

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Роботу нужно пройти по плоскости из точки A в точку B. Пройти по прямой не всегда возможно из-за препятствий. Требуется написать программу, вычисляющую минимальную длину пути робота из точки A в точку B. Будем считать размеры робота пренебрежимо малыми по сравнению с преодолеваемым расстоянием и размером препятствий. Будем считать, что все препятствия представлены набором отрезков на плоскости. Эти отрезки робот не может пересекать во внутренних точках, но он может проходить через концы отрезков, а также может ходить вдоль отрезка.

Входные данные

Первая строка содержит одно целое число N — количество отрезков-препятствий (0 <= N <= 100). Затем идут N строк по четыре целых числа X_1, Y_1, X_2 и Y_2 в каждой. Это координаты концов соответствующего отрезка. Последние две строки содержат координаты X и Y точек A и B. Гарантируется, что все координаты по модулю не превосходят 1000, а также ни один из концов отрезков не принадлежит другому отрезку. Начальная и конечная точки пути различны и не принадлежат ни одному отрезку.

Выходные данные

Выведите одно число — длину кратчайшего пути из точки A в точку B с четырьмя знаками после десятичной точки. Если искомого пути не существует, то выведите –1.

Пример

Входные данные #1
1
5 -2 5 3
10 0
0 0
Выходные данные #1
10.7703
Автор Павел Кузнецов