Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Окопы и траншеи

 На полигоне,на котором проводятся военные учения сухопутных войск Bykhovtown, вырыты 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 ≤ xAyAxByB ≤ 104). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

Выходные данные:

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


Примеры:
input.txt output.txt
1 3
0 4 10 11
3 7 7 9
3 0 7 2
4 9
5 0
4

Сложность задачи: 20%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 40, зарегистрированных 4:
Marichka, cor Sabrr, Fate, Myronets21,
[Данные за последние 5 минут]