Гладстон Гандер идет через Дакбург и должен как можно скорее добраться до своего свидания с Дейзи Дак. Если он не успеет вовремя, Дональд может появиться и занять его место.
Недавно в Дакбурге стали предоставлять очень экологичный способ общественного транспорта: велосипеды. На многих велосипедных станциях по всему городу можно взять бесплатный велосипед, прокатиться на нем до другой велосипедной станции и оставить его там. У Гладстона имеется два метода передвижения: пешком или на велосипеде. Езда на велосипеде быстрее, конечно, однако он должен брать и оставлять велосипеды на назначенных станциях. Гладстон может ходить или ездить на велосипеде между любыми двумя точками по прямой.
Гладстон обладает картой (прямоугольного) центра Дакбурга. Его текущее положение и точка встречи с Дейзи находятся на этой карте. Карта также содержит местоположения всех велосипедных станций в пределах границ.
В городе может быть больше велосипедных станций, которые не находятся в пределах границ карты. Учитывая его удачу, Вы можете предположить, что в тот момент, когда Гладстон сходит (или съезжает на велосипеде) с карты, он встречает велосипедную станцию, если она ему подходит. Велосипедные станции, не находящиеся на карте, могут быть расположены за пределами карты, они не обязательно должны лежать в целочисленных координатах.
Задача Гладстона выяснить, какой маршрут лучше взять. Вы можете помочь ему? Учитывая карту и его бесконечное количество удачи, какое самое быстрое время для его свидания с Дейзи?
Состоит из:
одна строка содержит два целых числа v[walk]
и v[bike]
(1 ≤ v[walk]
< v[bike]
≤ 1 000) - скорость ходьбы и езды на велосипеде;
стрка из четырех целых чисел x[1]
, y[1]
, x[2]
и y[2]
(-10^6
≤ x[1]
< x[2]
≤ 10^6
, -10^6
≤ y[1]
< y[2]
≤ 10^6
) - граничные координаты карты центра Дакбурга;
строка из двух целых чисел x[G]
и y[G]
- местоположение Гладстона;
строка из двух целых чисел x[D]
и y[D]
- местоположение Дейзи;
строка с числом n (0 ≤ n ≤ 1000) - количество велостанций;
n строк, каждая с двумя целыми числами x[station]
и y[station]
- координатами имеющихся велостанций.
Все координаты заданы на карте центра, то есть x[1]
≤ x ≤ x[2]
и y[1]
≤ y ≤ y[2]
.
Выведите кратчайшее возможное время для Гладстона, чтобы добраться до Дейзи. Ваш ответ должен иметь абсолютную или относительную ошибку не более 10^(-6)
.