[백준][Python] 10000 원 영역

 

라인 스위핑. 큰걸 기준으로 작은걸 감싸냐 안감싸냐

왼쪽이 겹치면 재귀로 오른쪽 이 겹쳐지는 원이 나올때까지 재귀(큰 원 안에 원이 몇개 겹치나 조사하기 위함)

 

import sys
from bisect import bisect_left
input = sys.stdin.readline
sys.setrecursionlimit(400000)

def next_circle(cur_c,next_c):
    global cnt
    if circles[cur_c][1] == circles[next_c][1]:
        cnt += 1
        return
    tmp = bisect_left(circles,(circles[next_c][1],))
    if tmp == len(circles):
        return
    if circles[tmp][0]==circles[next_c][1]:
        next_circle(cur_c,tmp)


n = int(input())
circles = []
for i in range(n):
	x,r = map(int,input().split())
	circles.append((x-r,x+r))
circles.sort(key=lambda x:(x[0],-x[1]))

cnt = 0
for i in range(n-1):
	if circles[i][0] == circles[i+1][0]:
		next_circle(i,i+1)
print(n+cnt+1)