섬 연결하기

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

요약

섬 다각형들을 꼭짓점 사이의 다리로 연결하되 각 다리는 물 위만 지나야 하며, 다리 길이 합의 최솟값과 다리 개수를 구한다.

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

문제

여러 개의 섬을 다리로 연결하여, 어떤 섬에서든 다른 모든 섬으로 갈 수 있도록 만들려고 합니다. 다리를 놓는 비용은 다리의 길이에 비례하므로, 전체 비용을 줄이려면 모든 섬을 연결하는 데 필요한 다리들의 총 길이를 최소로 해야 합니다. 모든 섬을 서로 연결하는 데 필요한 다리들의 최소 총 길이를 구하는 프로그램을 작성하세요.

각 섬은 다각형으로 주어지며, 다리는 서로 다른 두 다각형의 꼭짓점(코너) 사이에만 놓을 수 있습니다. 다리는 반드시 물 위로만 지나가야 하며, 어떤 섬의 육지 위로도 지날 수 없습니다. 단, 두 다리가 서로 교차하는 것은 허용됩니다. 섬의 모양은 볼록하지 않을 수도 있습니다.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어집니다.

각 테스트 케이스의 첫 줄에는 섬의 개수 $N$ ( $2 \le N \le 15$ )이 주어집니다. 이어지는 $N$ 개의 줄에는 각각 하나의 섬이 주어집니다. 한 섬은 꼭짓점의 개수 $P$ ( $1 \le P \le 25$ )와, 그 뒤에 이어지는 $P$ 개의 좌표쌍 $x\ y$ 로 이루어진 다각형입니다. 각 좌표는 $[-1000, 1000]$ 범위의 정수입니다. 꼭짓점들은 순서대로 주어지며, 연속한 꼭짓점들을 잇고 마지막 꼭짓점을 다시 첫 꼭짓점과 이으면 섬의 해안선이 됩니다.

섬들은 서로 닿거나 겹치지 않음이 보장됩니다.

출력

각 테스트 케이스마다 다음 형식으로 두 줄을 출력합니다.

The minimal interconnect consists of B bridges
with a total length of L.

여기서 $B$ 는 놓은 다리의 개수, $L$ 은 다리들의 총 길이이며, $L$ 은 소수점 아래 정확히 세 자리까지 출력합니다.

예제6

예제 1

입력

1
3
4 0 0 0 1 1 1 1 0
4 2 0 2 1 3 1 3 0
3 4 0 5 0 5 1

예상 출력

The minimal interconnect consists of 2 bridges
with a total length of 2.000.

예제 2

입력

1
2
4 0 0 0 1 1 1 1 0
4 3 0 3 1 4 1 4 0

예상 출력

The minimal interconnect consists of 1 bridges
with a total length of 2.000.

예제 3

입력

1
4
4 0 0 0 1 1 1 1 0
4 2 0 2 1 3 1 3 0
4 4 0 4 1 5 1 5 0
4 6 0 6 1 7 1 7 0

예상 출력

The minimal interconnect consists of 3 bridges
with a total length of 3.000.

예제 4

입력

1
2
4 0 0 0 1 1 1 1 0
4 2 2 2 3 3 3 3 2

예상 출력

The minimal interconnect consists of 1 bridges
with a total length of 1.414.

예제 5

입력

1
3
4 0 0 0 2 2 2 2 0
4 7 0 7 2 9 2 9 0
4 3 -30 3 30 4 30 4 -30

예상 출력

The minimal interconnect consists of 2 bridges
with a total length of 56.178.

예제 6

입력

2
2
4 0 0 0 1 1 1 1 0
4 3 0 3 1 4 1 4 0
2
4 0 0 0 1 1 1 1 0
4 2 2 2 3 3 3 3 2

예상 출력

The minimal interconnect consists of 1 bridges
with a total length of 2.000.
The minimal interconnect consists of 1 bridges
with a total length of 1.414.