복도 청소

사람 $N$명이 진공청소기 $N$대로 바닥을 청소한다. 바닥 전체를 청소할 수 있을 것 같지만 그렇지 않다. 청소기는 바닥에 있는 콘센트에 연결해야 돌아가고, 전선 길이도 정해져 있다.

어떤 청소기의 전선 길이가 $D$라면, 그 청소기를 쓰는 사람은 콘센트에서 최대 $D$까지 떨어질 수 있다. 그런데 전선에 결함이 있어서 전선이 조금이라도 느슨해지면, 즉 사람과 콘센트의 거리가 $D$보다 가까워지면 전원이 끊긴다. 그래서 사람은 콘센트에서 거리가 정확히 $D$인 곳에만 서 있을 수 있다. 손잡이도 무거워서 청소기 헤드를 자기 위치에서 $d$보다 멀리 밀어낼 수 없다.

정리하면 청소기 한 대는, 콘센트에서 거리가 정확히 $D$인 곳에 선 사람으로부터 거리가 $d$ 이하인 바닥을 모두 청소한다.

청소기마다 $D$와 $d$, 그리고 연결된 콘센트의 좌표가 주어진다. 이렇게 배치했을 때 청소할 수 있는 바닥의 면적을 구하시오. 한 곳을 여러 사람이 청소할 수도 있으므로, 각자 청소한 면적을 더한 값이 아니라 합집합의 면적을 구해야 한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 30$)

각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 청소기의 개수 $N$이 주어진다. ($1 \le N \le 500$)
• 이어지는 $N$개 줄에 청소기 한 대를 나타내는 정수 네 개 $x$, $y$, $D$, $d$가 공백 하나로 구분되어 주어진다. $(x, y)$는 콘센트의 좌표, $D$는 전선 길이, $d$는 사람과 청소기 헤드 사이의 거리다. ($|x|, |y| \le 1000$, $0 < D, d \le 200$)

각 테스트 케이스마다 Case x: A 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $A$는 청소할 수 있는 면적을 소수점 아래 둘째 자리까지 반올림한 값이다.

정확한 면적과 $0.005 + 0.01k$ ($k$는 정수) 꼴인 값의 차이는 항상 $10^{-5}$보다 크므로, 반올림한 값은 하나로 정해진다.

첫 번째 테스트 케이스에는 청소기가 한 대뿐이다. 콘센트가 $(0, 0)$에 있고 $D = 10$, $d = 1$이므로 사람은 $(0, 0)$을 중심으로 하는 반지름 10인 원 위를 돌아다닌다. 청소기는 사람으로부터 거리 1 이하인 곳을 청소하니, 청소되는 영역은 중심이 $(0, 0)$이고 반지름이 9와 11인 두 원 사이의 고리다. 면적은 $\pi \times (11^2 - 9^2) = 125.6637\ldots$이고, 출력은 125.66이다.

두 번째 테스트 케이스에는 청소기가 두 대 있다. 첫 번째 청소기는 $(0, 0)$의 콘센트에 연결되어 반지름 6과 8 사이의 고리를 청소하고, 두 번째 청소기는 $(13, 0)$의 콘센트에 연결되어 반지름 9와 11 사이의 고리를 청소한다. 두 고리가 겹치므로 합집합의 면적은 두 고리의 면적을 더한 값보다 작다.