题目描述

公元 2xxx 年，人类已经迁离地球，居住在太空殖民地中。由于宇宙射线和陨石等恶劣环境，殖民地需要由维护机器人不断进行修复。现在需要计算机器人从当前位置移动到下一个维修点时，沿殖民地表面能够走出的最短距离。

每个殖民地可以看成一个 polycube（多立方体）：由一个或多个边长相同的立方体组成，任意两个相邻立方体通过完整的面连接，并且所有立方体整体连通。除仅含一个立方体的情况外，每个立方体至少有一个面与另一个立方体的面重合。

机器人只能在多立方体的外表面移动，即只能经过那些没有与其他立方体重合的面。

由于殖民地的结构限制，机器人跨越一个面的边界时，只允许出现以下三种情况：

1. 在同一个立方体的两个相邻表面之间移动；
2. 在两个相邻立方体的相邻表面之间移动；
3. 沿一个 L 形凹角的内侧移动：也就是说，在两个立方体的相邻表面之间移动，并且这两个立方体还拥有一个共同的相邻立方体。

这里，“相邻面”指两个面拥有一条公共边，“相邻立方体”指两个立方体拥有一个公共面。

建立三维直角坐标系，所有立方体的边都平行于 $x$、$y$ 或 $z$ 轴。每个立方体的边长均为 $100$。

给定组成殖民地的所有立方体中心，以及机器人当前所在的表面点 $S$ 和目标维修点 $D$，求机器人沿允许的殖民地表面移动时，从 $S$ 到 $D$ 的最短距离。

输入格式

第一行一个整数 $n$，表示殖民地中立方体的数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,z_i$，表示第 $i$ 个立方体中心的坐标。

最后一行包含六个整数：

sx sy sz dx dy dz

其中 $(sx,sy,sz)$ 为机器人的当前位置 $S$，$(dx,dy,dz)$ 为目标维修点 $D$。

保证：

• $1\le n\le16$；
• 每个立方体中心坐标都是 $100$ 的整数倍；
• 所有立方体构成一个连通的 polycube；
• $S$ 和 $D$ 都位于殖民地外表面上；
• $S\ne D$；
• $S,D$ 均不位于任何立方体的棱上；
• 输入中的所有坐标均为整数，且位于 $[-2000,2000]$ 内。

输出格式

输出一个实数，表示机器人从 $S$ 到 $D$ 的最短表面路径长度。

答案允许存在浮点误差，但要求绝对误差不超过 $10^{-8}$。

样例 1

1
0 0 0
0 0 50 30 40 50

50.0

样例 2

1
0 0 0
50 0 0 0 50 0

100.0

样例 3

2
0 0 0
100 0 0
0 0 50 100 0 50

100.0

样例 4

3
0 0 0
100 0 0
0 100 0
100 50 0 50 100 0

100.0

样例 5

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

416.2277660168