일조량 (Large)

곧 결혼하는 A씨는 집을 살 돈은 넉넉하지만 고민이 하나 있다. 해가 충분히 오래 드는 집에서 살고 싶기 때문이다. 해는 아침 6시에 동쪽에서 떠서 반원을 그리며 움직이다가 12시간 뒤에 서쪽으로 진다. 도시에는 건물이 빽빽해서, 하루 중 일부 시간은 다른 건물에 가려 해가 들지 않는 집이 많다. A씨가 원하는 집이 도시에 얼마나 있는지 구하자.

그림에서 빨간색은 건물이고, 파란색은 가운데 건물의 가장 아래에 있는 집에 해가 드는 시간 구간이다.

도시는 2차원 평면이고 지면은 x축이다. 해는 크기가 없는 점이며, 원점을 중심으로 하는 반지름 $R$의 반원 경로를 일정한 속도로 지난다. 동쪽 끝인 $(R, 0)$에서 6시에 떠서 서쪽 끝인 $(-R, 0)$으로 18시에 진다. 건물 $i$는 $(X_i, 0)$에서 $(X_i, Y_i)$까지 이어지는 폭 0의 수직 선분이다. 같은 위치에 건물이 두 채 이상 서 있는 경우는 없다.

건물 $i$에는 높이 $0$부터 $Y_i$까지 무한히 많은 집이 높이에 따라 고르게 놓여 있고, 한 건물 안에서 같은 높이에 있는 집은 없다. 높이 $y$에 있는 집이 어느 순간 해를 보는 조건은, 집의 위치 $(X_i, y)$와 그 순간 해의 위치를 잇는 선분이 다른 건물과 만나지 않는 것이다. 집이 속한 건물은 그 집의 해를 가리지 않는다. 집의 일조시간은 12시간 중 해를 보는 시간을 모두 더한 값이다.

일조시간이 $H$시간 이상인 집의 비율을 구하라. 집이 높이에 고르게 분포하므로, 이 비율은 조건을 만족하는 높이 구간의 길이를 모두 더한 값을 모든 건물의 높이의 합으로 나눈 값과 같다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

N R H
X0 Y0
...
XN-1 YN-1

첫 줄에 건물의 수 $N$, 해가 지나는 반원의 반지름 $R$, A씨가 생각하는 최소 일조시간 $H$가 정수로 주어진다. 이어지는 $N$개의 줄에는 건물마다 정수 두 개가 주어진다. $X_i$는 반원의 중심을 기준으로 한 건물의 x좌표이고, $Y_i$는 건물의 높이이다.

제한

• $1 \le T \le 100$
• $1 \le N \le 200$
• $100 \le R \le 1000$
• $1 \le H \le 12$
• $Y_i > 0$
• $X_i^2 + Y_i^2 < R^2$
• $i \ne j$이면 $X_i \ne X_j$
• 입력의 모든 수는 정수이다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조건을 만족하는 집의 비율이다. $y$는 소수점 아래 일곱째 자리까지 반올림해서 출력한다.