2004 Canadian Computing Competition, Stage 2
Day 2, Problem 1: Return of Space Turtle
Remember Space Turtle, our fearless space adventurer? Last we encountered him, he was searching for the fabled Golden Shell in the Tortoise, his trusty spaceship.
Space Turtle has run out of fuel, but he thinks that he is very close to the Golden Shell. Unfortunately, due to a spatial anomaly (the sort you see on TV), both the Tortoise and the Golden Shell are trapped on a two-dimensional grid, travelling around and around in very strange orbits.
These orbits always travel from lattice (integer co-ordinate) points on the grid to adjacent lattice points, and it takes exactly one minute to travel one unit of distance
on the lattice. Both the Tortoise and the Golden Shell entered the anomaly at the same time, so you can really think of this as two things travelling around on a grid. You can imagine that as the Tortoise and the Golden Shell are travelling in their respective orbits, the distance between them varies quite a bit. As the lonely keeper of the fabled Golden Shell, you have the task of observing the Tortoise once each minute (exactly when both you and the Tortoise are on lattice points) and recording how far away the Tortoise is.
In particular, you want to determine the closest distance Space Turtle will ever be observed from the Golden Shell. (He might be closer when you're not looking, but that doesn't count.)
Input
The first line consists of two integers sx, and sy, which give the coordinates of Space Turtle's starting point in the anomaly, and a third integer, sm.
Then, the orbit is described as a sequence of sm moves, each on a separate line. Each move consists of an integer, d, -100 ≤ d ≤ 100 and a letter c, separated by a space. The integer indicates the distance in light-years that the Tortoise moves, and the letter indicates the direction, either 'X' or 'Y', corresponding to the X and Y directions on the grid. There will be no more than 100 such lines.
After this description, is an analogous description for the orbit of the Golden Shell: tx, and ty for the starting point, and tm on the first line, and then tm lines describing the orbit in the same manner as the first orbit. Both orbits are guaranteed to end at the starting location (so that they are cycles).
Output
Output the closest distance that you will ever observe between Space Turtle and the Golden Shell, to 2 decimal places. If you and Space Turtle collide on a lattice point at some point, report 0.00.
Sample Input
0 0 4 -1 Y -1 X 1 Y 1 X 1 0 4 -1 X 1 Y 1 X -1 Y
Sample Output
1.00
All Submissions
Best Solutions
Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 27, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)