파이썬 백준 10000 원 영역

import sys input = sys.stdin.readline sys.setrecursionlimit(10**8) from bisect import bisect_left n = int(input()) l = [] for i in range(n) :     x, r = map(int, input().split())     l.append([x - r, x + r]) l.sort(key = lambda x : (x[0], -x[1])) count = 0 def check(big, small) :     global count     if big[1] == small[1] :         count = count + 1         return     nextidx = bisect_left(l, [small[1], -1000000000])     if nextidx == len(l) :         return     if small[1] == l[nextidx][0] :         check(big, l[nextidx]) for i in range(n-1) :     if l[i][0] == l[i+1][0] :         check(l[i], l[i+1]) print(1 + n + count)

폐곡면인 원이 하나 생길 때마다 평면이 둘로 분할된다.

단 서로 접하는 원들이 큰 원 하나의 지름을 빈틈없이 채울 경우 평면이 셋으로 분할된다.

즉 위의 경우를 세어 n+1에 더하면 답이 된다.

 

input마다 원의 시작점 끝점을 list에 저장한다.

시작점이 같은(=내접하는) 원 중 큰 원이 리스트 앞에 있어야 DFS를 최고레벨부터 쓰며 내려갈 수 있다.

시작점이 같을 때 끝점이 클수록 큰 원이므로 시작점 정순 끝점 역순으로 정렬한다.

 

big과 small을 받았을 때 small의 끝점에서 시작하는(=외접하는) 다른 원이 있는지 확인하고, 있다면 재귀한다.

이때 bisect를 썼는데, 리스트의 원소가 int가 아니라 list다보니 함수의 input도 리스트로 줘야했다.

근데 끝점은 역순으로 정렬했으니 [1]에는 range 최댓값을 넣어야 left가 나올 것 같은데

+10억을 넣으니 제값이 안나오고 정순정렬처럼 최솟값인 -10억을 넣어야 제값이 나온다.

???

남이 만든 함수를 import하면 왜 되고 왜 안되는질 모르는게 문제다. 이게 왜 되지?

 

아무튼 외접의 연속으로 big의 끝까지 도달했다면 big이 작은 원들로 이분된 것이므로 count를 +1한다.

 

모든 내접관계에 대해 함수를 실행한 뒤 1+n+count를 출력하면 끝