만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

비바 콘페티

시간 제한2초메모리 제한512 MB

요약
원판 n개가 아래에서 위 순서로 쌓여 있을 때, 위에서 보았을 때 일부라도 가려지지 않고 남는 원판의 개수를 센다.
난이도

보통10점 중 7점

유형
기하, 구현, 완전 탐색, 정렬
정답자
아직 제출이 없습니다

문제

콘페티는 파티나 축제에서 뿌리는 작은 색종이 원반이다. 한 번에 많이 뿌리기 때문에 원반끼리 겹쳐 쌓이고, 아래에 깔려 보이지 않는 원반도 생긴다.

크기가 제각각인 원반을 탁자 위에 흩뿌렸다. 각 원반의 위치와 크기가 주어질 때, 위에서 내려다보았을 때 보이는 원반이 몇 개인지 세어라. 원반이 보인다는 말은 위에 놓인 원반에 가려지지 않은 부분이 넓이를 가진 채 남아 있다는 뜻이다.

다음 그림은 첫 번째 예제 입력의 첫 배치다. 맨 아래 원반이 아직 보인다.

입력

입력은 여러 배치로 이루어진다. 한 배치의 형식은 다음과 같다.

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

배치의 첫 줄에는 그 배치에 놓인 원반의 개수 nn이 주어진다. nn은 100 이하의 양의 정수다. 이어지는 nn개의 줄에는 원반 하나의 중심 좌표와 반지름이 주어진다. 세 값 모두 소수점 아래 12자리까지 쓴 십진 실수다.

오차 한계는 ±5×10−13\pm 5 \times 10^{-13}이다. 즉 입력값을 5×10−135 \times 10^{-13}보다 작게 바꾸어도 보이는 원반은 달라지지 않는다.

원반에 속한 모든 점의 좌표는 −10-10 이상 1010 이하다.

원반은 쌓인 순서대로 주어진다. x1 y1 r1x_1\ y_1\ r_1이 맨 아래 원반이고 xn yn rnx_n\ y_n\ r_n이 맨 위 원반이다. 관찰자는 위에서 내려다본다.

입력의 끝은 0 하나만 있는 줄로 표시한다.

출력

각 배치마다 보이는 원반의 개수를 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    3
    0 0 0.5
    -0.9 0 1.00000000001
    0.9 0 1.00000000001
    5
    0 1 0.5
    1 1 1.00000000001
    0 2 1.00000000001
    -1 1 1.00000000001
    0 -0.00001 1.00000000001
    5
    0 1 0.5
    1 1 1.00000000001
    0 2 1.00000000001
    -1 1 1.00000000001
    0 0 1.00000000001
    2
    0 0 1.0000001
    0 0 1
    2
    0 0 1
    0.00000001 0 1
    0
    
    예상 출력
    3
    5
    4
    2
    2
    
  2. 예제 2

    입력
    1
    0 0 1
    2
    0 0 1
    0 0 2
    2
    0 0 2
    0 0 1
    0
    
    예상 출력
    1
    1
    2
    
  3. 예제 3

    입력
    2
    0 0 1
    1 0 1
    3
    -1 0 1
    1 0 1
    0 0 1
    0
    
    예상 출력
    2
    3