[WEEK02] 백준 10000 원 영역

문제

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.

원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.

영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

입력

첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)

입력으로 주어지는 원은 항상 유일하다.

출력

첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다.

풀이

큰 원 안에 내접원이 쭉 연결되어 있는 상태를 어떻게 판단하는지가 핵심이라고 생각한다.

우선 입력을 받을 때 중심점과 반지름을 이용해
[ 시작점, ' ( ' ], [ 끝점, ' ) ' ] 을 리스트에 저장해주었다.
이 후 시작점을 기준으로 오름차순 정렬하였고 시작점이 같다면 ')' 가 먼저 올 수 있도록 정렬하였다.

stack을 선언하여 시작점 끝점 정보를 저장한 리스트를 읽어오며 조건에 따라 값을 넣어주었다.

내접원으로 인해 내부 영역이 나뉘는걸 어떻게 판단할지만 적어보겠다.
( 가 들어있는 상태에서 똑같은 시작점을 가지는 ( 가 들어오면 스택에 들어있던 ( 에 내접의 가능성을 열어준다.
이 후 ) 가 들어오면 내접원끼리 쭉 이어지는지 판단하기 위해 현재 좌표와 다음 좌표를 비교했을 때 다르다면 내접의 가능성을 다시 닫아주면 된다.

) 가 들어오면 카운팅을 하는데 ( 의 상태에 따라 +1 또는 +2를 해주면 된다.

전체코드

n = int(input())
circle_info = []
stack = []
count = 1

for _ in range(n):
    r, c = list(map(int, sys.stdin.readline().split()))
    circle_info.append([r - c, '('])
    circle_info.append([r + c, ')'])
circle_info = sorted(circle_info, key = lambda x : (x[0], -ord(x[1])))

for i in range(2 * n):
    if stack:
        # 연속으로 open이 들어오고 좌표도 같다면 스택에 있는 open을 내접상태로 바꿔줌
        if circle_info[i][1] == '(' and circle_info[i][0] == stack[-1]['pos']:
            stack[-1]['state'] = 2
        # close가 들어오면 상태에 따라 점수 추가하고, pop 후 비어있으면 컨티뉴, open상태가 남아있다면
        # 이어지는지 확인하기 위해 현재 좌표와 다음좌표가 같은지 확인
        elif circle_info[i][1] == ')':
            count += stack.pop()['state']
            if not stack:
                continue
            if i + 1 < 2 * n and circle_info[i + 1][0] != circle_info[i][0]:
                stack[-1]['state'] = 1
            continue

    stack.append({'pos': circle_info[i][0], 'shape': circle_info[i][1], 'state': 1})

print(count)