화성인의 장난

화성인들은 장난을 좋아한다. 낯선 탐사 로버가 과학 연구를 위해 자기네 행성 사진을 찍는다는 사실을 알게 된 화성인들은, 사진과 사진 사이에 돌을 옮겨 지구의 과학자들을 헷갈리게 하기로 했다. 로버가 같은 지점을 $t$초 간격으로 두 번 찍을 때마다 일부 돌의 위치가 바뀌어 있다.

무대는 단위 정사각형 $[0,1]\times[0,1]$이다. 한 장의 사진은 $n$개의 돌 위치 $(x_i, y_i)$의 목록이며 모든 좌표는 $[0,1]$ 안에 있다. 두 사진에 들어 있는 돌의 개수는 같지만, 과학자들은 개별 돌을 구별할 수 없으므로 첫 번째 사진의 어떤 돌이든 두 번째 사진의 어떤 돌과도 대응될 수 있다.

정사각형 바로 바깥에는 사실상 무한히 많은 화성인이 대기하고 있으며, 모든 화성인은 같은 속도 $v$(초당 단위 길이)로 달린다. 돌 하나를 옮길 때, 그 돌에 가장 가까운 화성인이 속도 $v$로 돌까지 곧장 달려가고(달려 들어가는 거리는 돌에서 정사각형의 가장 가까운 변까지의 거리이다), 새 위치까지 속도 $v/2$로 밀며(돌이 무겁다), 그런 다음 새 위치에서 가장 가까운 변까지의 최단 경로로 속도 $v$로 사진 밖으로 빠져나간다. 옮기지 않는 돌에는 화성인이 필요 없고 시간도 걸리지 않는다.

각 돌은 서로 다른 화성인이 담당하므로 모든 이동은 동시에(병렬로) 일어나며, 따라서 전체 재배치는 가장 오래 걸리는 한 번의 이동이 끝나는 순간에 완료된다. 화성인들은 첫 번째 사진의 어떤 돌을 두 번째 사진의 어떤 돌로 만들지 자유롭게 정할 수 있다. 이 규칙을 따르면서 모든 이동을 $t$초 안에 끝낼 수 있는 가장 작은 속도 $v$를 구하라.

점 $P=(x,y)$에서 정사각형의 가장 가까운 변까지의 거리를 $d(P)=\min(x,\,1-x,\,y,\,1-y)$라 하자. 돌을 $A$에서 다른 위치 $B$로 옮기는 데 걸리는 시간은 $\big(d(A)+2\,|AB|+d(B)\big)/v$이고, 돌을 제자리에 두면 걸리는 시간은 $0$이다. 어떤 대응을 골랐을 때 가능한 가장 작은 속도는 (가장 큰 이동 비용)을 $t$로 나눈 값이며, 정답은 이 값을 모든 대응에 대해 최소화한 것이다.

첫 번째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 주어진다.

각 데이터 집합의 첫 줄에는 정수 $n$과 실수 $t$가 주어진다. 이어지는 $2n$개의 줄에는 각각 두 실수 $x$와 $y$가 주어지는데, 처음 $n$개의 줄은 첫 번째 사진의 돌 위치이고 다음 $n$개의 줄은 두 번째 사진의 돌 위치이다. 돌은 임의의 순서로 나열되며(구별할 수 없다), 여러 돌이 같은 위치에 있을 수도 있다.

제약: $0 \le n \le 100$, $t \ge 1.0$, $0 \le x, y \le 1$.

각 데이터 집합에 대해 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 $1$부터 시작하는 데이터 집합의 번호이다. 다음 줄에는 가장 작은 속도 $v$를 소수점 아래 둘째 자리까지 반올림하여 출력한다. 연속한 데이터 집합 사이에는 빈 줄을 하나 출력한다.