백준 3552 - Circles on a Screen (Python)

문제 정보

• https://www.acmicpc.net/problem/3552
• 기하학, 스위핑

---

문제 정리

검은 픽셀로만 이루어진 W*H 크기의 격자 위에 원을 N개 그리려고 한다. 원의 중심 $(x_c, y_c)$에 대해 $\sqrt{(x_c-x)^2 + (y_c-y)^2} \leq r$ 이 수식을 만족하는 픽셀은 흰 픽셀이 될 때, N개의 원을 전부 그린 뒤 격자에 남은 검은 픽셀의 수를 구하는 문제이다.

---

풀이

우선 격자의 크기는 $W, H \leq 2,000$, 원의 개수는 $N \leq 100$ 이므로 단순히 모든 격자에 대해 흰색 픽셀인지 체크하는 $O(W^2N)$ 브루트포스는 TLE가 발생한다. 좀 더 빠른 방법으로 풀어야 한다.

한 세로선 x=i에 대해, 이 세로선 위에서 각 원들이 차지하는 흰색 픽셀의 y구간을 도출한 뒤, 각 구간을 정렬하여 병합하면 x=i일 때의 흰색 픽셀 개수를 구할 수 있다. 이 과정을 모든 x에 대해 반복하면 된다. 이 경우 $O(WNlogN)$이 된다.

더 빨리 풀 수 있나? 푼 사람이 10명밖에 없어서 잘 모르겠다. 구간 병합을 좀 더 빠르게 할 수 있을 것 같긴 한데...

---

코드

# 백준 3552

import io
import math

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(X, Y, circles):
    total = 0
    for curX in range(X):
        # 현재 x가 curX일 때 각 원에 대해 흰색으로 칠해지는 y구간 저장
        line = []
        for cX, cY, cR in circles:
            if abs(cX - curX) <= cR:
                temp = (cR*cR - (cX-curX)*(cX-curX))**0.5
                line.append([max(0, math.ceil(cY-temp)), min(int(cY+temp), Y-1)])

        # 구간 병합 및 흰색 개수 도출
        if len(line) > 0:
            line.sort()
            prevS = line[0][0]
            prevE = line[0][1]
            for curS, curE in line:
                # 이전 구간과 겹치지 않는 경우
                if max(prevS, curS) > min(prevE, curE):
                    total += prevE - prevS + 1
                    prevS = curS
                    prevE = curE
                else:
                    prevS = min(prevS, curS)
                    prevE = max(prevE, curE)
            total += prevE - prevS + 1

    return X*Y - total


def main():
    X, Y, N = map(int, input().split())
    circles = []
    for _ in range(N):
        circles.append(list(map(int, input().split())))

    print(solve(X, Y, circles))


main()