로봇 통신

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

프레시테너호도 그중 하나로, 안드로메다 은하를 향해 항해하고 있다. 초공간에서의 길고 긴 항해 끝에 승무원들은 마침내 가능성이 높은 후보 행성을 발견했다. 다음으로 할 일은 그 행성이 정말로 새 거주지로 적합한지 조사하는 것이다.

이를 위해 우주선은 무인 착륙선 여러 대를 싣고 있다. 선장 Juclean Dripac은 착륙선을 행성에 내려보내 데이터를 수집하기로 결정했다. 하지만 안타깝게도 이 로봇들은 조금 낡았고 그리 똑똑하지 않아서, 조작자가 착륙 전에 행성에서 무엇을 할지 미리 프로그램해야 한다. 당신을 포함한 많은 인원이 이 중요한 계획을 세우기 위해 소집되었다.

임무에서 가장 복잡한 단계는 여러 로봇이 각자 수집한 데이터를 모두 모아 통합하는 것이다. 로봇들은 임무 중 한 번, 서로 데이터를 교환하기 위해 모든 로봇 사이에 통신 채널을 개설해야 한다. 즉, 모든 로봇이 정해진 시각에 동시에 통신 채널을 활성화하고 그 시각에 서로 데이터를 교환한다.

로봇들은 무선 채널로 통신하므로 로봇 사이의 거리가 연결 가능성을 제한하지 않는다. 하지만 두 로봇이 멀어질수록 통신에 더 많은 전력을 사용해야 한다. 배터리 용량의 한계 때문에 전송 전력을 최대한 아끼고 싶다.

다행히도 로봇의 통신 장치는 라우팅 기능도 갖추고 있어서, 각 로봇은 가장 가까운 로봇과만 대화하면 된다. 로봇을 정점으로, 로봇 사이에 개설된 통신 채널을 간선으로 하는 그래프를 생각하자. 이 그래프가 연결되어 있으면 모든 로봇 사이의 통신이 가능하다.

당신의 임무는 로봇들 사이의 모든 로봇 통신에 필요한 최소 총 전송 전력을 계산하는 프로그램을 작성하는 것이다. 각 로봇은 행성 표면에서 직선으로 움직인다. 서로 통신하는 로봇 쌍마다 채널 하나를 차지하지만, 채널은 충분히 많이 있다고 가정해도 된다. 두 로봇에 필요한 전송 전력은 두 로봇 사이의 거리에 비례하므로, 여기서의 비용은 통신 채널을 개설한 로봇 쌍마다의 거리의 합과 정확히 같다.

행성 표면은 충분히 크므로 2차원 평면으로 간주해도 된다. 로봇들이 데이터를 주고받는 데 걸리는 시간도 무시할 수 있다.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋의 형식은 아래와 같다.

N T
x1 y1 vx1 vy1
...
xN yN vxN vyN

각 데이터셋의 첫 줄에는 두 정수 N과 T가 주어진다. N은 데이터 수집에 사용되는 로봇의 수이고 (2 ≤ N ≤ 16), T는 임무의 시간 제한이다 (1 ≤ T < 1000).

다음 N개 줄은 각각 로봇의 움직임을 나타낸다. (xi, yi)와 (vxi, vyi)는 각각 i번째 로봇의 초기 착륙 위치와 속도이다 (|xi|, |yi| < 100000, |vxi|, |vyi| < 1000).

마지막 데이터셋 뒤에는 두 개의 0이 있는 줄이 온다. 이 줄은 어떤 데이터셋에도 속하지 않으며 처리해서는 안 된다.

각 데이터셋마다 모든 로봇 통신에 필요한 최소 통신 비용을 한 줄에 출력한다. 소수점 아래 자릿수는 임의로 출력해도 된다. 절대 오차는 0.001 이하여야 한다.