Martian Pranks

Martians love pranks. When they realized that a strange new rover was taking pictures of their planet for scientific study, they decided to confuse the scientists on Earth by rearranging rocks between shots. Whenever the rover photographs the same spot twice, $t$ seconds apart, some rocks have moved.

The scene is the unit square $[0,1]\times[0,1]$. A picture is a list of $n$ rock positions $(x_i, y_i)$ with every coordinate in $[0,1]$. Both pictures contain the same number of rocks, but the scientists cannot tell individual rocks apart, so any rock in the first picture may correspond to any rock in the second picture.

An effectively unlimited number of Martians wait just outside the square, and every Martian runs at the same speed $v$ (units per second). To move one rock, the Martian nearest to it runs straight to the rock at speed $v$ (the run-in distance is the distance from the rock to the nearest edge of the square), pushes it to its new position at speed $v/2$ (the rock is heavy), and then leaves the picture at speed $v$ by the shortest route (the distance from the new position to the nearest edge). A rock that is not moved needs no Martian and takes no time.

Because each rock is handled by a different Martian, all moves happen in parallel, so the rearrangement finishes as soon as the slowest single move finishes. The Martians may freely choose which first-picture rock becomes which second-picture rock. Find the smallest speed $v$ for which they can follow this protocol and finish every move within $t$ seconds.

Let $d(P)=\min(x,,1-x,,y,,1-y)$ be the distance from a point $P=(x,y)$ to the nearest edge of the square. Moving a rock from $A$ to a different position $B$ takes time $\big(d(A)+2,|AB|+d(B)\big)/v$, while leaving a rock in place takes time $0$. For a chosen pairing the smallest feasible speed is (the largest move cost) divided by $t$; the answer is the minimum of this value over all pairings.

The first line contains the number of data sets $K$. The $K$ data sets follow.

The first line of a data set contains an integer $n$ and a real number $t$. The next $2n$ lines each contain two real numbers $x$ and $y$: the first $n$ lines are the rock positions in the first picture, and the following $n$ lines are the positions in the second picture. The rocks are listed in arbitrary order (they cannot be told apart), and several rocks may share the same position.

Constraints: $0 \le n \le 100$, $t \ge 1.0$, and $0 \le x, y \le 1$.

For each data set, print Data Set x: on its own line, where $x$ is the data set's number starting from $1$. On the next line print the smallest speed $v$, rounded to two decimal places. Print one blank line between consecutive data sets.