Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Robot
Description Let ( y) be a collection of n points in a two-dimensional plane. Your goal is to navigate a robot from point (_{n}x_{1}, y_{1}) to point (x, _{n}y). From any point (_{n}x, _{i}y), the robot may travel to any other point (_{i}x, _{j}y) at most _{j}R units away at a speed of 1 unit per second. Before it does this, however, the robot must turn until it faces (x, _{j}y); this turning occurs at a rate of 1 degree per second._{j}Compute the shortest time needed for the robot to travel from point ( y). Assume that the robot initially faces (_{n}x, _{n}y). To prevent floating-point precision issues, you should use the _{n}`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 y (where −1000 ≤ _{i}x, _{i}y ≤ 1000). Each of the points is guaranteed to be unique. The end-of-file is denoted by a test case with _{i}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 ( y). If no trip is possible, print “impossible” instead._{n}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 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator