Sewerage Planning

ICPC City is a fast-growing city. Its population has risen so quickly that several public facilities now need to be improved, extended, or renovated. One of them is the sewerage system: a recent report says a new sewerage backbone pipeline must be built across the city. Even though modern sewerage systems are kept clean by an automated control system, residents still want the backbone pipeline placed as far from them as possible.

ICPC City is a well-planned, perfectly rectangular city whose four vertices are $(L, B)$, $(L, T)$, $(R, T)$, and $(R, B)$ for some $L < R$ and $B < T$. The backbone pipeline must be a straight line that crosses the city, because it connects the neighboring regions on the two sides. We want the pipeline to lie as far as possible from everyone in the city. The population is given as a set of $N$ points $P_i = (X_i, Y_i)$ with $L \le X_i \le R$ and $B \le Y_i \le T$.

For any line $l$ that passes through the city area, define the objective function

$\delta(l) = \min_{i = 1, \dots, N} d(P_i, l),$

where $d(P_i, l)$ is the Euclidean (perpendicular) distance from point $P_i$ to line $l$. In other words, $\delta(l)$ is the smallest of the distances from all $P_i$ to line $l$.

Figure 1. Computing $\delta(l)$ for a given line $l$ through the city area.

An optimal backbone plan is a line $l^*$ that maximizes $\delta(l)$ over all lines $l$ that intersect the rectangle with vertices $(L, B)$, $(L, T)$, $(R, T)$, and $(R, B)$. Figure 2 shows three basic cases of an optimal plan $l^*$.

Figure 2. Three basic examples.

Write a program that, given $L$, $R$, $B$, $T$, and the $N$ points $P_i$, finds the value $\delta(l^*)$ for an optimal backbone plan $l^*$.

The input is read from standard input. The first line contains the number of test cases $K$ $(1 \le K \le 20)$. Each test case is given as follows.

The first line of a test case contains four real numbers $L$, $R$, $B$, $T$ $(-1000 \le L < R \le 1000;\ -1000 \le B < T \le 1000)$ that define the city area. The next line contains one integer $N$ $(1 \le N \le 500)$, the number of points. Each of the following $N$ lines contains two real numbers $X_i$ and $Y_i$, the $X$-coordinate and $Y$-coordinate of point $P_i$, with $L \le X_i \le R$ and $B \le Y_i \le T$.

Every real number is given with exactly three digits after the decimal point, and two numbers on the same line are separated by a single space.

The output is written to standard output. For each test case, print exactly one line containing the value $\delta(l^*)$ for an optimal backbone plan $l^*$. Print the value rounded to exactly three digits after the decimal point.