Утка на велосипеде
Утка на велосипеде
Гладстон Гандер идет через Дакбург и должен как можно скорее добраться до своего свидания с Дейзи Дак. Если он не успеет вовремя, Дональд может появиться и занять его место.
Недавно в Дакбурге стали предоставлять очень экологичный способ общественного транспорта: велосипеды. На многих велосипедных станциях по всему городу можно взять бесплатный велосипед, прокатиться на нем до другой велосипедной станции и оставить его там. У Гладстона имеется два метода передвижения: пешком или на велосипеде. Езда на велосипеде быстрее, конечно, однако он должен брать и оставлять велосипеды на назначенных станциях. Гладстон может ходить или ездить на велосипеде между любыми двумя точками по прямой.
Гладстон обладает картой (прямоугольного) центра Дакбурга. Его текущее положение и точка встречи с Дейзи находятся на этой карте. Карта также содержит местоположения всех велосипедных станций в пределах границ.
В городе может быть больше велосипедных станций, которые не находятся в пределах границ карты. Учитывая его удачу, Вы можете предположить, что в тот момент, когда Гладстон сходит (или съезжает на велосипеде) с карты, он встречает велосипедную станцию, если она ему подходит. Велосипедные станции, не находящиеся на карте, могут быть расположены за пределами карты, они не обязательно должны лежать в целочисленных координатах.
Задача Гладстона выяснить, какой маршрут лучше взять. Вы можете помочь ему? Учитывая карту и его бесконечное количество удачи, какое самое быстрое время для его свидания с Дейзи?
Входные данные
Состоит из:
одна строка содержит два целых числа
vwalk
иvbike
(1 ≤vwalk
<vbike
≤ 1 000) - скорость ходьбы и езды на велосипеде;стрка из четырех целых чисел
x1
,y1
,x2
иy2
(-106
≤x1
<x2
≤106
,-106
≤y1
<y2
≤106
) - граничные координаты карты центра Дакбурга;строка из двух целых чисел
xG
иyG
- местоположение Гладстона;строка из двух целых чисел
xD
иyD
- местоположение Дейзи;строка с числом n (0 ≤ n ≤ 1000) - количество велостанций;
n строк, каждая с двумя целыми числами
xstation
иystation
- координатами имеющихся велостанций.
Все координаты заданы на карте центра, то есть x1
≤ x ≤ x2
и y1
≤ y ≤ y2
.
Выходные данные
Выведите кратчайшее возможное время для Гладстона, чтобы добраться до Дейзи. Ваш ответ должен иметь абсолютную или относительную ошибку не более 10-6
.
1 8 0 0 10 10 5 1 5 9 3 5 8 2 2 9 6
3.000000000
5 100 0 -100000 100000 0 5 -30000 40000 -5 0
501.9987496