Colony Maintenance

Time limit8sMemory limit512 MB

Summary

Given up to 16 unit cubes forming a connected polycube, find the shortest path over its exposed surface between two points, with moves constrained by the three surface-adjacency cases.

Level: Hard8 of 10
Topics: Graph, BFS, Geometry, Implementation
Solved: No attempts yet

Problem

The year is 2xxx. People have left Earth and live in space colonies. Cosmic rays and meteorites damage the colonies without pause, so maintenance robots repair them constantly. Write a program that computes the shortest distance a robot travels on a colony from its present point to the next repair point.

A colony is a polycube, that is, one or more cubes of the same size joined by their faces. All cubes of a colony are connected, so every cube shares at least one face with another cube, except in a colony made of a single cube. The figure below shows two example colonies.

Figure 2: Example colonies

The robot moves only on the surface of the polycube, that is, on the faces that are not shared with another cube. The structure of a colony restricts a move across the boundary of a face to these three cases.

(a) The robot moves between adjacent faces of the same cube. (b) The robot moves between adjacent faces of adjacent cubes. (c) The robot moves along the inner side of an L shape, that is, between adjacent faces of two cubes that have a common adjacent cube.

Here, adjacent faces are two faces that share an edge, and adjacent cubes are two cubes that share a face.

Figure 3: Possible moves

All cubes are placed in xyz space with every edge parallel to the x-axis, the y-axis, or the z-axis. The edge length of a cube is 100.

Input

The input is a sequence of datasets. Each dataset has the following format.

n
x1 y1 z1
...
xn yn zn
sx sy sz dx dy dz

$n$ is the number of cubes of a colony ( $1 \le n \le 16$ ). $(x_i, y_i, z_i)$ is the center of the $i$ -th cube, and every coordinate value is a multiple of 100, the edge length of a cube. $(s_x, s_y, s_z)$ is the present point of the robot and $(d_x, d_y, d_z)$ is the next repair point. The two points are always different, and neither of them lies on an edge of a cube. All coordinate values are integers between $-2000$ and $2000$ inclusive.

The end of the input is a line with a single zero. That line is not a dataset, so do not process it.

Output

For each dataset, print on one line the length of the shortest route from the present point to the next repair point. Print the value rounded to six digits after the decimal point.

Hint

The figure below shows how the robot moves in the sixth dataset of the sample input.

Figure 4: The robot's move in the 6th dataset

Examples1

Example 1

Input

1
0 0 0
0 0 50 30 40 50
1
0 0 0
50 0 0 0 50 0
2
0 0 0
100 0 0
0 0 50 100 0 50
3
0 0 0
100 0 0
0 100 0
100 50 0 50 100 0
7
0 0 0
100 0 0
-100 0 0
0 100 0
0 -100 0
0 0 100
0 0 -100
150 0 0 -150 0 0
6
0 0 0
100 0 0
0 100 0
100 100 0
0 0 100
100 100 100
100 0 50 0 100 50
6
0 0 0
100 0 0
0 100 0
100 100 0
0 0 100
100 100 100
100 100 150 0 0 150
6
0 0 0
100 0 0
0 100 0
100 100 100
100 0 100
0 100 100
0 0 50 100 100 50
8
0 0 0
-100 0 0
-100 100 0
-100 200 0
0 200 0
100 200 0
100 200 100
100 100 100
0 0 50 100 100 50
0

Expected output