정사각형 고리

정사각형 고리(square annulus)는 중심이 같고 변이 $x$축과 $y$축에 평행한 두 정사각형 사이에 놓인 영역이다. 즉, 큰 정사각형의 내부(경계 포함)에 있으면서 작은 정사각형의 외부(경계 포함)에 있는 모든 점의 집합이다. 정사각형 고리의 너비는 두 정사각형의 한 변 길이의 차를 절반으로 한 값으로 정의한다.

평면 위에 $N$개의 점이 주어진다. 이 $N$개의 점을 모두 포함하면서 너비가 최소인 정사각형 고리 $A$를 찾고, 그 최소 너비를 구하여라.

다음 사실을 이용할 수 있다. 이는 어느 독일 연구진이 증명한 것이다.

$N$개의 점을 포함하는 너비 최소의 정사각형 고리 가운데, 바깥쪽 정사각형이 그 점들을 포함하는 가장 작은 축평행 정사각형인 것이 반드시 존재한다.

따라서 $A$의 바깥쪽 정사각형 $S$는, $N$개의 점을 포함하는 축평행 정사각형 중에서 한 변의 길이 $L$이 최소인 것이라고 가정할 수 있다. 즉, 한 변의 길이가 $L$보다 작으면서 그 점들을 모두 포함하는 축평행 정사각형은 존재하지 않는다. 한 변의 길이가 $L$인 정사각형은 여러 개일 수 있으므로 바깥쪽 정사각형이 유일하지는 않다.

두 정사각형이 완전히 같을 때 너비는 $0$이 될 수 있고, 안쪽 정사각형이 한 변의 길이가 $0$인 한 점으로 줄어들 수도 있는데, 이때 너비는 바깥쪽 정사각형 한 변 길이의 절반과 같다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 각 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 점의 개수 $N$ ($1 \le N \le 100{,}000$)이 주어진다. 다음 $N$개의 줄에는 각각 한 점의 $x$좌표와 $y$좌표를 나타내는 두 정수가 공백 하나로 구분되어 주어진다. 모든 좌표는 $-1{,}000{,}000$ 이상 $1{,}000{,}000$ 이하의 정수이다. 연속한 두 테스트 케이스 사이에 빈 줄은 없다.

각 테스트 케이스마다, 해당 테스트 케이스의 $N$개의 점을 모두 포함하는 축평행 정사각형 고리의 최소 너비를 한 줄에 출력한다. 값은 소수점 아래 한 자리까지 출력하며, 필요하면 소수점 아래 둘째 자리에서 반올림한다.