별자리 만들기
면접 대비시간 제한1초메모리 제한128 MB
평면 위의 점 n개를 유클리드 거리를 비용으로 하는 선분으로 모두 연결할 때 최소 총비용을 구한다.
문제
도현이는 우주의 신이다. 도현이는 2차원 평면 위에 흩어져 있는 개의 별을 선으로 이어 하나의 별자리를 만들려고 한다.
별자리는 다음 두 조건을 만족해야 한다.
- 별자리를 이루는 각 선은 서로 다른 두 별을 잇는 직선이다.
- 모든 별은 이 선들을 통해 서로 직접 또는 간접적으로 연결되어야 한다.
선 하나를 이을 때 드는 비용은 그 선이 잇는 두 별 사이의 거리(유클리드 거리)와 같다. 모든 별을 하나로 연결하는 별자리를 만드는 데 드는 최소 비용을 구하여라.
입력
첫째 줄에 별의 개수 이 주어진다. ()
둘째 줄부터 개의 줄에 걸쳐 각 별의 , 좌표가 주어진다. 각 좌표는 소수점 아래 최대 둘째 자리까지 주어지는 이하의 양의 실수이다.
출력
첫째 줄에 별자리를 만드는 최소 비용을 소수점 아래 정확히 둘째 자리까지 반올림하여 출력한다.