Box
---

Figuring out the shortest path on a box may seem trivial at first.
All we need to do is find the unfolding of the box that brings
the destination point closest.
If the final point is on one of the three faces touching the origin,
the shortest path is always a straight line directly to the destination;
if it's on one of the other three faces, it may seem obvious that we can
start on a face adjacent to the final face, and then just go around a
single corner.  It may seem obvious, that is, but it is wrong.

Consider a box that has a width of 100 units, and a height and depth
of 4 units, and let's say our destination is (100,3,3).  If we
use the face perpendicular to the depth and adjacent with the origin,
and then the destination face, we must traverse 103 units horizontally
and 3 units vertically for a total distance of 103 and some change:

   |--------~...~------------|----|
   |                         |   *|
   |                         |    |
   |                         |    |
   *--------~...~------------|----|

If on the other hand we use both the face perpendicular to the
depth and the one on top of that we can cut this down to 101
units horizontally and 7 units vertically for a total distance
of only 101 and some change:

   |--------~...~------------|----|
   |                         |*   |
   |                         |    |
   |                         |    |
   |--------~...~------------|----|
   |                         |
   |                         |
   |                         |
   *--------~...~------------|

So sometimes we will need to traverse three faces to get to
our final point the quickest way.  Do we ever need to traverse
four or more faces?  In this problem, probably not, but it
turns out we don't need to know that; we can easily enumerate
all single, two-face, three-face, four-face, and even more
using recursion.

Indeed, manually enumerating and coding all the cases is
terribly error-prone and very difficult to test; a single sign
error or coordinate swap can doom your submission.  So writing
the general case is much safer.

We'll start with a routine that enumerates the unfoldings
starting with a single face.  If the final destination is on
that face, the shortest path is always directly to that
point (every subpath of the final shortest path is itself a
straight line on the unfolded box).  Otherwise, we need to
traverse either over the right edge, or over the top edge,
to the next face.  As we cross each edge, we need to
accumulate how much horizontal and vertical distance we have
covered.

long best = Integer.MAX_VALUE ;
long sqadd(int x, int y) {
   return x * (long)x + y * (long)y ;
}
void rec(
   int x, int y,        // the distance we've traversed so far
   int w, int h, int d, // the width and height of the current face, and
                        // depth of the box in this orientation
   int dx, int dy, int dz, // the position of the destination
   int togo) {          // how many additional faces we allow ourselves
   if (dz == 0) { // the destination is on this face
      best = Math.min(best, sqadd(x+dx, y+dy)) ;
      return ;
   }
   if (togo == 0) return ; // no more faces allowed
   // now we consider going to the right edge; this rotates the box and point
   rec(x + w, y, d, h, w, dz, dy, w-dx, togo-1) ;
   // now we consider going to the top edge; this rotates the box and point
   rec(x, y + h, w, d, h, dx, dz, h-dy, togo-1) ;
}

Finally, in the main routine, we need to consider all three
possible starting faces.  We don't know how many faces a best path
might be, so we be generous and say 6.  This is only a maximum of
2^6 * 3 cases, so it runs very fast.

for (each case) {
   best = Integer.MAX_VALUE ;
   rec(0, 0, w, h, d, x, y, z, 6) ;
   rec(0, 0, h, d, w, y, z, x, 6) ;
   rec(0, 0, d, w, h, z, x, y, 6) ;
}

There's one other concern we may have.  We are considering all
unfoldings, even the unfoldings for which the straight line from
the origin to the (unfolded) destination goes off the actual
unfolded box.  In such a case, the path will always be longer
than the final best result, so considering it doesn't hurt
anything.  Essentially, all the space outside the unfolding
represents the edges of the box "opened up" or "stretched";
by opening those edges that way, you can only increase the
overall path length.  Consider the picture below:

         |----|
         |*   |
         /    |
        /|    |
   |---/-|----|
   |  /  |    |
   | /   |    |
   |/    |    |
   *-----|----|

Our straight line leaves the leftmost rectangle and reenters
the topmost rectangle.  But the two edges so represented
are actually joined in the real box, so a different unfolding
for which that line does not leave the unfolding always will
have a shorter distance:

   |-----|
   |     |
   |     |
   |*    |
   |-----|
   |     |
   |     |
   |     |
   *-----|

But if you were worried about this not being the case, it is
straightforward to extend the recursion to maintain a minimum
and maximum slope (represented by rationals) permitted by this
straight-line traversals, and thus eliminate all unfoldings for
which a straight line would leave the boundaries.