재계산

당신은 Driverless Direct Delivery Drone Directions Design Division of Apricot Rules LLC에서 일하고 있다. 회사는 최초의 드론 "Principia"을 시장에 출시하려 한다. Principia가 주 위치 확인 시스템(예: GPS)에 접근할 수 없게 되었지만 여전히 길을 찾을 방법이 필요한 경우에 대비하여, Principia의 백업 시스템을 설계하는 임무를 맡았다. Principia는 평평한 영역에서 사용하도록 설계되었다. 형식적으로 이 영역은 좌표의 단위가 미터인 데카르트 평면이다. 이 평면 위의 하나 이상의 점에 드론 수리 센터가 있다. 어떤 두 드론 수리 센터도 같은 위치에 있지 않다.

Principia에는 자신의 위치에서 최대 D미터의 $L_{1}$ 거리(맨해튼 거리라고도 한다) 이내에 있는 드론 수리 센터들의 상대적 위치를 알아낼 수 있는 시스템이 있다. 알아낸 정보는 Principia의 현재 위치를 기준으로 한 수리 센터 위치들의 집합이다. 예: "북쪽으로 4미터, 서쪽으로 3.5미터 떨어진 곳에 수리 센터 하나가 있고, 동쪽으로 2.5미터 떨어진 곳에 또 하나가 있다". 이 정보는 수리 센터를 식별하지 않고, Principia를 기준으로 한 수리 센터의 위치를 제공한다는 점에 유의하라.

당신은 이 정보만으로는 Principia가 현재 위치를 유일하게 결정할 수 없는 점들이 지도에 있을 수 있음을 곧 깨달았다. 서로 다른 둘 이상의 점에서 정보가 똑같이 보일 수 있기 때문이다. 이러한 성질을 가진 점을 구별 불가능한 점이라 하고, 그 밖의 모든 점을 구별 가능한 점이라 한다.

형식적으로 Principia가 점 (x, y)에 있을 때 알아내는 정보 Info(x, y)는 (z, w)가 수리 센터의 위치이고 |z - x| + |w - y| ≤ D인 모든 점 (z - x, w - y)의 집합 :=이다. 여기서 |z - x|와 |w - y|는 각각 z - x와 w - y의 절댓값을 나타낸다. 점 ($x_{1}$, $y_{1}$)이 구별 불가능한 것은 Info($x_{1}$, $y_{1}$) = Info($x_{2}$, $y_{2}$)를 만족하는 다른 점 ($x_{2}$, $y_{2}$)이 존재할 때, 그리고 그럴 때에만이다.

예를 들어 D=4이고 점 (0, 0)와 (5, 0)에 수리 센터가 있다고 하자. Info(0, 0)={(0, 0)}=Info(5, 0)이므로 점 (0, 0)은 구별 불가능하다. 이는 점 (5, 0)도 구별 불가능하다는 뜻이다. 반면 Info(3.5, 0.1)={(-3.5, -0.1), (1.5, -0.1)}는 다른 어떤 점에서 얻는 정보와도 같지 않으므로, 점 (3.5, 0.1)은 구별 가능하다. 다음 그림은 구별 가능한 점들의 영역(빨간색)과 구별 불가능한 점들의 영역(파란색)을 보여 준다.

Principia는 적어도 하나의 수리 센터에서 D미터 이내에 있는 모든 점의 집합에서 균등하고 무작위로 선택된 점에 배치된다. 이때 거리는 $L_{1}$ 거리를 사용한다. 즉, 이 집합은 Info(x, y)가 공집합이 아닌 모든 점 (x, y)의 집합이다. 이렇게 선택한 점이 주어진 연속적인 점들의 집합 S에 속할 확률은 S의 넓이를 제곱미터로 나타낸 값에 비례한다. 위 예에서 각 빨간색 정사각형의 넓이는 4.5제곱미터이고, 각 파란색 구역의 넓이는 23제곱미터이다. 따라서 Principia가 각 빨간색 정사각형 안에 배치될 확률은 4.5/(3×4.5 + 2×23)이고, 각 파란색 구역 안에 배치될 확률은 23/(3×4.5 + 2×23)이다. 서로 인접하고 색이 다른 구역 사이의 경계는 넓이가 0이므로, Principia가 정확히 경계 위에 배치될 확률은 정확히 0이다.

모든 수리 센터의 위치가 주어질 때, Principia가 배치되는 점이 구별 가능할 확률은 얼마인가?

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ D ≤ $10^{7}$. 모든 i에 대해 -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$. 모든 i에 대해 -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$. 모든 i ≠ j에 대해 ($X_{i}$, $Y_{i}$) ≠ ($X_{j}$, $Y_{j}$). (어떤 두 수리 센터도 같은 위치를 공유하지 않는다.)

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. N = 2.

테스트 세트 2 (Visible Verdict)

시간 제한: 60초. 2 ≤ N ≤ 10.

테스트 세트 3 (Visible Verdict)

시간 제한: 120초. 6개의 경우에는 N = 1687. T-6개의 경우에는 2 ≤ N ≤ 100.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 D가 포함된 줄로 시작하며, 이들은 각각 수리 센터의 수와 위에서 설명한 대로 Principia가 수리 센터의 정보를 알아낼 수 있는 최대 $L_{1}$ 거리를 나타낸다. 이어서 N개의 줄이 주어진다. 이 중 i번째 줄에는 i번째 수리 센터의 좌표를 나타내는 두 정수 $X_{i}$와 $Y_{i}$가 주어진다. 모든 좌표와 D의 측정 단위는 미터이다.

각 테스트 케이스마다 Case #x: y z를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(번호는 1부터 시작한다), y와 z는 음이 아닌 정수이다. 분수 y/z는 적어도 하나의 수리 센터에서 D미터 이내에 있는 모든 위치 중 하나를 균등하고 무작위로 선택했을 때, Principia가 구별 가능한 위치에 있을 확률을 나타내야 한다. 이때 거리는 $L_{1}$ 거리를 사용한다. y와 z에 허용되는 값이 여러 개라면, z가 최소인 것을 선택한다.

위의 케이스들은 테스트 세트 1의 제한을 만족한다. 이 제한을 만족하지 않는 또 다른 예제 케이스는 이 절의 끝에 있다.

예제 케이스 #1은 문제 설명에 묘사되어 있으며 그림으로도 제시되어 있다.

가운데 빨간색 영역의 점들은 두 수리 센터 모두에서 정보를 알아내는 유일한 점들이고, 그 영역의 각 점은 서로 다른 정보의 집합을 알아내므로 모두 구별 가능한 점이다.

왼쪽과 오른쪽의 빨간색 영역에 있는 각 점은 하나의 수리 센터에서만 정보를 받지만, 그 정보는 항상 유일하므로 모두 구별 가능한 점이다. 예를 들어 Principia가 자신이 어느 수리 센터에서 동쪽으로 3미터 떨어져 있음을 안다면, (0, 0)에 있는 수리 센터에서 동쪽으로 3미터 떨어져 있는 것은 아니라고 확신할 수 있다. 그랬다면 두 수리 센터 모두에서 정보를 알아냈을 것이기 때문이다. 따라서 (5, 0)에 있는 수리 센터에서 동쪽으로 3미터 떨어져 있어야 한다.

파란색 영역의 점들은 모두 구별 불가능한 점이다. 그 영역들 중 하나에서 아무 점이나 선택하고, Principia가 그 점에서 얻을 정보를 생각해 보자. 이 정보에는 범위 안에 있는 하나의 수리 센터만 포함된다. 하지만 다른 파란색 영역에는 Principia가 정확히 같은 정보를 얻는 대응하는 점이 있다.

위에서 설명했듯이 Principia가 빨간색 구역 중 하나에 배치될 확률은 4.5/59.5이므로, 그중 어느 곳에든 배치될 전체 확률은 3×4.5/59.5 = 27/119이다.

다음 그림은 예제 케이스 #2를 보여 준다. 둘 이상의 수리 센터에서 정보를 알아낼 방법이 없으므로, 그중 하나에 충분히 가까운 모든 점은 구별 불가능하다. 다른 수리 센터 근처의 대응하는 점에서 같은 정보를 알아내기 때문이다. z(분모)는 최소여야 하므로, 0 1만이 허용되는 답임을 기억하라.

다음 그림은 예제 케이스 #3를 보여 준다. 두 파란색 정사각형 사이의 경계는 구별 가능한 점들로 이루어져 있음에 유의하라. 하지만 그 넓이가 0이므로 Principia가 그곳에 배치될 확률은 0이다. Principia가 배치될 수 있는 나머지 모든 점은 구별 불가능하다.

다음 그림은 예제 케이스 #4를 보여 준다.

다음 그림은 추가 케이스를 보여 준다.

다음 추가 케이스는 테스트 세트 1에는 나올 수 없지만, 다른 테스트 세트에는 어디에든 나올 수 있다.

올바른 출력은 Case #1: 101 109이다.