돌고래 풀장

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

요약

중심이 서로 다른 원이 20개 이하로 주어질 때, 원들이 둘러싸는 바깥 영역의 개수를 센다.

난이도: 보통10점 중 6점
유형: 기하, 그래프, DFS
정답자: 아직 제출이 없습니다

문제

페르시아만 키시 섬에 새로 지어진 돌고래 풀장에서 즐기는 놀이 중 하나는 다음과 같다. 진행자는 여러 개의 플라스틱 링(원)을 물 위에 던지는데, 이때 어떤 링의 중심도 다른 링의 내부에 있지 않으며 어떤 두 링도 서로 접하지 않는다. 돌고래들은 진행자의 호루라기 소리에 맞추어, 모든 링의 바깥에 완전히 놓인 닫힌 영역을 통해 한 영역마다 한 마리씩 뛰어오르도록 훈련되어 있다. 돌고래들은 이러한 닫힌 영역의 개수가 돌고래의 수와 정확히 같을 때에만 뛰어오른다.

여기서 닫힌 영역이란, 모든 링의 바깥에 있으면서 링들에 의해 둘러싸인 유계(bounded) 평면 영역을 뜻한다. 주어진 각 링의 위치와 반지름을 보고, 링들 사이에 생기는 닫힌 영역의 개수를 구하는 프로그램을 작성하라.

입력

첫 줄에 테스트 케이스의 개수(최대 20)가 주어진다. 각 테스트 케이스의 첫 줄에는 플라스틱 링의 개수 $N$ ( $1 \le N \le 20$ )이 주어진다. 이어지는 $N$ 개의 줄에는 각각 세 정수가 주어지며, 앞의 두 정수는 링을 이루는 원의 중심의 $x$ , $y$ 좌표이고 세 번째 정수는 반지름이다. 좌표는 1000보다 작은 양의 정수이고, 반지름은 1 이상 100 이하이다.

출력

각 테스트 케이스마다, 그 테스트 케이스에서 링들 사이에 생기는 닫힌 영역의 개수를 한 줄에 하나씩 출력한다.

예제5

예제 1

입력

예상 출력

1
0

예제 2
입력
```
1
3
100 100 50
190 100 50
145 178 50
```
예상 출력
```
1
```
예제 3
입력
```
1
3
100 100 50
170 100 50
135 161 50
```
예상 출력
```
0
```
예제 4
입력
```
1
2
100 100 30
150 100 30
```
예상 출력
```
0
```
예제 5
입력
```
1
3
100 100 20
300 300 20
700 200 30
```
예상 출력
```
0
```