Time limit per test: 0.75
second(s)

Memory limit: 262144 kilobytes

Memory limit: 262144 kilobytes

input: standard

output: standard

output: standard

It is the year of 2xxx. Human beings have migrated out of the Earth and resided in space colonies. Because of the severe environment of the space, which comes from cosmic rays and meteorites, those colonies have to be continuously repaired by maintenance robots. In this problem, you are requested to write a program that calculates the shortest distance for a robot to move from the present point to the next repair point on a colony. Each colony can be modeled as a polycube, that is, one or more cubes of the same size all joined by their faces. Note that, as forming a polycube, all cubes of each colony are connected. This implies every cube has at least one face coincident with a face of another cube, except for colonies with a single cube. The figure below illustrates a couple of example colonies.

The maintenance robot can move only on the surface of the polycubes, that is, on faces not in common with other cubes. In addition, due to the structure of the colonies, move of the robot beyond a face is restricted to the following cases: (a) the robot is moving between adjacent faces of the same cube; (b) the robot is moving between adjacent faces of adjacent cubes; and (c) the robot is moving along the inner side of an L-shape, namely, the robot is moving between adjacent faces of two cubes that have the common adjacent cube. Here, adjacent faces denote those with the common edge, and adjacent cubes denote those with the common face.

For the purpose of this problem, we consider an

nx_{1}y_{1}z_{1}...x_{n}y_{n}z_{n}sxsyszdxdydz

sample input |
sample output |

1 0 0 0 0 0 50 30 40 50 |
50.0 |

sample input |
sample output |

1 0 0 0 50 0 0 0 50 0 |
100.0 |

sample input |
sample output |

2 0 0 0 100 0 0 0 0 50 100 0 50 |
100.0 |

sample input |
sample output |

3 0 0 0 100 0 0 0 100 0 100 50 0 50 100 0 |
100.0 |

sample input |
sample output |

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 |

sample input |
sample output |

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 |
141.4213562373 |

sample input |
sample output |

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 |
316.2277660168 |

sample input |
sample output |

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 |
341.4213562373 |

sample input |
sample output |

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 |
341.4213562373 |

Online Contester Team © 2002 - 2010. All rights reserved. |