지하 케이블
시간 제한1초메모리 제한128 MB
평면 위의 점이 최대 1000개 주어질 때, 모든 점을 잇는 서로 교차하지 않는 직선 케이블의 최소 총 길이를 구한다.
문제
한 도시가 보기 싫은 전봇대를 없애기 위해 전선을 지하로 옮기려고 한다. 여러 개의 점을 모두 연결해야 하는데 몇 가지 제약이 있다. 굴착 장비는 점과 점 사이를 직선으로만 팔 수 있고, 주어진 점을 제외한 어떤 위치에도 케이블은 하나만 지날 수 있어서 두 케이블이 서로 교차할 수 없다.
점들이 주어질 때, 모든 점의 쌍이 직접 또는 다른 점들을 거쳐 간접적으로 연결되도록 하는 데 필요한 케이블의 최소 총 길이를 구하라.
입력
입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 점의 개수를 나타내는 정수 ()으로 시작한다. 이어지는 개의 줄에는 각각 두 정수 와 (), 즉 한 점의 좌표가 주어진다. 한 테스트 케이스 안의 모든 점은 서로 다르다. 입력은 하나만 있는 줄로 끝난다.
출력
각 테스트 케이스에 대해, 모든 점을 연결하는 데 필요한 케이블의 최소 총 길이인 실수 하나를 출력한다. 소수점 아래 정확히 두 자리로 반올림하여 출력한다. 각 답을 한 줄에 하나씩 출력하고, 답들 사이에 빈 줄을 출력하지 않는다.