시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты 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