All submissions for this problem are available.
There is an artificial intelligence program, that needs to be coded, which will act as a simulator for training of the sailor. Every calculation needs to be done in a two-dimensional plane. Let (x1, y1). . . (xn, yn) be a collection of n islands. You are a pilot of the ship and your goal is to navigate the ship from island (x1, y1) to island (xn, yn). The ship can travel a maximum distance of D units before it must refuel. We assume that a ship can only refuel from an island. From any island (xi, yi), the ship may travel to any other island (xj , yj) away at a speed of 1 unit per second. Before it does this, however, the ship 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 ship to travel from island (x1, y1) to (xn, yn). Assume that
the ship initially faces (xn, yn) and take all intermediate values like angles and distances as integer(hint: can use floor function)
The input will contain multiple test cases. Each test case will begin with a single line containing an integer D, the maximum distance between islands that the ship can travel (where 5≤ D ≤ 500),
and an integer n, the number of islands (where 2 ≤ n ≤ 25). The next n lines each contain 2 integer values; here, the ith line contains xi and yi (where 0 ≤ xi, yi ≤ 1000). Each of the island is guaranteed to be unique. The end-of-file is denoted by a test case with D = n = −1.
The output should contain a single line per test case indicating the shortest possible time in second
(rounded to the nearest integer) required for the ship to travel from (x1, y1) to (xn, yn). If no trip is
possible, print “impossible” instead.
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 Output: 7 71 impossible
|Time Limit:||20 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.