캠퍼스 연결하기

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

요약

평면 위 N개 점과 이미 놓인 무료 간선이 주어질 때, 모든 점을 연결하는 최소 유클리드 길이의 새 간선을 구한다.

난이도: 보통10점 중 6점
유형: 최소 신장 트리, 유니온 파인드, 그래프, 기하
정답자: 아직 제출이 없습니다

문제

폴카루 대학교(University of Polkaroo) 캠퍼스에 새 건물이 여러 채 지어지고 있다. 대학은 모든 건물이 통신 케이블 네트워크를 통해 (직접 또는 간접적으로) 서로 연결되기를 원한다.

각 건물은 $x$ 좌표와 $y$ 좌표로 주어지는 평면 위의 한 점으로 나타낸다. 통신 케이블 하나는 정확히 두 건물을 잇는 선분이며, 정보는 케이블을 따라 양방향으로 전달된다. 케이블끼리는 자유롭게 교차할 수 있지만, 오직 끝점(건물)에서만 서로 연결된다.

캠퍼스 지도에는 모든 건물의 위치와 이미 설치된 통신 케이블이 표시되어 있다. 기존 케이블은 바꿀 수 없다. 모든 건물이 연결되도록 새 통신 케이블을 설치하되, 새로 사용하는 케이블의 총 길이를 최소로 하려고 한다.

입력

입력은 하나의 테스트 케이스를 나타낸다. 첫 줄에는 건물의 수 $N$ $(1 \le N \le 750)$ 이 주어진다. 건물은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다. 이어지는 $N$ 개의 줄에는 각 건물의 $x$ 좌표와 $y$ 좌표가 주어진다. 좌표는 절댓값이 $10\,000$ 이하인 정수이며, 같은 위치에 있는 두 건물은 없다.

그다음 줄에는 기존 케이블의 수 $M$ $(0 \le M \le 1000)$ 이 주어지고, 이어지는 $M$ 개의 줄에 각 기존 케이블이 직접 잇는 두 건물의 번호가 주어진다. 같은 두 건물을 직접 잇는 케이블은 최대 한 개뿐이다.

출력

새로 설치하는 케이블의 총 길이의 최솟값을 소수점 아래 둘째 자리까지 반올림하여 한 줄에 출력한다.

예제3

예제 1

입력

예상 출력

4.41

예제 2
입력
```
1
0 0
0
```
예상 출력
```
0.00
```
예제 3
입력
```
2
0 0
3 4
0
```
예상 출력
```
5.00
```