| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 270 | 46 | 33 | 15.493% |
3차원 좌표공간에 n개의 공(ball)이 있다. 이 중 i (1 ≤ i ≤ n)번째 공은 겉표면이 중심이 (xi, 0, 0)이고 반지름은 ri인 구 형태이며, 이 공이 차지하는 영역은 Si = {(x, y, z) ∈ R3 : (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가 유일하게 존재함을 증명할 수 있다.
1 1 4
333333421
반지름이 4인 공의 부피는 4⁄3 · 43· π = 256⁄3 π이다. V ⋅ 3 ≡ 256 (mod 109+ 7)의 해를 구하면 V ≡ 333,333,421 (mod 109+ 7)이다.
2 3 4 6 3
100
그림은 아래와 같으며, 합집합의 부피는 100π이다.
sphere
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2019 F번