Задача №602. Окопы и траншеи
На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты n окопов. Каждый окоп вырыт вдоль границы прямоугольника со сторонами, параллельными направлениям север–юг и запад–восток. При этом окопы могут иметь общие точки, но никакие два окопа не имеют общего участка ненулевой длины.
Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.
Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.
Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.
Формат входных данных
Первая строка входного файла содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x1, y1, x2, y2 — координатами юго-западного и северо-восточного углов, соответственно (–104 ≤ x1 < x2 ≤ 104, –104 ≤ y1 < y2 ≤ 104).
Последние две строки содержат по два целых числа: xA, yA — координаты точки A и xB, yB — координаты точки B, соответственно (–104 ≤ xA, yA, xB, yB ≤ 104). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.
Формат выходных данных
Выведите в выходной файл одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10–6.
Примеры
| Входные данные | Выходные данные | рисунок |
| 3 0 4 10 11 3 7 7 9 3 0 7 2 4 9 5 0 | 4 |  |
| 2 0 0 3 3 6 6 9 9 1 3 7 9 | 4.24264068711928515 |
|
| 2 0 0 6 6 3 3 9 9 1 6 7 9 | 0 |  |
