20939번 - 달고나

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

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

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

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

• $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$)
    • 각 꼭짓점은 반시계방향 순서로 주어진다.

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

• $N$은 도형의 개수이다. ($1 \le N \le 2\,000$)
• 모든 단순 다각형의 선분 개수와 원의 개수의 합은 $2\,000$을 넘지 않는다.
• 세 개 이상의 원 또는 선분이 한 점을 지나는 경우는 주어지지 않는다.
• 입력으로 주어지는 모든 수는 정수다.