Union of Circles
문제 정보
문제
N개의 원들의 영역의 합집합의 넓이를 구하는 법에 대해 생각해봅시다.
그린 정리에 의해 임의의 폐곡선 C의 넓이를 구하는 식은 다음과 같습니다.
원들이 다음과 같이 주어져 있다고 합시다. 이 원들을 폐곡선으로 나타내는 것은 가장 외곽에 있는(호가 다른 원에 포함되지 않는 부분)부분이 원의 중심을 기준으로 어느 각도의 구간에 포함되는지 검사하면 됩니다.
이제 각 원을 원의 중심(x_c,y_c)를 기준으로 한 각도를 매개변수로 하여 식을 만들면
가 되고, 또한 각 원에 대해 외곽선에 원의 중심을 기준으로 각도가 [s_i,e_i]인 호가 포함되는 경우 위의 넓이를 구하는 식을 이용하여 더해주시면 됩니다.
하나의 원과 나머지 원에 의해 생기는 교점의 수는 O(N)개 이므로, 이로 인해 생기는 호가 다른 원에 포함되는지 안되는지 따져보는 것으로 전체시간 O(N^3)에 원들의 넓이를 구할 수 있습니다. 그러나 약간의 개선을 통하여 O(N^2lgN)의 시간에 구할 수도 있습니다. N개의 원들을 입력받아 그 합집합의 넓이를 구하는 프로그램을 작성해주세요.
입력
입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.
각 테스트 케이스에 대해, 첫 번째줄에 정수 N (1 \leq N \leq 3,000) 이 주어진다. 이는 주어지는 원의 개수이다.
그리고 다음 N줄에는 각 원의 중심의 좌표와 반지름을 나타내는 정수 X Y R이 공백으로 구분되어 순서대로 주어진다. (-10,000 \leq X, Y \leq 10,000, 1 \leq R \leq 10,000)
출력
각 테스트 케이스마다 한 줄에 하나씩 답 출력한다. 절대/상대 오차가 1e-8이하인 답은 정답으로 인정한다.
예제 입력
3 2 0 0 1 1 0 1 2 0 0 1 1 1 1 3 0 0 3 1 1 2 2 2 1
예제 출력
5.0548156086 5.7123889804 29.8989831391
노트
