아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

별자리 만들기

면접 대비

시간 제한1초메모리 제한128 MB

요약
평면 위의 점 n개를 유클리드 거리를 비용으로 하는 선분으로 모두 연결할 때 최소 총비용을 구한다.
난이도

보통10점 중 5점

유형
최소 신장 트리, 그래프, 기하, 유니온 파인드
정답자
아직 제출이 없습니다

문제

도현이는 우주의 신이다. 도현이는 2차원 평면 위에 흩어져 있는 nn개의 별을 선으로 이어 하나의 별자리를 만들려고 한다.

별자리는 다음 두 조건을 만족해야 한다.

  • 별자리를 이루는 각 선은 서로 다른 두 별을 잇는 직선이다.
  • 모든 별은 이 선들을 통해 서로 직접 또는 간접적으로 연결되어야 한다.

선 하나를 이을 때 드는 비용은 그 선이 잇는 두 별 사이의 거리(유클리드 거리)와 같다. 모든 별을 하나로 연결하는 별자리를 만드는 데 드는 최소 비용을 구하여라.

입력

첫째 줄에 별의 개수 nn이 주어진다. (1≤n≤1001 \le n \le 100)

둘째 줄부터 nn개의 줄에 걸쳐 각 별의 xx, yy 좌표가 주어진다. 각 좌표는 소수점 아래 최대 둘째 자리까지 주어지는 10001000 이하의 양의 실수이다.

출력

첫째 줄에 별자리를 만드는 최소 비용을 소수점 아래 정확히 둘째 자리까지 반올림하여 출력한다.

예제1

  1. 예제 1

    입력
    3
    1.0 1.0
    2.0 2.0
    2.0 4.0
    
    예상 출력
    3.41