일조량 (Small)

결혼을 앞둔 A씨는 집을 살 돈은 넉넉하지만 해가 충분히 드는 집을 고르기가 어렵다. 도시에 건물이 많아서 낮 동안 다른 건물에 가려지는 집이 많기 때문이다. 도시의 집 가운데 A씨의 조건을 만족하는 집이 얼마나 되는지 구해 보자.

해는 아침 6시에 $(-R, 0)$에서 떠서 반지름이 $R$인 반원 경로를 일정한 속도로 지나고, 12시간 뒤인 저녁 6시에 $(R, 0)$으로 진다. 반원의 중심은 지면 위의 원점 $(0, 0)$이다.

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

도시에는 건물이 $N$개 있다. $i$번 건물은 $(X_i, 0)$에서 $(X_i, Y_i)$까지 이어지는 수직 선분이며 두께는 0이다. 같은 좌표에 건물이 두 채 이상 서 있는 경우는 없다.

건물마다 같은 형태의 집이 무한히 많고, 한 건물 안에서 두 집이 같은 높이에 있는 경우는 없다. 집은 바닥부터 꼭대기까지 높이 방향으로 고르게 놓여 있고, 단위 높이당 집의 개수는 모든 건물에서 같다. 그래서 어떤 조건을 만족하는 집의 비율은 그 조건을 만족하는 높이 구간의 길이를 모든 건물의 높이 합 $Y_1 + Y_2 + \cdots + Y_N$으로 나눈 값이다.

$i$번 건물에서 높이가 $h$인 집은 점 $(X_i, h)$이고 $0 \le h \le Y_i$이다. 이 집과 해를 잇는 선분이 다른 건물에 막히지 않는 순간에 집에 해가 든다. 즉 $j \ne i$인 건물마다, 그 선분이 직선 $x = X_j$를 지난다면 지나는 지점의 높이가 $Y_j$보다 커야 한다. 자기 건물은 두께가 0이라서 해를 가리지 않는다.

하루에 해가 드는 시간이 $H$시간 이상인 집의 비율을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 다음 형식으로 주어진다.

N R H
X1 Y1
...
XN YN

첫 줄의 $N$은 건물의 수, $R$은 해가 지나는 반원의 반지름, $H$는 A씨가 원하는 최소 일조 시간이다. 이어지는 $N$개의 줄에는 건물의 좌표 $X_i$와 높이 $Y_i$가 주어진다. 좌표는 반원의 중심을 원점으로 삼아 잰 값이다.

제한

• $1 \le T \le 100$
• $1 \le N \le 5$
• $100 \le R \le 1000$
• $1 \le H \le 12$
• $Y_i > 0$
• $X_i^2 + Y_i^2 < R^2$
• 한 테스트 케이스 안에서 $X_i$는 서로 다르다.
• 입력의 모든 수는 정수이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 하루에 $H$시간 이상 해가 드는 집의 비율이다. $y$는 소수점 아래 일곱째 자리까지 반올림해서 일곱 자리를 모두 채워 출력한다.