Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Path
Задача Кратчайший Путь (PATH)

На плоскости заданы N прямоугольников со сторонами, параллельными осям координат, и две различные точки A и B. Никакие два прямоугольника не пересекаются и не касаются друг друга. Точки и B не принадлежат ни одному из прямоугольников. Путь между точками A и B может касаться вершин и проходить вдоль сторон прямоугольников, однако не должен заходить внутрь прямоугольников. Определите длину L  кратчайшего пути между точками и 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


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"