Роботу нужно
пройти по плоскости из точки A в точку B. Пройти по прямой не
всегда возможно из-за препятствий. Требуется написать программу, вычисляющую
минимальную длину пути робота из точки A в точку B. Будем считать
размеры робота пренебрежимо малыми по сравнению с преодолеваемым расстоянием и
размером препятствий. Будем считать, что все препятствия представлены набором
отрезков на плоскости. Эти отрезки робот не может пересекать во внутренних
точках, но он может проходить через концы отрезков, а также может ходить вдоль
отрезка.
Время
тестирования: 1 секунда на один тест.
Первая строка
входного файла содержит одно целое число N — количество
отрезков-препятствий (0 £ N £ 100). Затем идут N строк
по четыре целых числа x1, y1,
x2 и y2
в каждой. Это координаты концов соответствующего отрезка. Последние две строки
содержат координаты x и y точек A и B. Гарантируется, что все координаты
по модулю не превосходят 1000, а также ни один из концов отрезков не
принадлежит другому отрезку. Начальная и конечная точки пути различны и не
принадлежат ни одному отрезку.
Выведите в выходной
файл одно число — длину кратчайшего пути из точки A в точку B
с четырьмя знаками после десятичной точки. Если искомого пути не существует, то
выведите –1.
Примеры
|
input
|
output
|
|
1
5 -2 5 3
10 0
0 0
|
10.7703
|
|
2
0 0 2 0
3 0 10 0
-100 0
100 0
|
200.0000
|
|
3
-1 -1 6 6
4 6 11 -1
-1 0 11 0
2 1
-100 -100
|
-1
|
