// CCC 2004
// Problem S4 Space Turtle
//
// This algoritm is due to Richard Peng.
//
// The idea is: given the position of a space turtle and a
// golden shell, determine the closest the turtle comes to the shell.
// (The turtle moves forward than turns left, right up and down.)
//
// Peng's insight is to ALWAYS think of the turtle at 0,0,0.
// This puts the shell at x,y,z.
//
// As an example lets think only in 2d: assume the shell is at (5,2)
// moving forward 2 is the same as moving the shell to (3,2)
// that is, each movement is: x = x - d
//
// Now here's Peng's second great insight: the closest the turtle comes
// to the shell will be at the ends points of the movement, OR if he zooms by
// so to speak, its at x = 0. EG: if the shell is at (5,2) and the turtle moves 8
// and the new shell location is (-3,2) the closest the turtle was, was
// 2. At one point the shell was at (0,2)
// in 3D terms if the new x and x are different signs, the closest distance
// is sqrt(y^2 + z^2) versus the normal sqrt(x^2+ y^2 + z^2)
//
// Turning is a bit of a mind bending exercise, but again not so bad
// if you imagine it in only 2D: if the shell is at (5,2) and
// the turtle turns left the shell will be at (2,-5)
// that is (x,y,z) becomes (y,-x,z) (z is unaffected by a left or right turn)
// DRAW a grid, plot the point, and you'll see!
// similarly right means (x,y,z) becomes (-y,x,z)
// down means (x,y,z) becomes (-z,y,x) (y is unaffected by down/up)
// and up means (x,y,z) becomes (z,y,-x)
import hsa.*;
public class S4SpaceTurtlePeng
{
static Console c;
static double tx, ty, tz;
static double sx, sy, sz;
static double x, y, z, newX, t;
public static void main (String[] args)
{
c = new Console ();
double closest, distance, d;
char turn;
String file;
c.print ("file name: ");
file = c.readString ();
TextInputFile fi = new TextInputFile (file);
tx = fi.readDouble (); // turtle coordinates
ty = fi.readDouble ();
tz = fi.readDouble ();
sx = fi.readDouble (); // shell coordinates
sy = fi.readDouble ();
sz = fi.readDouble ();
x = sx - tx;
y = sy - ty;
z = sz - tz;
closest = x * x + y * y + z * z;
do
{
distance = fi.readDouble ();
turn = fi.readChar ();
newX = x - distance;
if (newX * x < 0)
closest = Math.min (closest, y * y + z * z);
else
closest = Math.min (closest, newX * newX + y * y + z * z);
x = newX;
t = x;
if (turn == 'L')
{
x = y;
y = -t;
}
else if (turn == 'R')
{
x = -y;
y = t;
}
else if (turn == 'U')
{
x = z;
z = -t;
}
else
{
x = -z;
z = t;
}
}
while (turn != 'E');
c.println ((int) ((Math.sqrt (closest) * 100) + 0.5) / 100.0);
}
}