원들을 감싸는 원

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

요약

n개의 원과 반지름 r이 주어질 때, 주어진 모든 원을 포함하는 반지름 r인 원들의 합집합 경계의 길이를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

평면 위에 반지름과 위치가 제각각인 원들의 집합 $C$ 가 주어진다. 이 원들은 서로 겹칠 수도 있다. 반지름이 $r$ 인 원 하나를 적절한 위치에 놓으면, $r$ 이 충분히 클 때 그 원은 집합 $C$ 의 모든 원을 완전히 감쌀 수 있다.

반지름 $r$ 인 원이 $C$ 의 모든 원을 감싸도록 놓을 수 있는 위치는 하나가 아니라 여러 개일 수 있다. 이렇게 $C$ 를 감쌀 수 있는 모든 위치에서 그린 원들이 덮는 영역의 합집합을 $U$ 라 하자. 즉, $U$ 에 속한 각 점에 대해 그 점과 $C$ 의 모든 원을 동시에 감싸는 반지름 $r$ 짜리 원이 적어도 하나 존재한다. 이때 영역 $U$ 의 둘레(경계선)의 길이를 구하여라.

아래 그림 I.1은 원들의 집합 $C$ 와 영역 $U$ 의 예이다. 실선으로 그려진 세 원이 $C$ 에 속한 원이고, 점선 원들은 $C$ 를 감쌀 수 있는 원의 여러 위치를 나타내며, 굵은 점선으로 둘러싸인 부분이 영역 $U$ 이다.

그림 I.1: 원 집합의 예

입력

입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트의 개수는 $100$ 개 미만이다. 각 데이터 세트의 형식은 다음과 같다.

n r
x1 y1 r1
x2 y2 r2
...
xn yn rn

첫 줄에는 두 양의 정수 $n$ 과 $r$ 이 공백 하나로 구분되어 주어진다. $n$ 은 집합 $C$ 에 속한 원의 개수로 $100$ 을 넘지 않으며, $r$ 은 감싸는 원의 반지름으로 $1000$ 을 넘지 않는다.

이어지는 $n$ 개의 줄에는 각각 세 정수가 공백으로 구분되어 주어진다. $(x_i, y_i)$ 는 $C$ 의 $i$ 번째 원의 중심 좌표이고 $r_i$ 는 그 반지름이다. $-500 \le x_i \le 500$ , $-500 \le y_i \le 500$ , $1 \le r_i \le 500$ 임이 보장된다.

입력의 끝은 공백으로 구분된 두 개의 $0$ 으로 이루어진 줄로 표시된다.

출력

각 데이터 세트마다 영역 $U$ 의 둘레 길이를 소수점 아래 정확히 두 자리로 반올림하여 한 줄에 출력한다(예: 81.68). 만약 $r$ 이 너무 작아 $C$ 의 모든 원을 감쌀 수 없으면(즉 유효한 위치가 존재하지 않으면) 0.00만 출력한다. 그 밖의 문자는 출력하지 않는다.

입력은 반올림한 값이 명확하게 정해지도록 주어진다.

힌트

그림 I.2: 마지막 데이터 세트를 나타낸 그림

예제2

예제 1

입력

1 10
5 5 7
2 12
5 5 7
8 6 3
3 10
3 11 2
2 1 1
2 16 3
3 15
-5 2 5
9 2 9
5 8 6
3 38
-25 -10 8
30 5 7
-3 35 11
3 39
-25 -10 8
30 5 7
-3 35 11
3 800
-400 400 2
300 300 1
300 302 1
3 800
400 -400 2
300 300 1
307 300 3
8 147
130 80 12
130 -40 12
-110 80 12
-110 -40 12
70 140 12
70 -100 12
-50 140 12
-50 -100 12
3 493
345 154 10
291 111 75
-275 -301 46
4 55
54 0 1
40 30 5
27 36 10
0 48 7
3 30
0 3 3
-3 0 4
400 0 3
3 7
2 3 2
-5 -4 2
-4 3 2
3 10
-5 -4 5
2 3 5
-4 3 5
4 6
4 6 1
5 5 1
1 7 1
0 1 1
3 493
345 154 10
291 111 75
-275 -301 46
5 20
-9 12 5
0 15 5
3 -3 3
12 9 5
-12 9 5
0 0

예상 출력

예제 2
입력
```
1 20
0 0 5
0 0
```
예상 출력
```
219.91
```