사슴 방지 울타리

Magnus 아저씨는 재조림 사업의 일환으로 농장에 어린 묘목을 몇 그루 심었다. 안타깝게도 사슴이 연한 묘목의 순과 잎을 먹어 버리기 때문에, 묘목 주변에 보호 울타리를 세워야 한다. 사슴과 다른 묘목 포식자들이 울타리 너머로 어느 정도 손을 뻗을 수 있으므로, 모든 울타리는 각 묘목에서 최소 거리(마진) 이상 떨어져 있어야 한다.

사슴 방지 울타리는 꽤 비싸서, Magnus 아저씨는 사용하는 울타리의 총 길이를 최소화하려 한다. 여러분의 임무는 묘목을 둘러싸 보호하는 데 필요한 최소 울타리 길이를 계산하는 프로그램을 작성하는 것이다. 울타리는 직선 구간과 곡선 구간을 모두 포함할 수 있다. 모든 묘목을 둘러싸는 하나의 울타리를 설계해도 되고, 묘목을 여러 그룹으로 나누어 각각을 둘러싸는 여러 개의 울타리를 설계해도 된다.

그림 6은 마진 요구량이 다른 세 그루의 묘목으로 이루어진 두 가지 예시 구성을 보여 준다. 첫 번째 샘플 입력에 해당하는 위쪽 구성에서 최소 길이 해는 분리된 두 개의 울타리로 이루어진다. 두 번째 샘플 입력에 해당하는 아래쪽 구성에서 최소 길이 해는 하나의 울타리로 이루어진다.

그림 6: 사슴 방지 울타리.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 묘목의 수 N (0 < N ≤ 9)과 각 묘목 주변에 필요한 마진 M (0 < M ≤ 200)이 주어진다. 이 줄 다음에 N개의 줄이 이어진다. 이 N개의 줄 각각에는 묘목의 직교 좌표를 나타내는 두 정수 x와 y가 주어진다 (|x| ≤ 100, |y| ≤ 100). 두 묘목이 같은 위치에 있는 경우는 없다. 편의상 묘목은 모두 점으로 간주할 수 있고, 사슴 방지 울타리의 두께는 0으로 간주할 수 있다.

마지막 테스트 케이스 다음에는 두 개의 0이 있는 줄이 온다.

각 테스트 케이스마다 케이스 번호(1부터 시작)와 주어진 마진으로 묘목을 보호하는 데 필요한 최소 총 울타리 길이를 출력한다. 길이는 소수점 오른쪽 두 자리까지 출력한다. 샘플 출력의 형식을 따른다.