원 그리기
시간 제한5초메모리 제한1024 MB
최대 2000개의 원을 순서대로 그리며 새 원이 이미 그려진 영역의 내부를 지울 때, 종이에 남아 보이는 원호 길이의 합을 구한다.
문제
Alice는 원 그리기를 좋아한다. 시간이 나면 종이를 한 장 꺼내 원을 그린다.
Alice는 좌표계가 있는 종이 위에 원을 그린다. 각 원은 순서쌍 (x, y, r)로 나타내며, (x, y)는 원의 중심 위치, r은 반지름이다. 두 원이 서로 교차하는 것을 싫어하기 때문에, 새 원을 그릴 때마다 그 원의 내부를 항상 지운다. 즉, 새로 그리는 원의 내부를 지워 연필 선인 원주만 남긴다. (물론 기존 원 위에 덧그리면 새 연필 선이 기존 원주를 가려 보이지 않게 된다.)
예를 들어 (그림 A.1 참고),
- (0, 0, 1)을 먼저 그리고 (0, 0, 2)를 그리면 첫 번째 원은 완전히 지워진다.
- (−1, 0, 2)를 먼저 그리고 (1, 0, 2)를 그리면 첫 번째 원 중 x = 0 축의 오른쪽 부분이 지워진다.
그림 A.1: 예시 입력. 점선은 지워진 영역이다.
여러 원을 그린 뒤, 종이에 아직 보이는 모든 곡선 선분의 총 길이를 알고 싶어 한다.
입력
첫째 줄에 Alice가 그린 원의 수 N (1 ≤ N ≤ 2000)이 주어진다. 다음 N개 줄에는 i번째로 그린 원을 나타내는 세 정수 xi, yi, ri가 공백으로 구분되어 주어진다 (−10 000 ≤ xi, yi ≤ 10 000, 1 ≤ ri ≤ 10 000, i = 1 . . . N).
출력
보이는 모든 곡선 선분의 총 길이를 출력한다.
절대 오차 또는 상대 오차가 10−6 이하이면 정답으로 인정된다.