주근깨 (Freckles)

invalid-file

딕 반 다이크 쇼라는 TV 프로그램에서, 딕의 아들 리치가 등에 있는 주근깨들을 연결하는 선을 그어서 자유의 종을 그리는 에피소드가 나온 적이 있다.

딕의 등을 여러 (x, y) 위치에 주근깨가 있는 평면이라고 생각해보자. 지금 우리는 리치가 최소한의 잉크로 점을 연결할 수 있는 방법을 알려줘야 한다. 리치는 점 사이에 직선을 긋는 식으로 점을 연결한다. 그리고 각 직선을 그을 때마다 펜을 등에서 뗀다. 이 일이 끝나고 나면 등에 있는 모든 주근깨가 연결되어야 한다.

입력
첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 입력되고, 그 다음 줄은 빈 줄이다.
각 테스트 케이스의 첫째 줄에는 0보다 크고 100이하의 정수 n이 입력되는데, 이 정수는 딕의 등에 있는 주근깨 개수를 뜻한다. 각 주근깨마다 한 줄씩 그 주근깨의 위치를 나타내는 좌표가 입력된다.
서로 다른 테스트 케이스 사이에는 빈 중이 하나씩 입력된다.

출력
각 테스트 케이스에 대해 모든 주근깨를 연결하기 위해 잉크로 연결해야 하는 선 길이의 합을 소수점 둘째 자리까지 출력한다. 서로 다른 테스트 케이스에 대한 결과 사이에는 빈 줄을 하나씩 출력한다.

입력예
1

3
1.0 1.0
2.0 2.0
2.0 4.0

출력예
3.41

참고사항
1. 각 점(노드)이 모두 연결된 그래프에서 최소신장트리를 구하는 문제.
2. 프림 알고리즘 / 크루스칼 알고리즘