Biking Duck

Picture by D J Shin via Wikimedia Commons, cc by-sa
Gladstone Gander is walking through Duckburg and needs to get to his date with Daisy Duck as soon as possible. If he doesn’t get there in time, Donald might show up and take his place instead.

Duckburg has recently started providing a very eco-friendly way of public transport: bikes. At many bike stations throughout the city, one can pick up a free bike, ride it to another bike station, and drop it there. This gives Gladstone two ways of transportion: on foot or by bike. Biking is faster, of course, but he must pick up and leave the bikes at the designated stations. Gladstone can walk or bike between any two points in a straight line.

Gladstone possesses a map of the (rectangular) center of Duckburg. His current position is on this map and so is the meeting point with Daisy. The map also contains the locations of all bike stations within the boundaries of the map.

There can be way more bike stations though, that are not within the boundaries of the map. Considering his luck, you can assume that the moment Gladstone walks (or bikes) off the map, he encounters a bike station if that suits him well. The bike stations not on the map can be located anywhere outside the map, they do not have to lie on integer coordinates.

That leaves Gladstone with the task of figuring out which route to take. Can you help him out? Given the map and his infinite amount of luck, what is the fastest time to his date with Daisy?


The input consists of:

  • one line with two integers $v_{\text {walk}}$ and $v_{\text {bike}}$ ($1\le v_{\text {walk}}< v_{\text {bike}} \le 1\, 000$), the speeds of walking and of biking;

  • one line with four integers $x_1, y_1, x_2$ and $y_2$ ($-10^6\le x_1< x_2\le 10^6$; $-10^6\le y_1< y_2\le 10^6$), the bounding coordinates of the map of the center of Duckburg;

  • one line with two integers $x_{\text {G}}$ and $y_{\text {G}}$, Gladstone’s position;

  • one line with two integers $x_{\text {D}}$ and $y_{\text {D}}$, Daisy’s position;

  • one line with one integer $n$ ($0\le n\le 1\, 000$), the number of known bike stations;

  • $n$ lines with two integers $x_{\text {station}}$ and $y_{\text {station}}$ each, the coordinates of the known bike stations.

All coordinates are on the map of the center, i.e., $x_1\le x\le x_2$ and $y_1\le y\le y_2$.


Output one line with the shortest possible time for Gladstone to get to Daisy. Your answer should have an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
1 8
0 0 10 10
5 1
5 9
5 8
2 2
9 6
Sample Input 2 Sample Output 2
5 100
0 -100000 100000 0
5 -30000
40000 -5
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in