eolymp
bolt
Try our new interface for solving problems
Məsələlər

Утка на велосипеде

Утка на велосипеде

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Гладстон Гандер идет через Дакбург и должен как можно скорее добраться до своего свидания с Дейзи Дак. Если он не успеет вовремя, Дональд может появиться и занять его место.

Недавно в Дакбурге стали предоставлять очень экологичный способ общественного транспорта: велосипеды. На многих велосипедных станциях по всему городу можно взять бесплатный велосипед, прокатиться на нем до другой велосипедной станции и оставить его там. У Гладстона имеется два метода передвижения: пешком или на велосипеде. Езда на велосипеде быстрее, конечно, однако он должен брать и оставлять велосипеды на назначенных станциях. Гладстон может ходить или ездить на велосипеде между любыми двумя точками по прямой.

Гладстон обладает картой (прямоугольного) центра Дакбурга. Его текущее положение и точка встречи с Дейзи находятся на этой карте. Карта также содержит местоположения всех велосипедных станций в пределах границ.

В городе может быть больше велосипедных станций, которые не находятся в пределах границ карты. Учитывая его удачу, Вы можете предположить, что в тот момент, когда Гладстон сходит (или съезжает на велосипеде) с карты, он встречает велосипедную станцию, если она ему подходит. Велосипедные станции, не находящиеся на карте, могут быть расположены за пределами карты, они не обязательно должны лежать в целочисленных координатах.

Задача Гладстона выяснить, какой маршрут лучше взять. Вы можете помочь ему? Учитывая карту и его бесконечное количество удачи, какое самое быстрое время для его свидания с Дейзи?

Giriş verilənləri

Состоит из:

  • одна строка содержит два целых числа v[walk] и v[bike] (1v[walk] < v[bike]1 000) - скорость ходьбы и езды на велосипеде;

  • стрка из четырех целых чисел x[1], y[1], x[2] и y[2] (-10^6x[1] < x[2]10^6, -10^6y[1] < y[2]10^6) - граничные координаты карты центра Дакбурга;

  • строка из двух целых чисел x[G] и y[G] - местоположение Гладстона;

  • строка из двух целых чисел x[D] и y[D] - местоположение Дейзи;

  • строка с числом n (0n1000) - количество велостанций;

  • n строк, каждая с двумя целыми числами x[station] и y[station] - координатами имеющихся велостанций.

Все координаты заданы на карте центра, то есть x[1]xx[2] и y[1]yy[2].

Çıxış verilənləri

Выведите кратчайшее возможное время для Гладстона, чтобы добраться до Дейзи. Ваш ответ должен иметь абсолютную или относительную ошибку не более 10^(-6).

Nümunə

Giriş verilənləri #1
1 8
0 0 10 10
5 1
5 9
3
5 8
2 2
9 6
Çıxış verilənləri #1
3.000000000
Giriş verilənləri #2
5 100
0 -100000 100000 0
5 -30000
40000 -5
0
Çıxış verilənləri #2
501.9987496
Mənbə 2014 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача B