На плоскости заданы 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 |