공의 합집합

시간 제한2초메모리 제한1024 MB

요약

모든 공의 중심이 x축 위에 있어 합집합은 회전체가 된다. 부피를 p/q 곱하기 파이 꼴로 구해 p 곱하기 q의 역원을 1e9+7로 나눈 값을 출력한다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

3차원 좌표공간에 n개의 공(ball)이 있다. i (1 ≤ i ≤ n)번째 공은 겉표면이 중심 (xi, 0, 0)이고 반지름이 ri인 구이며, 이 공이 차지하는 영역은 Si = {(x, y, z) ∈ ℝ3 : (x - xi)2 + y2 + z2 ≤ ri2}이다.

모든 공의 합집합 S1 ∪ S2 ∪ ··· ∪ Sn의 부피를 구하는 프로그램을 작성하라.

입력

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

다음 n개 줄에는 공의 정보가 한 줄에 하나씩 주어지는데, i (1 ≤ i ≤ n)번째 줄에는 두 정수 xi (0 ≤ xi ≤ 106)와 ri (1 ≤ ri ≤ 106)가 공백 하나를 사이로 두고 주어진다.

출력

모든 공의 합집합 S1 ∪ S2 ∪ ··· ∪ Sn의 부피는 p⁄q π (단, p와 q는 서로소인 두 자연수)로 나타낼 수 있다. 이때, 첫 번째 줄에 V ⋅ q ≡ p (mod 109 + 7)을 만족하는 0 이상 109 + 6 이하의 정수 V를 출력하라. 입력 제약 조건을 만족하는 모든 입력에서 이러한 V가 유일하게 존재함을 증명할 수 있다.

예제2

예제 1
입력
```
1
1 4
```
예상 출력
```
333333421
```
예제 2
입력
```
2
3 4
6 3
```
예상 출력
```
100
```