Hide

Problem I
Super Mario 169

Siggy is quite the video game enthusiast, and he’s been playing lots of Super Mario 169 lately (the highly obscure sequel to the more popular Super Mario 64). This game takes place entirely in an ocean, which can be modelled with a 3 dimensional coordinate system. The player’s objective is to swim around as the titular character, Mario, and collect all of the coins, of which there can be up to 169.

The coins are not simply in plain sight, however! Instead, there are up to 13 switches which Mario can press by touching them. Pressing any switch causes up to 13 coins to appear. Additionally, each switch can only be pressed once, and when it’s pressed, any other uncollected coins (which had been revealed by the previously-pressed switch, if any) disappear, meaning that Mario will be unable to collect them in the future. All switches and coins are small enough that they can be treated as points.

To make sure that he’s playing the game as optimally as possible, Siggy wants to know the minimum possible distance required to collect all of the coins.

Input

There will be a single test case in the input. This test case will begin with a single line with four integers:

     n mx my mz

where $n$ ($1 \le n \le 13$) is the number of switches, and the 3D point $(m_ x,m_ y,m_ z)$ is Mario’s starting point.

The following pattern is then repeated $n$ times, once for each switch. The pattern begins with a single line with four integers:

     k sx sy sz

where $k$ ($1 \le k \le 13$) is the number of coins activated by this switch, and the 3D point $(s_ x,s_ y,s_ z)$ is the point where the switch is found. Following this there will be $k$ lines with three integers:

     cx cy cz

where $(c_ x,c_ y,c_ z)$ is the 3D point of one of the coins activated by this switch. All coordinates $x$, $y$, $z$ of all points will be in the range $-1\, 000 \le x,y,z \le 1\, 000$, and all points in a test case, whether Mario’s starting point, switch or coin, will be unique.

Output

Output a single number equal to the minimum distance for Mario to travel in order to collect all of the coins. Your result should have an absolute or relative error of less than $10^{-3}$.

Sample Input 1 Sample Output 1
2 5 5 0
4 6 0 0
7 0 0
-11 -1 0
-11 1 0
-10 0 0
2 5 0 0
0 0 0
0 5 0
44.224463

Please log in to submit a solution to this problem

Log in