시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 36 9 8 22.857%

문제

서강대학교 K관 512호 랩실에 달고나 기계가 생겼다. 달고나 기계 옆에는 뽑기를 위해 원 또는 단순 다각형 모양의 모형 틀이 준비되어 있다. 일반적으로 모형 틀의 모양에 따라 뽑기의 난이도가 결정된다. 하지만 그 어떤 모양도 뽑기 장인 상원이를 만족시킬 수는 없다. 뽑기가 너무 쉬워 고민이던 상원이는 더 어려운 뽑기를 만드는 방법을 떠올렸다. 여러 가지 모형틀을 한 뽑기 안에 찍는다면 뽑아야 할 조각의 수가 많아져 더 어려워질 것이다!

2차원 평면 상에 원 또는 단순 다각형 모양의 도형들이 주어졌을 때, 평면을 몇 개의 영역으로 나누는지 구하는 프로그램을 작성하자.

그림 1: 첫 번째 예제에 따른 뽑기 모양이다.

입력

다음과 같이 입력이 주어진다.

$N$
$poly_1$
$poly_2$
$...$
$poly_N$
  • $N$은 도형의 개수이다. ($1 \le N \le 2\,000$)
  • $poly_i$는 각 도형의 정보이다.
    • 원인 경우, 다음과 같이 $poly_i$가 주어진다.
      $1 \ x \ y \ r$
      • 중심이 ($x,\ y$)이고 반지름이 $r$인 원이다. ($-10\,000 \le x,\ y \le 10\,000,\ 1 \le r \le 10\,000$)
    • 단순 다각형인 경우, 다음과 같이 $poly_i$가 주어진다.
      $m \ x_1 \ y_1 \ x_2 \ y_2 \ ... \ x_m \ y_m$
      • $m$은 단순 다각형을 이루는 꼭짓점의 개수이다.
      • ($x_i,\ y_i$)는 각 꼭짓점의 좌표이다. ($-10\,000 \le x_i,\ y_i \le 10\,000$)
      • 각 꼭짓점은 반시계방향 순서로 주어진다.
  • 모든 단순 다각형의 선분 개수와 원의 개수의 합은 $2\,000$을 넘지 않는다.
  • 세 개 이상의 원 또는 선분이 한 점을 지나는 경우는 주어지지 않는다.
  • 입력으로 주어지는 모든 수는 정수다.

출력

도형들로 인해 나눠지는 영역의 수를 출력한다.

예제 입력 1

6
7 3 5 1 2 2 2 0 -2 6 -2 4 2 5 2
4 2 0 2 -4 4 -4 4 0
1 16 2 2
7 20 0 12 0 14 -2 14 -6 16 -4 18 -6 18 -2
1 13 8 2
1 10 8 3

예제 출력 1

9

예제 입력 2

4
4 750 250 -750 250 -750 -250 750 -250
1 0 0 250
1 500 0 250
1 -500 0 250

예제 출력 2

12

예제 입력 3

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

예제 출력 3

14