| Задача Кратчайший Путь (PATH)
На плоскости заданы
N прямоугольников
со сторонами, параллельными осям координат, и две различные точки A и B. Никакие два прямоугольника не
пересекаются и не касаются друг друга. Точки
A и
B не принадлежат ни одному из прямоугольников. Путь между точками
A и
B может
касаться вершин и проходить вдоль сторон прямоугольников, однако не должен
заходить внутрь прямоугольников. Определите длину
L кратчайшего пути между точками
A и
B
Формат ввода/вывода:
Напишите программу
PATH,
которая читает c клавиатуры координаты точек и
прямоугольников и выводит длину кратчайшего пути L.
на экран
В первой строке ввода находится число N. Во второй строке находятся координаты
XA и YA точки
A. В третьей строке находятся координаты XB
и YB точки
B . В последующих
N
строчках находятся по четыре
числа Xk1 Yk1 Xk2 Yk2
– координаты противоположных вершин
k-го прямоугольника.
Искомая длина должна быть определена с точностью до 10-5 (это
означает, что ваш ответ не должен отличаться от ответа жюри больше чем на 10-5).
Ограничения: 1<=N<=30
Пример:
|
Ввод
2
1.0 10.0
20.0 7.0
5.0 8.0 9.0 20.0
11.0 9.0 15.0 3.0
|
Вывод
20.093368739633874
|
| 
