화면 위의 원들

시간 제한3초메모리 제한256 MB

요약
w×h 화면에 원 최대 100개를 그린 뒤, 원들의 합집합에 포함되지 않아 검은색으로 남는 픽셀 수를 구합니다.
난이도

보통10점 중 5점

유형
기하, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

앤드루는 검은 화면에 nn개의 흰색 원을 그리는 프로그램을 작성했다. 화면은 흑백이며 해상도는 w×hw \times h 픽셀이다. 픽셀은 왼쪽 위 모서리 (0,0)(0, 0)부터 오른쪽 아래 모서리 (w−1,h−1)(w-1, h-1)까지 번호가 매겨진다.

중심이 픽셀 (xc,yc)(x_c, y_c)이고 반지름이 rr인 원은 (xc−x)2+(yc−y)2≤r\sqrt{(x_c - x)^2 + (y_c - y)^2} \le r을 만족하는 모든 픽셀 (x,y)(x, y)로 이루어진다. 원이 화면을 벗어나면 벗어난 부분은 잘린다. 하나 이상의 원에 속하는 픽셀은 흰색이 된다.

앤드루는 완성된 그림이 마음에 들어 그것을 벽에 그대로 옮기려고 한다. 벽은 흰색이고 일부 픽셀만 검게 칠할 수 있으므로, 검은 물감이 얼마나 필요한지 알아야 한다. 그는 그림을 픽셀 단위로 정확히 옮긴다. nn개의 원을 모두 그린 뒤 화면에 남는 검은 픽셀의 개수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 세 정수 ww, hh, nn이 주어진다 (1≤w,h≤20 0001 \le w, h \le 20\,000; 1≤n≤1001 \le n \le 100). 다음 nn개의 줄에는 각각 하나의 원이 세 정수 xix_i, yiy_i, rir_i로 주어진다 (0≤xi<w0 \le x_i < w; 0≤yi<h0 \le y_i < h; 0≤ri≤40 0000 \le r_i \le 40\,000). 이는 중심이 픽셀 (xi,yi)(x_i, y_i)이고 반지름이 rir_i인 원을 나타낸다.

출력

화면에 남는 검은 픽셀의 개수를 정수 하나로 출력한다.

힌트

위 그림은 두 번째 예제에 해당한다.

예제2

  1. 예제 1

    입력
    5 3 2
    1 1 1
    3 1 1
    
    예상 출력
    6
    
  2. 예제 2

    입력
    12 9 2
    3 3 2
    7 5 4
    
    예상 출력
    51