Square Annulus

A square annulus is the region that lies between two concentric, axis-parallel squares: two squares that share the same center and whose sides are parallel to the $x$- and $y$-axes. Concretely, it is the set of all points that lie inside the larger square (boundary included) but outside the smaller square (boundary included). The width of a square annulus is defined as half the difference of the side lengths of its two squares.

You are given $N$ points in the plane. Find a square annulus $A$ of minimum width that contains all $N$ points, and report that minimum width.

You may use the following fact, which was established by a German research group.

Among all minimum-width square annuli that contain the $N$ points, there is one whose outer square is a smallest axis-parallel square containing the points.

Hence you may assume the outer square $S$ of $A$ has the smallest possible side length $L$ among all axis-parallel squares that contain the $N$ points; that is, no axis-parallel square with side length less than $L$ contains all of them. Several distinct squares of side length $L$ may contain the points, so the outer square is not necessarily unique.

Note that the width can be $0$ (when the two squares coincide), and the inner square may shrink to a single point of side length $0$, in which case the width equals half the side length of the outer square.

The first line contains an integer $T$, the number of test cases. The test cases follow one after another.

Each test case begins with a line containing an integer $N$ ($1 \le N \le 100{,}000$), the number of points. Each of the next $N$ lines contains two integers, the $x$- and $y$-coordinates of one point, separated by a single space. Every coordinate is an integer between $-1{,}000{,}000$ and $1{,}000{,}000$, inclusive. There are no blank lines between consecutive test cases.

For each test case, print one line containing the minimum width of an axis-parallel square annulus that contains all $N$ points of that test case. Print the value with exactly one digit after the decimal point, rounding to one decimal place if necessary.