prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem J: </font>Cubic Colonies</H1>3 4<p>5In AD 3456, the earth is too small for hundreds of billions of people to live in peace. Interstellar Colonization Project with Cubes (ICPC) is a project that tries to move people on the earth to space colonies to ameliorate the problem. ICPC obtained funding from governments and manufactured space colonies very quickly and at low cost using prefabricated cubic blocks.6</p>7 8<p>9The largest colony looks like a Rubik's cube. It consists of 3 &times; 3 &times; 3 cubic blocks (Figure J.1A). Smaller colonies miss some of the blocks in the largest colony.10</p>11 12<p>13When we manufacture a colony with multiple cubic blocks, we begin with a single block. Then we iteratively glue a next block to existing blocks in a way that faces of them match exactly. Every pair of touched faces is glued.14</p>15<center>16<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_cubicColonies1" style="aling:center"><br/>17<p>18Figure J.1: Example of the largest colony and a smaller colony19</p>20</center>21 22<p>23However, just before the first launch, we found a design flaw with the colonies. We need to add a cable to connect two points on the surface of each colony, but we cannot change the inside of the prefabricated blocks in a short time. Therefore we decided to attach a cable on the surface of each colony. If a part of the cable is not on the surface, it would be sheared off during the launch, so we have to put the whole cable on the surface. We would like to minimize the lengths of the cables due to budget constraints. The dashed line in Figure J.1B is such an example.24</p>25 26<p>27Write a program that, given the shape of a colony and a pair of points on its surface, calculates the length of the shortest possible cable for that colony.28</p>29 30 31<H2>Input</H2>32 33<p>34The input contains a series of datasets. Each dataset describes a single colony and the pair of the points for the colony in the following format.35</p>36 37<p>38<i>x</i><sub>1</sub> <i>y</i><sub>1</sub> <i>z</i><sub>1</sub> <i>x</i><sub>2</sub> <i>y</i><sub>2</sub> <i>z</i><sub>2</sub><br/>39<i>b</i><sub>0,0,0</sub><i>b</i><sub>1,0,0</sub><i>b</i><sub>2,0,0</sub><br/>40<i>b</i><sub>0,1,0</sub><i>b</i><sub>1,1,0</sub><i>b</i><sub>2,1,0</sub><br/>41<i>b</i><sub>0,2,0</sub><i>b</i><sub>1,2,0</sub><i>b</i><sub>2,2,0</sub><br/>42<i>b</i><sub>0,0,1</sub><i>b</i><sub>1,0,1</sub><i>b</i><sub>2,0,1</sub><br/>43<i>b</i><sub>0,1,1</sub><i>b</i><sub>1,1,1</sub><i>b</i><sub>2,1,1</sub><br/>44<i>b</i><sub>0,2,1</sub><i>b</i><sub>1,2,1</sub><i>b</i><sub>2,2,1</sub><br/>45<i>b</i><sub>0,0,2</sub><i>b</i><sub>1,0,2</sub><i>b</i><sub>2,0,2</sub><br/>46<i>b</i><sub>0,1,2</sub><i>b</i><sub>1,1,2</sub><i>b</i><sub>2,1,2</sub><br/>47<i>b</i><sub>0,2,2</sub><i>b</i><sub>1,2,2</sub><i>b</i><sub>2,2,2</sub><br/>48</p>49 50<p>51(<i>x</i><sub>1</sub>, <i>y</i><sub>1</sub>, <i>z</i><sub>1</sub>) and (<i>x</i><sub>2</sub>, <i>y</i><sub>2</sub>, <i>z</i><sub>2</sub>) are the two distinct points on the surface of the colony, where <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>y</i><sub>1</sub>, <i>y</i><sub>2</sub>, <i>z</i><sub>1</sub>, <i>z</i><sub>2</sub> are integers that satisfy 0 &le; <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>y</i><sub>1</sub>, <i>y</i><sub>2</sub>, <i>z</i><sub>1</sub>, <i>z</i><sub>2</sub> &le; 3. <i>b<sub>i,j,k</sub></i> is '<span>#</span>' when there is a cubic block whose two diagonal vertices are (<i>i</i>, <i>j</i>, <i>k</i>) and (<i>i</i> + 1, <i>j</i> + 1, <i>k</i> + 1), and <i>b<sub>i,j,k</sub></i> is '<span>.</span>' if there is no block. Figure J.1A corresponds to the first dataset in the sample input, whereas Figure J.1B corresponds to the second. A cable can pass through a zero-width gap between two blocks if they are touching only on their vertices or edges. In Figure J.2A, which is the third dataset in the sample input, the shortest cable goes from the point A (0, 0, 2) to the point B (2, 2, 2), passing through (1, 1, 2), which is shared by six blocks. Similarly, in Figure J.2B (the fourth dataset in the sample input), the shortest cable goes through the gap between two blocks not glued directly. When two blocks share only a single vertex, you can put a cable through the vertex (Figure J.2C; the fifth dataset in the sample input).52</p>53 54<p>55You can assume that there is no colony consisting of all 3 &times; 3 &times; 3 cubes but the center cube.56</p>57 58<p>59Six zeros terminate the input.60</p>61<center>62<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_cubicColonies2" style="aling:center"><br/>63<p>64Figure J.2: Dashed lines are the shortest cables. Some blocks are shown partially transparent65for illustration.66</p>67</center>68 69 70 71<H2>Output</H2>72 73<p>74For each dataset, output a line containing the length of the shortest cable that connects the two given points. We accept errors less than 0.0001. You can assume that given two points can be connected by a cable.75</p>76 77<H2>Sample Input</H2>78<pre>790 0 0 3 3 380###81###82###83###84###85###86###87###88###893 3 0 0 0 390#..91###92###93###94###95###96#.#97###98###990 0 2 2 2 2100...101...102...103.#.104#..105...106##.107##.108...1090 1 2 2 1 1110...111...112...113.#.114#..115...116##.117##.118...1193 2 0 2 3 2120###121..#122...123..#124...125.#.126..#127..#128.##1290 0 0 0 0 0130</pre>131 132<H2>Output for the Sample Input</H2>133<pre>1346.708203932499369415151356.478708664619074575341362.828427124746190290951372.236067977499789805051382.82842712474619029095139</pre>