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

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

지하 케이블

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

요약
평면 위의 점이 최대 1000개 주어질 때, 모든 점을 잇는 서로 교차하지 않는 직선 케이블의 최소 총 길이를 구한다.
난이도

보통10점 중 5점

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

문제

한 도시가 보기 싫은 전봇대를 없애기 위해 전선을 지하로 옮기려고 한다. 여러 개의 점을 모두 연결해야 하는데 몇 가지 제약이 있다. 굴착 장비는 점과 점 사이를 직선으로만 팔 수 있고, 주어진 점을 제외한 어떤 위치에도 케이블은 하나만 지날 수 있어서 두 케이블이 서로 교차할 수 없다.

점들이 주어질 때, 모든 점의 쌍이 직접 또는 다른 점들을 거쳐 간접적으로 연결되도록 하는 데 필요한 케이블의 최소 총 길이를 구하라.

입력

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 점의 개수를 나타내는 정수 NN(2≤N≤10002 \le N \le 1000)으로 시작한다. 이어지는 NN개의 줄에는 각각 두 정수 XX와 YY(−1000≤X,Y≤1000-1000 \le X, Y \le 1000), 즉 한 점의 좌표가 주어진다. 한 테스트 케이스 안의 모든 점은 서로 다르다. 입력은 00 하나만 있는 줄로 끝난다.

출력

각 테스트 케이스에 대해, 모든 점을 연결하는 데 필요한 케이블의 최소 총 길이인 실수 하나를 출력한다. 소수점 아래 정확히 두 자리로 반올림하여 출력한다. 각 답을 한 줄에 하나씩 출력하고, 답들 사이에 빈 줄을 출력하지 않는다.

예제1

  1. 예제 1

    입력
    4
    0 0
    0 10
    10 0
    10 10
    2
    0 0
    10 10
    0
    
    예상 출력
    30.00
    14.14