Задача: Окопы и траншеи

На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты n окопов. Каждый окоп вырыт вдоль границы прямоугольника со сторонами, параллельными направлениям север–юг и запад–восток. При этом окопы могут иметь общие точки, но никакие два окопа не имеют общего участка ненулевой длины.

Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.

Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

Формат входных данных

Первая строка содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₁ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

Формат выходных данных

Выведите одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^-6.

Ваш ответ: