로봇 간 통신

21xx년, 인류는 은하 곳곳으로 퍼져 나가고 있다. 지난 세기 말 이후 새로운 거주 가능 행성을 찾기 위해 수천 대의 개척 우주선이 발사되었다.

트라이페너스호는 그중 하나로, 안드로메다 은하를 향해 가고 있다. 초공간에서 길고 긴 항행을 마친 승무원들은 아주 유망한 후보 행성을 찾았다. 다음 단계는 이 행성이 정말 새 거주민에게 적합한지 조사하는 것이다.

이를 위해 우주선은 무인 착륙선 여러 대를 싣고 있다. 선장 Juclean Dripac은 이들을 행성에 내려보내 데이터를 수집하기로 했다. 그러나 로봇은 낡았고 그리 똑똑하지 않아서, 운용자가 착륙 전에 행성에서의 동작을 미리 프로그래밍해야 한다. 이 계획을 세우기 위해 여러분을 포함한 많은 승무원이 소집되었다.

임무에서 가장 복잡한 단계는 로봇들이 독립적으로 수집한 데이터를 모아 통합하는 것이다. 로봇들은 임무 중 한 번, 데이터를 주고받을 수 있도록 전체 대 전체 통신 채널을 맺어야 한다. 모든 로봇이 미리 정해진 같은 순간에 통신 채널을 동시에 켜서, 그 정확한 순간에 서로 데이터를 한 번 주고받는다. 이 순간은 임무의 맨 처음일 수도, 맨 마지막일 수도, 그 사이 어느 때일 수도 있다. 이 시각은 여러분이 고르고, 운용자가 그에 맞춰 로봇을 프로그래밍한다.

로봇은 무선 채널로 통신하므로 거리가 연결을 제한하지는 않는다. 다만 두 로봇이 멀수록 통신에 더 많은 전력이 든다. 배터리 용량이 제한되어 있으니 송신 전력을 최대한 아껴야 한다.

다행히 로봇의 통신 장치에는 경로 설정 기능도 있어서, 로봇은 다른 로봇을 중계기로 삼아 간접적으로 통신할 수 있다. 로봇을 정점, 맺어진 통신 채널을 간선으로 하는 그래프를 생각하자. 이 그래프가 연결되어 있으면 전체 대 전체 통신이 가능하다.

여러분의 과제는 로봇들 사이의 전체 대 전체 통신에 필요한 최소 총 송신 전력을 계산하는 프로그램을 작성하는 것이다. 통신은 임무 중 특정한 순간에 단 한 번만 이루어지며, 그 순간은 미리 고를 수 있다. 각 로봇은 일정한 속도로 직선 운동을 한다. 두 로봇 사이에 필요한 송신 전력은 거리에 비례하므로, 비용은 통신 채널을 맺은 로봇 쌍마다 거리를 모두 더한 값과 정확히 같다. 행성 표면은 충분히 넓으므로 2차원 평면으로 봐도 된다. 데이터를 주고받는 데 걸리는 시간은 무시할 만하다.

입력에는 최대 200개의 데이터셋이 들어 있다. 각 데이터셋의 형식은 다음과 같다.

$N$ $T$

$x_1$ $y_1$ $vx_1$ $vy_1$

...

$x_N$ $y_N$ $vx_N$ $vy_N$

각 데이터셋의 첫 줄에는 정수 두 개가 주어진다. $N$은 로봇의 수($2 \le N \le 16$), $T$는 임무의 제한 시간($1 \le T < 1000$)이다. 이어지는 $N$개의 줄은 로봇 한 대의 운동을 나타낸다. $(x_i, y_i)$는 $i$번째 로봇의 초기 착륙 위치, $(vx_i, vy_i)$는 속도이다($|x_i|, |y_i| < 10^6$, $|vx_i|, |vy_i| < 1000$).

마지막 데이터셋 뒤에는 0 0이 한 줄에 주어진다. 이 줄은 데이터셋이 아니므로 처리하지 않는다. 모든 데이터셋의 $N$을 합하면 1700을 넘지 않는다.

각 데이터셋에 대해 전체 대 전체 통신에 필요한 최소 통신 비용을 한 줄에 출력한다. 소수점 아래 자릿수는 몇 자리로 출력해도 된다. 절대 오차는 $0.001$ 이하여야 한다.