Zamburguesas P88760


Statement
 

pdf   zip

html

The Lake of the Dragon God is one of the most mythical challenges of the contest. A river must be crossed by jumping from rock to rock, but be careful! Some rocks are fake and sink!

[r]

There are n true rocks, all round, with centre (xi, yi) and radius ri. The maximum distance that a contestant can jump is d (measuring it from the border of the rocks). Your task is to compute the minimum number of jumps to go from the first rock to the last one without falling into the water. If it is impossible, state so.

Input

Input consists of several cases. Each case starts with the number of rocks n ≥ 2 and the jump distance d > 0. Follow n triples of real numbers xi, yi and ri, describing each rock.

Output

For each case of the input, print in a line the minimum number of jumps to go from the first of the given rocks to the last one, by making jumps non larger than d, or “Xof!” if it is impossible.

Observations

  • The test cases will never contain overlapped rocks, nor any exact jump that could cause an error because of precision issues.
  • The picture shows the rocks of the sample test cases.
Public test cases
  • Input

    4 3
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    4 8.3
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    4 1
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    

    Output

    2
    1
    Xof!
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C C++ Go Java