Contest.samsu.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача D. Легкий путь

Задачу добавил: alef

Успешно сдано решений: 23

Ограничения: время на тест - 2с, память - 256 Мб

Планета у Сириуса показалась Василию не особо гостеприимной. Что космодром, что телепорт выглядели на редкость обшарпанными, как в каком-нибудь заштатном городишке на Земле. А ведь он приехал во второй по величине город планеты. Впрочем, он не собирался задерживаться здесь долго. За пределами зоны телепорта его ждал сотрудник музея.
Некоторая проблема состояла в том, что Василию нужно было перейти через прикосмодромную площадь, на которой ремонтировали покрытие. Во многих местах оно было снято, и идти по этой грязи (конечно, ремонт не успели закончить до наступления сезона дождей), а уж тем более везти чемодан на колесиках Василию не очень хотелось. Доброжелательные служители телепорта выдали ему одноразовые сапоги-бахилы. Но чемодан Василию придется нести. И, конечно, он хочет нести его как можно меньше.
Оставшееся на прикосмодромной площади покрытие можно описать множеством прямоугольников разного размера (некоторые прямоугольники могут перекрываться). Василий решил не спешить, а пойти так (пусть и довольно кружным путем), чтобы суммарное расстояние, которое ему придется пройти по грязи, было бы минимально возможным. Ваша задача - найти это минимальное суммарное расстояние.

Формат входного файла input.txt
Первая строка - четыре целых числа XS, YS, XF, YF (0 <= |XS|, |YS|, |XF|, |YF| <= 1000) через пробел - координаты точки, в которой Василий находится (XS, YS), и координаты точки, в которую ему нужно попасть (XF, YF)
Вторая строка - целое число N (1 <= N <= 1000) - количество прямоугольников, описывающих оставшееся покрытие
В каждой из следующих N строк содержатся 4 целых числа через пробел, по абсолютной величине не превосходящие 1000, - координаты левого верхнего (первые два числа) и правого нижнего (третье и четвертое) угла очередного прямоугольника.

Формат выходного файла output.txt
Первая строка - вещественное число с точностью не менее 6 знаков после десятичной точки, минимально возможное расстояние, которое Василию все же придется пройти по грязи.

Пример входного файла - 1 (см. рис.):
-2 -2 6 8
8
6 2 10 0
7 9 8 6
3 9 5 7
-2 7 2 4
1 2 3 1
9 6 10 1
-3 0 0 -3
2 4 7 3

Пример выходного файла - 1:
4.41421356237

Рисунок: Один из возможных путей для теста 1 (красным показан путь по грязи):



Пример входного файла - 2:
-6 -2 4 -2
5
-7 -1 -5 -3
-2 -1 -1 -2
3 -1 5 -3
-4 2 -3 0
0 1 2 0


Пример выходного файла - 2:
5.65685424949

Сдать задачу

Задать вопрос жюри по этой задаче