Simulator

Problem code: CRAFT04

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).

Input

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.

Output

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.

Example

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

Author: aman871988
Date Added: 4-03-2010
Time Limit: 20 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

Hint: The problem is based on

amanatadmin @ 12 Mar 2010 05:05 PM

Hint: The problem is based on Dijkstra algorithm

what is the initial

dejavu @ 12 Mar 2010 05:45 PM

what is the initial orientation of the plane ( are we supposed to consider any penalty of rotation for the first hop??)

is the second answer 71 or 51 ?

when i m submitting the

khyatigupta @ 12 Mar 2010 10:56 PM

when i m submitting the answer , an error is cmng out i.e "contest_id_field is required"

wat to do??

@Ankit Malpani: It is clearly

amanatadmin @ 12 Mar 2010 11:10 PM

@Ankit Malpani: It is clearly mentioned in the question. So read it carefully

hey no body is solving this

amanatadmin @ 12 Mar 2010 11:14 PM

hey no body is solving this problem.

If any one has any doubt i am here to help

:)

i have solved it and i m

khyatigupta @ 12 Mar 2010 11:26 PM

i have solved it and i m getting correct answer for the sample input given also

bt its sayng wrong answer, i hv also checked my code for many more inputs

ohh... sry :)

dejavu @ 12 Mar 2010 11:51 PM

ohh... sry :)

@Aman can u test i/o with ur

vish @ 13 Mar 2010 09:05 AM

@Aman

can u test i/o with ur solution.......

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions