编程介的小学生
2017-08-06 03:05Robot
Description
Let (x1, y1), …, (xn, yn) be a collection of n points in a two-dimensional 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 floating-point 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 end-of-file 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
- 点赞
- 回答
- 收藏
- 复制链接分享
2条回答
为你推荐
- robotframework,运行ride如何解决,求助
- python
- 2个回答
- java Robot 如何在方法内重用robot对象
- java
- eclipse
- 2个回答
- 如何在具有多个域的godaddy共享服务器中创建robot.txt
- robots.txt
- html
- php
- 2个回答
- ·Robotframework」运行ride.py 报错 麻烦大神们看一下!
- python
- ubuntu
- 2个回答
- 运动规划的伪代码程序看不懂程序的逻辑
- 运动规划
- 路径规划
- 算法
- 伪代码
- 1个回答