CCC '04 S4 - Space Turtle

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2004 Stage 1, Senior #4

Space Turtle is a fearless space adventurer. His spaceship, the Tortoise, is a little outdated, but still gets him where he needs to go.

The Tortoise can do only two things – move forward an integer number of light-years, and turn in one of four directions (relative to the current orientation): right, left, up and down. In fact, strangely enough, we can even think of the Tortoise as a ship which travels along a 3-dimensional co-ordinate grid, measured in light-years.

In today’s adventure, Space Turtle is searching for the fabled Golden Shell, which lies on a deserted planet somewhere in uncharted space. Space Turtle plans to fly around randomly looking for the planet, hoping that his turtle instincts will lead him to the treasure.

You have the lonely job of being the keeper of the fabled Golden Shell. Being lonely, your only hobby is to observe and record how close various treasure seekers come to finding the deserted planet and its hidden treasure. Given your observations of Space Turtle’s movements, determine the closest distance Space Turtle comes to reaching the Golden Shell.

Input Specification

The first line consists of three integers sx, sy, and sz, which give the coordinates of SpaceTurtle’s starting point. Space Turtle is originally oriented in the positive x direction, with the top of his spaceship pointing in the positive z direction, and with the positive y direction to his left. Each of these integers are between -100 and 100. The second line consists of three integers tx, ty, and tz, which give the coordinates of the deserted planet. Each of these integers are between -10\,000 and 10\,000. The rest of the lines describe Space Turtle’s flight plan in his search for the Golden Shell. Each line consists of an integer, d, 0 \le d \le 100, and a letter c, separated by a space. The integer indicates the distance in light-years that the Tortoise moves forward, and the letter indicates the direction the ship turns after having moved forward. L, R, U, and D stand for left, right, up and down, respectively. There will be no more than 100 such lines.

On the last line of input, instead of one of the four direction letters, the letter E is given instead, indicating the end of today’s adventure.

Output Specification

Output the closest distance that Space Turtle gets to the hidden planet, rounded to 2 decimal places. If Space Turtle’s coordinates coincide with the planet’s coordinates during his flight indicate that with a distance of 0.00. He safely lands on the planet and finds the Golden Shell.

Sample Input

0 0 0
1 1 1
2 L
2 L
2 U
2 U
2 L
2 L
2 U
2 E

Sample Output

1.41

Comments


  • 0
    Evan091  commented on Aug. 11, 2019, 10:56 p.m.

    is the answer should be sqrt(3), 1.72, instead of 1.41?


    • -1
      tzak_el  commented on Aug. 12, 2019, 5:04 a.m.

      No, your answer should take into consideration the minimum distance at any point in time, which includes when you are traveling (and not turning at a fixed grid point).


  • 2
    4fecta  commented on June 22, 2019, 10:46 a.m.

    Does the question also require computation of minimum distance while travelling? I.E, does the program have to calculate the distance between a line and a point or just point to point distances?


    • 2
      discoverMe  commented on June 22, 2019, 10:49 a.m. edit 2

      yes it is the closest he gets at any time including while traveling