[17378] 공의 합집합

x축에 타코야끼마냥 중심을 꽂힌 다양한 크기의 구들이 있는데, 이 녀석들의 전체 부피를 구해야 한다. 그런데 서로 겹치는 경우가 생길 수 있기 때문에 그냥 구해서는 안 된다. 뭔가 방법을 써야 한다.

 

우선 3차원 상황을 그대로 써먹으려고 하면 불편하다. 어차피 문제 상황의 모든 도형이 x축을 중심으로 한 회전체 꼴이기 때문에 2차원 평면 위의 반원들로 차원을 낮추자. 

각 공 $S_i = (x - x_i)^2 + y^2 + z^2 \leq r_i^2$들은 이제 $C_i = (x - x_i)^2 + y^2 \leq r_i^2\ (y \geq 0)$으로 생각하자. 그럼 부피는 간단하게 $\displaystyle \pi\int_{a}^{b} y^2dx = \pi\int_{a}^{b} \{r_i^2 - (x - x_i)^2\}dx$로 생각할 수 있다.

 

어쨌든 이제 해야 할 작업은 '필요한' 반원과 '필요 없는' 반원을 골라내는 것이다. 그러니까 반원 중엔 그것의 일부가 전체 도형의 외곽선의 일부에 포함되는 경우가 있을 것이고 그냥 다른 반원들 사이에 묻혀 버려서 있든 없든 별로 상관없는 경우가 있을 것인데, 이 '필요 없는' 반원이 존재하면 계산하는 데 걸리적거리니까 얘네를 제거하든 하면 좋겠다.

 

이 '필요 없는' 반원을 두 가지 케이스로 나눠볼 수 있다. 반원이 반원 하나에 딱 가려지는 경우와 두 개 이상의 반원들에 걸쳐서 가려지는 경우인데, 일단 첫 번째 경우는 스위핑으로 해결할 수 있다. 반원 자체를 보지 말고 차원을 그냥 1차원으로 냅다 낮춰버리자. 반원을 그냥 반원이 $x$축과 만나는 두 점으로 표현해버리는 것이다. 이제 그걸 잘 정렬해서 어떤 정보만 들고 한번 쓱 훑으면 첫 번째 케이스의 반원만 딱 골라낼 수 있다.

 

이제 적분 구간을 따져야 한다. 사실 이것도 대충 관찰하면 얻을 수 있는 것이긴 한데... 우선 반원이 서로 만나는 점에서 적분함수가 바뀔 테니까 이 점들에 주목해야 한다. 만약 그 점들을 시간 내로 싸그리 구할 수 있다면 그걸로 컨벡스 헐을 돌려서 될 것 같은데 이건 잘 모르겠고, 아까 말한 두 번째 케이스: '반원이 다른 두 반원에 걸쳐서 가려지는 경우'를 안고 가면서 스위핑 비슷한 무언가로 해결하고자 한다.

 

이게 설명하기가 좀 그런데... 우선 반원들을 중심의 $x$좌표 순으로 정렬한다. 그리고 앞에서부터 리스트에서 인접한 두 반원의 교점을 차례차례 구해 나간다. 만약 어떤 시점에서 구한 교점과 그 다음 시점에서 구한 교점을 비교했을 때 다음에 구한 교점의 $x$좌표가 이전에 구한 교점의 $x$좌표보다 작거나 같다면 두 교점을 구할 때 공통적으로 들어간 그 반원을 리스트에서 제거한 후 이전 시점으로 돌아가 다시 계산을 진행한다.

 

이게 왜 되느냐? 만약 이전 시점에서 반원 $h_1, h_2$에 대해서 구한 교점의 $x$좌표가 2고 그 다음 시점에서 반원 $h_2, h_3$에 대해서 구한 교점의 $x$좌표가 1이라고 하자. 그럼 자명하게 $h_1$과 $h_3$의 교점이 $x=1$과 $x=2$ 사이에서 생기고, 그 교점의 $y$좌표는 해당 $x$에서 $h_2$의 $y$좌표보다 크다.

이런 상황이 발생한다는 것 자체가 $h_2$의 $r$보다 $h_1$의 $r$, 혹은 $h_3$의 $r$이 더 크다는 의미니까 반원 $h_2$는 반원 $h_1$과 $h_3$에 완전히 묻혀버리는 거라 리스트에서 없애버리면 된다.

말은 리스트에서 없애버린다고는 하지만 구현은 뭐 링크드리스트라도 쓰는 거 아니면 그렇게 쓱싹 없애기는 어렵고... 뭐 잘 구현하면 된다.

 

그렇게 적분 구간을 다 구했으면 이제 적분을 하면 되는데 모듈러가 1e9+7로 소수니까 모듈러 역수와 모듈러 상에서의 곱셈 뭐 그런 것들 따져서 오버플로우 안 나게 잘 해주면 된다.

아니면 즐거운 python Fraction을 쓰든가... 근데 시간 2초 고정이라 파이썬 쓰면 TLE 나지 싶음. 아직 파이썬으로 푼 사람도 없고...

17378번: 공의 합집합