acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem H

Ninja Escape

I've just completed a mission inside ICPC Castle in the enemy country, and am leaving the castle through the underground escape route dug in advance. However, there are n watchtowers placed at equal intervals in the castle, and I must reach the entrance of the escape route without being noticed by the guards in the watchtowers.

The yard of the castle has a rectangular shape of 100n × 100. Let the coordinates of the back left corner be (0, 0) and the coordinates of the front right corner be (100n, 100). The watchtowers are numbered from 1 to n, and the k-th watchtower is located at the coordinates (100k − 50, 50).

I am currently at the coordinates (x1, y1), and I want to move to the coordinates (x2, y2), where the entrance of the escape route is located, in the shortest possible time.

Should I move too fast near a watchtower, the guards might notice the footsteps. Strictly saying, I must not move faster than D2 per second, where D is the distance to the nearest watchtower.

I'm wondering how long it takes to reach the entrance of the escape route.

For example, when there is one watchtower and the coordinates of the starting location (current location) and the goal location (the entrance of the escape route) are (5, 6) and (78, 90), respectively, the optimal route is as shown in Figure H-1. For another example, when there are two watchtowers and the coordinates of the starting location and the goal location are (85, 70) and (115, 30), respectively, the optimal route is as shown in Figure H-2. These are corresponding to the first two datasets in the Sample Input.

Figure H-1: The optimal route for the first dataset
Figure H-2: The optimal route for the second dataset

Input

The input consists of multiple datasets, each in the following format.

n x1 y1 x2 y2

n is the number of watchtowers. n is a positive integer not exceeding 107. (x1, y1) gives the coordinates of the starting location, and (x2, y2) gives the coordinates of the goal location. x1 and x2 are integers between 0 and 100n, inclusive. y1 and y2 are integers between 0 and 100, inclusive. The coordinates of the starting and goal locations are different. The coordinates of the starting and goal locations are also different from those of any watchtowers.

The end of the input is indicated by a line containing five zeros. The number of datasets in the input is at most 1000.

Output

For each dataset, output the shortest possible time to move in seconds. The error contained in the output should not exceed 10−8. The output shall be deemed correct if its relative error or its absolute error is within this limit.

Sample Input

1 5 6 78 90
2 85 70 115 30
1 2 50 98 50
1 12 23 34 45
1 23 45 67 89
2 80 50 195 50
2 80 50 180 70
2 10 50 190 60
10 1 2 987 65
10 80 60 920 40
10 50 90 950 10
0 0 0 0 0

Output for the Sample Input

0.056924948365
0.024806946918
0.060137708723
0.039815727511
0.054616382922
0.070423053859
0.063218824369
0.091771006495
0.338081602957
0.297714980979
0.316557291903
(End of Problem H) A B C D E F G H