쓰레기

Bob은 뛰어난 Googler이다. 그는 효율성을 좋아하므로 모든 일을 잘하고 빠르게 처리한다. 오늘 Bob은 자기 책상 근처의 쓰레기통이 사라졌다는 사실을 발견했다! 안타깝게도 이는 대신 근처의 다른 쓰레기통을 사용해야 한다는 뜻이다. 쓰레기통을 사용하려고 자리에서 일어나면 생산성이 떨어지므로, Bob은 그 쓰레기통을 향해 쓰레기를 던지기로 했다!

하지만 Google 사무실에는 장애물이 많다. 예를 들어, 던진 쓰레기가 사람이나 벽 또는 그 밖의 어떤 것에 부딪히면 무례한 일이다. Bob은 기존의 어떤 장애물에도 닿지 않게 쓰레기를 던지고 싶어 한다.

이 문제를 단순화하기 위해 Bob과 쓰레기통을 포함하는 수직 평면만 고려한다. Bob은 점 (0, 0)에 있고, 쓰레기통은 점 (P, 0)에 있다. 또한 사무실에는 N개의 장애물이 있으며, 각각은 하나의 점이고 i번째 장애물의 좌표는 ($X_{i}$, $Y_{i}$)이다. 사무실의 천장은 이 평면에서 식 y=H으로 표현되는 직선이다. Since Bob은 새로운 첨단 부유식 사무실 중 하나에 있으므로, 이 문제에서는 사무실 바닥을 고려하지 않으며 바닥과의 충돌을 걱정할 필요가 없다. Bob은 반지름이 R인 원 모양의 쓰레기 조각을 던진다. 쓰레기 조각의 중심은 처음에 (0, 0)에 있다. 쓰레기 조각을 던지면 그 중심은 식 f(x)=ax(x-P)으로 표현되는 포물선의 경로를 따라야 한다. 여기서 0 ≤ x ≤ P이고, a는 0 이하인 임의의 실수일 수 있다. 쓰레기 조각은 그 중심이 쓰레기통의 점에 도달해야만 버려진 것으로 간주되며, 쓰레기 조각의 일부가 그 점에 단지 닿는 것만으로는 충분하지 않다.

Bob은 천장이나 어떤 장애물에도 부딪히지 않고 던질 수 있는 가장 큰 쓰레기 조각이 무엇인지 궁금해한다. 즉, 다음 조건을 만족하는 a가 적어도 하나 존재하게 하는 R의 최댓값을 찾아야 한다. 임의의 0 ≤ x ≤ P에 대해 (x, f(x))와 (x, H) 사이의 유클리드 거리는 R보다 크고, 각 i에 대해 점 (x, f(x))와 ($X_{i}$, $Y_{i}$) 사이의 유클리드 거리는 R 이상이다.

제한

1 ≤ T ≤ 50. 시간 제한: 테스트 세트당 120초. 메모리 제한: 1GB. 2 ≤ P ≤ 1000. 2 ≤ H ≤ 1000. 0 < $X_{i}$ < P. 0 < $Y_{i}$ < H.

작은 데이터 세트 (테스트 세트 1 - 공개)

N = 1.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 10.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나가 포함된 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 장애물의 수, 쓰레기통의 x좌표, 천장의 높이를 각각 나타내는 세 정수 N, P, H가 주어진다. 그다음 N개의 줄이 더 주어진다. 그중 i번째 줄은 i번째 장애물을 나타내며, 해당 장애물의 좌표를 나타내는 두 정수 $X_{i}$와 $Y_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 최대 반지름 R을 나타내는 배정밀도 부동소수점 수이다. 답이 정답과의 절대 오차 또는 상대 오차가 10^{-4} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.

마지막 예제 케이스는 작은 데이터 세트에 등장하지 않는다는 점에 유의한다.

다음 그림은 예제 케이스 #1을 보여 준다. Bob은 (0, 0)에 있고, 쓰레기통은 (10, 0)에 있다. 별표로 표시된 장애물이 점 (5, 3)에 있다. Bob이 장애물 위로 쓰레기를 던지면 최대 R은 3.2387이고, 이를 위해서는 a가 약 -0.2705여야 한다. Bob이 장애물 아래로 쓰레기를 던지면 최대 R은 3이고, 이를 위해서는 a가 0여야 한다. 따라서 이 케이스에서 최대 R은 약 3.2387이다.

예제 케이스 #2은 예제 케이스 #1과 비슷하지만, 장애물이 한 단위 더 높다. 이제 Bob이 장애물 아래로 쓰레기를 던지면 최대 R은 4이다. 이때 a = 0이다. 장애물 위로 쓰레기를 던지면 반지름이 최대 약 2.8306인 쓰레기만 사용할 수 있다. 이때 a = -0.4이다. 따라서 이 케이스에서 최대 R은 4이다.