
Robot 
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB 
Total submit users: 3, Accepted users: 1 
Problem 10049 :
No special judgement

Problem description 
Let (x1,y1),...,(xn,yn) be a collection of n points in a twodimensional plane. Your goal is to navigate a
robot from point (x1,y1) to point (xn,yn). From any point (xi,yi), the robot may travel to any other point
(xj,yj) at most R units away at a speed of 1 unit per second. Before it does this, however, the robot must
turn until it faces (xj,yj); this turning occurs at a rate of 1 degree per second.
Compute the shortest time needed for the robot to travel from point (x1,y1) to (xn,yn). Assume that
the robot initially faces (xn,yn). To prevent floatingpoint precision issues, you should use the double data
type instead of float. It is guaranteed that the unrounded shortest time will be no more than 0.4 away
from the closest integer. Also, if you decide to use inverse trigonometric functions in your solution (hint,
hint!), try atan2() rather than acos() or asin().

Input 
The input test file will contain multiple test cases. Each test case will begin with a single line containing an
integer R, the maximum distance between points that the robot is allowed to travel (where 10 ¡Ü R ¡Ü 1000),
and an integer n, the number of points (where 2 ¡Ü n ¡Ü 20). The next n lines each contain 2 integer values;
here, the ith line contains xi and yi (where 1000 ¡Ü xi,yi ¡Ü 1000). Each of the points is guaranteed to be
unique. The endoffile is denoted by a test case with R = n = 1.

Output 
The output test file should contain a single line per test case indicating the shortest possible time in second
(rounded to the nearest integer) required for the robot to travel from (x1,y1) to (xn,yn). If no trip is
possible, print ¡°impossible¡± instead.

Sample Input 
10 2
0 0
7 0
10 3
0 0
7 0
14 5
10 3
0 0
7 0
14 10
1 1 
Sample Output 
7
71
impossible 
Problem Source 
Stanford Local 2006

Submit
Discuss
Judge Status
Problems
Ranklist

