Chef bought a huge (effectively infinite) planar island and built $N$ restaurants (numbered $1$ through $N$) on it. For each valid $i$, the Cartesian coordinates of restaurant $i$ are $(X_i, Y_i)$.
Now, Chef wants to build $N-1$ straight narrow roads (line segments) on the island. The roads may have arbitrary lengths; restaurants do not have to lie on the roads. The slope of each road must be $1$ or $-1$, i.e. for any two points $(x_1, y_1)$ and $(x_2, y_2)$ on the same road, $|x_1-x_2| = |y_1-y_2|$ must hold.
Let's denote the minimum distance Chef has to walk from restaurant $i$ to reach a road by $D_i$. Then, let's denote $a = \mathrm{max}\,(D_1, D_2, \ldots, D_N)$; Chef wants this distance to be minimum possible.
Chef is a busy person, so he decided to give you the job of building the roads. You should find a way to build them that minimises $a$ and compute $a \cdot \sqrt{2}$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_i$ and $Y_i$.

-----Output-----
For each test case, print a single line containing one real number — the minimum distance $a$ multiplied by $\sqrt{2}$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 10^4$
- $|X_i|, |Y_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (10 points):
- $1 \le T \le 10$
- $2 \le N \le 5$
- $|X_i|, |Y_i| \le 10$ for each valid $i$
- $a \cdot \sqrt{2}$ is an integer
Subtask #2 (90 points): original constraints

-----Example Input-----
2
3
0 0
0 1
0 -1
3
0 1
1 0
-1 0

-----Example Output-----
0.5
0

-----Explanation-----
Example case 1: We should build roads described by equations $y-x+0.5 = 0$ and $y-x-0.5 = 0$.
Example case 2: We should build roads described by equations $y-x-1 = 0$ and $y+x-1 = 0$.

Difficulty: MEDIUM_HARD
Tags: Geometry

Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	n = int(input())
	X = []
	Y = []
	xy = []
	yx = []
	for j in range(0, n):
		(x, y) = map(int, input().split())
		xy.append(y - x)
		yx.append(x + y)
	xy = sorted(xy)
	yx = sorted(yx)
	diff1 = 10 ** 20
	diff2 = 10 ** 20
	for k in range(n - 1):
		if xy[k + 1] - xy[k] < diff1:
			diff1 = abs(xy[k + 1] - xy[k])
		if yx[k + 1] - yx[k] < diff2:
			diff2 = abs(yx[k + 1] - yx[k])
	print(abs(min(diff1, diff2)) / 2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	d = []
	dl = []
	for i in range(n):
		(x, y) = map(int, input().split())
		d.append(y - x)
		dl.append(y + x)
	d = sorted(d)
	dl = sorted(dl)
	ans = abs(d[0] - d[1])
	k = 0
	while k < n - 1:
		ans = min(ans, abs(d[k] - d[k + 1]))
		ans = min(ans, abs(dl[k] - dl[k + 1]))
		k += 1
	if ans % 2 == 0:
		print(int(ans / 2))
	else:
		print(ans / 2)


T = int(input())
for i in range(0, T):
	N = int(input())
	L = []
	for j in range(0, N):
		(x, y) = map(int, input().split())
		L.append((x, y))
	arr11 = []
	arr12 = []
	for j in range(0, len(L)):
		arr11.append(L[j][1] - L[j][0])
		arr12.append(L[j][1] + L[j][0])
	arr11 = sorted(arr11)
	arr12 = sorted(arr12)
	arr11 = arr11[::-1]
	arr12 = arr12[::-1]
	arr21 = [100000000000]
	arr22 = [100000000000]
	for j in range(0, len(L) - 1):
		arr21.append(arr11[j] - arr11[j + 1])
		arr21.append(arr12[j] - arr12[j + 1])
	print(min(min(arr21), min(arr22)) / 2)


t = int(input())
for test in range(1, t + 1):
	arrx = []
	arry = []
	n = int(input())
	res = 0.0
	for i in range(n):
		temp = input()
		temp2 = temp.split()
		temp2[0] = float(temp2[0])
		temp2[1] = float(temp2[1])
		arrx.append(temp2)
		arry.append(temp2)
	arrx.sort(key=lambda x: x[1] - x[0])
	arry.sort(key=lambda x: x[1] + x[0])
	for i in range(int(n - 1)):
		xmid = (arrx[i][0] + arrx[i + 1][0]) / 2
		ymid = (arrx[i][1] + arrx[i + 1][1]) / 2
		dist = abs(arrx[i][1] - arrx[i][0] - (ymid - xmid))
		if i == 0:
			res = dist
		if dist < res:
			res = dist
		dist = abs(arrx[i][1] + arrx[i][0] - (ymid + xmid))
		if dist < res:
			res = dist
		xmid = (arry[i][0] + arry[i + 1][0]) / 2
		ymid = (arry[i][1] + arry[i + 1][1]) / 2
		dist = abs(arry[i][1] - arry[i][0] - (ymid - xmid))
		if dist < res:
			res = dist
		dist = abs(arry[i][1] + arry[i][0] - (ymid + xmid))
		if dist < res:
			res = dist
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	pos = []
	neg = []
	for i in range(n):
		(x, y) = map(int, input().split(' '))
		pos.append(y - x)
		neg.append(y + x)
	pos = sorted(pos)
	neg = sorted(neg)
	pdiff = []
	for p in range(len(pos) - 1):
		k = abs(pos[p] - pos[p + 1])
		pdiff.append(k)
	for q in range(len(neg) - 1):
		l = abs(neg[q] - neg[q + 1])
		pdiff.append(l)
	ii = min(pdiff) / 2
	print(ii)


for i in range(int(input())):
	n = int(input())
	plus = []
	mins = []
	for i in range(n):
		(x, y) = map(int, input().split())
		plus.append(x + y)
		mins.append(x - y)
	plus.sort()
	mins.sort()
	pdi = []
	mdi = []
	for j in range(1, n):
		pdi.append(plus[j] - plus[j - 1])
		mdi.append(mins[j] - mins[j - 1])
	pdi.sort()
	mdi.sort()
	print(min(pdi[0], mdi[0]) / 2)


def mini(n, c1, c2):
	d = c1[1] - c1[0]
	for i in range(0, n - 1):
		d = min(c1[i + 1] - c1[i], d)
		d = min(c2[i + 1] - c2[i], d)
		i += 1
		if d == 0:
			return 0
	return d
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	i = 0
	c1 = []
	c2 = []
	while i < n:
		(x, y) = input().split()
		c1.append(float(x) - float(y))
		c2.append(float(x) + float(y))
		i += 1
	c1.sort()
	c2.sort()
	print('{0:.7f}'.format(mini(n, c1, c2) / 2))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	islp = []
	slp = []
	for i in range(n):
		(x, y) = map(int, stdin.readline().split())
		slp.append(y - x)
		islp.append(x + y)
	if len(set(slp)) < n or len(set(islp)) < n:
		print(0)
	else:
		islp = sorted(islp)
		slp = sorted(slp)
		ians = [abs(islp[0] - islp[1])]
		ans = [abs(slp[0] - slp[1])]
		for i in range(1, n - 1):
			ians.append(min(abs(islp[i - 1] - islp[i]), abs(islp[i] - islp[i + 1])))
			ans.append(min(abs(slp[i - 1] - slp[i]), abs(slp[i] - slp[i + 1])))
		print(min(min(ians) / 2, min(ans) / 2))


t = int(input())
root = 2 ** 0.5
for i in range(t):
	n = int(input())
	x = []
	y = []
	for j in range(n):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		r = a * 0.5 ** 0.5 + b * 0.5 ** 0.5
		s = -a * 0.5 ** 0.5 + b * 0.5 ** 0.5
		x.append(r)
		y.append(s)
	x.sort()
	y.sort()
	min_x = 10 ** 12
	min_y = 10 ** 12
	for i in range(n):
		if i == n - 1:
			break
		else:
			g = abs(x[i] - x[i + 1])
			h = abs(y[i] - y[i + 1])
			if g < min_x:
				min_x = g
			if h < min_y:
				min_y = h
	print(min(min_x, min_y) * 0.5 * root)


from math import cos, sin, pi, sqrt
t = int(input())
for test in range(1, t + 1):
	n = int(input())
	points = []
	for i in range(1, n + 1):
		(x_, y_) = map(int, input().split())
		points.append((x_, y_))
	rotatedx = []
	rotatedy = []
	for i in range(0, n):
		rx = points[i][1] * cos(pi / 4) - points[i][0] * sin(pi / 4)
		ry = points[i][1] * sin(pi / 4) + points[i][0] * cos(pi / 4)
		rotatedx.append(rx)
		rotatedy.append(ry)
	rotatedx.sort()
	rotatedy.sort()
	mindneg = float('inf')
	mindpos = float('inf')
	for i in range(0, n - 1):
		if mindpos > abs(rotatedy[i + 1] - rotatedy[i]):
			mindpos = rotatedy[i + 1] - rotatedy[i]
		if mindneg > abs(rotatedx[i + 1] - rotatedx[i]):
			mindneg = rotatedx[i + 1] - rotatedx[i]
	print(min(mindpos * sqrt(2) / 2, mindneg * sqrt(2) / 2))


import math
import numpy as np
T = int(input())
results = np.array([])
for _ in range(T):
	N = int(input())
	(X, Y) = (np.zeros(N), np.zeros(N))
	for i in range(N):
		(x, y) = (float(x) for x in input().split())
		(X[i], Y[i]) = (x, y)
	(c, s) = (math.cos(math.pi / 4), math.sin(math.pi / 4))
	(x, y) = (X * c - Y * s, Y * c + X * s)
	if np.unique(x).size != len(x) or np.unique(y).size != len(y):
		results = np.append(results, 0)
	else:
		(x_sorted, y_sorted) = (sorted(x), sorted(y))
		(x_shifted, y_shifted) = (np.roll(x_sorted, -1), np.roll(y_sorted, -1))
		(x_delta, y_delta) = (np.absolute(np.subtract(x_sorted, x_shifted)), np.absolute(np.subtract(y_sorted, y_shifted)))
		(x_min, y_min) = (np.min(x_delta), np.min(y_delta))
		results = np.append(results, x_min * math.sqrt(2) / 2 if x_min < y_min else y_min * math.sqrt(2) / 2)
for i in range(T):
	print(results[i])


import bisect

def sign(a):
	if a == abs(a):
		return 1
	else:
		return -1

def insert(list, n):
	bisect.insort(list, n)
	return list
t = int(input())
for i in range(0, t):
	n = int(input())
	arr = []
	brr = []
	for j in range(0, n):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		a = x - y
		b = x + y
		insert(arr, a)
		insert(brr, b)
	m1 = arr[1] - arr[0]
	for k in range(1, len(arr) - 1):
		if arr[k + 1] - arr[k] < m1:
			m1 = arr[k + 1] - arr[k]
	m2 = brr[1] - brr[0]
	for k in range(1, len(arr) - 1):
		if brr[k + 1] - brr[k] < m2:
			m2 = brr[k + 1] - brr[k]
	print(min(m1, m2) / 2)


import sys
mod = 1000000007
get_arr = lambda : list(map(float, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()
from math import sqrt

def base(points):
	p = {}
	s = {}
	for i in points:
		if i[0] + i[1] in p:
			p[i[0] + i[1]] += 1
		else:
			p[i[0] + i[1]] = 1
	for i in points:
		if i[0] - i[1] in s:
			s[i[0] - i[1]] += 1
		else:
			s[i[0] - i[1]] = 1
	for i in p:
		if p[i] > 1:
			return True
	for i in s:
		if s[i] > 1:
			return True
	return False

def rotate_points(points):
	for i in range(len(points)):
		(x, y) = (points[i][0], points[i][1])
		points[i][0] = (x - y) / sqrt(2)
		points[i][1] = (x + y) / sqrt(2)
for _ in range(get_int()):
	n = get_int()
	points = [get_arr() for i in range(n)]
	if base(points):
		print(0)
	else:
		rotate_points(points)
		sort_x = sorted(points)
		sort_y = sorted(points, key=lambda x: x[1])
		ans = sys.maxsize
		for i in range(1, n):
			ans = min(ans, (sort_x[i][0] - sort_x[i - 1][0]) / 2, (sort_y[i][1] - sort_y[i - 1][1]) / 2)
		print('%.6f' % (ans * sqrt(2)))


res = []

def getMin(nums):
	nums.sort()
	diff = 1000000000
	for i in range(len(nums) - 1):
		diff = min(abs(nums[i + 1] - nums[i]), diff)
	return diff
x = int(input())
for _ in range(x):
	slope1Dist = {}
	slope2Dist = {}
	dist1 = []
	dist2 = []
	zero = False
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().strip().split(' '))
		if y - x not in slope1Dist:
			slope1Dist[y - x] = 1
			dist1.append(y - x)
		else:
			zero = True
		if y + x not in slope2Dist:
			slope2Dist[y + x] = 1
			dist2.append(y + x)
		else:
			zero = True
	if zero:
		res.append(0)
	else:
		dmin = 1000000000
		if len(dist1) > 0:
			dmin = min(dmin, getMin(dist1))
		if len(dist2) > 0:
			dmin = min(dmin, getMin(dist2))
		res.append(dmin / 2)
for xx in res:
	print(xx)


def ret(add, sub):
	add.sort()
	sub.sort()
	minadd = abs(add[0] - add[1])
	for i in range(len(add) - 1):
		temp = abs(add[i] - add[i + 1])
		if temp < minadd:
			minadd = temp
	minsub = abs(sub[0] - sub[1])
	for i in range(len(sub) - 1):
		temp = abs(sub[i] - sub[i + 1])
		if temp < minsub:
			minsub = temp
	return min(minadd / 2, minsub / 2)
testcase = int(input())
for i in range(testcase):
	points = int(input())
	add = []
	sub = []
	for j in range(points):
		a = list(map(int, input().split()))
		add.append(a[0] + a[1])
		sub.append(a[0] - a[1])
	print('%.6f' % ret(add, sub))


T = int(input())
for i in range(T):
	N = int(input())
	l1 = []
	l2 = []
	for j in range(N):
		(a, b) = map(int, input().split())
		l1.append(a - b)
		l2.append(a + b)
	l1.sort()
	l2.sort()
	m1 = 100000000000000000000000
	for j in range(1, len(l1)):
		if l1[j] - l1[j - 1] < m1:
			m1 = l1[j] - l1[j - 1]
	m2 = 1000000000000000000000
	for j in range(1, len(l2)):
		if l2[j] - l2[j - 1] < m2:
			m2 = l2[j] - l2[j - 1]
	if min(m1, m2) % 2 == 0:
		print(min(m1, m2) // 2)
	else:
		print(min(m1, m2) / 2)


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
t = iinput()
for _ in range(t):
	n = iinput()
	p = []
	mi = []
	for i in range(n):
		(x, y) = rinput()
		p.append(x + y)
		mi.append(x - y)
	p.sort()
	mi.sort()
	m = float('inf')
	for i in range(1, n):
		if p[i] - p[i - 1] < m:
			m = p[i] - p[i - 1]
		if mi[i] - mi[i - 1] < m:
			m = mi[i] - mi[i - 1]
	if m % 2 == 0:
		print(m // 2)
	else:
		print(m / 2)


import math
for _ in range(0, int(input())):
	points = int(input())
	xs = set()
	ys = set()
	for _ in range(points):
		(x, y) = [int(i) for i in input().split()]
		xs.add(x - y)
		ys.add(x + y)
	xmin = 1000000001
	ymin = 1000000001
	if len(xs) != points or len(ys) != points:
		print(0)
	else:
		xs = sorted(xs)
		ys = sorted(ys)
		xmin = math.fabs(xs[1] - xs[0])
		ymin = math.fabs(ys[1] - ys[0])
		for i in range(1, len(xs) - 1):
			if xmin > math.fabs(xs[i + 1] - xs[i]):
				xmin = xs[i + 1] - xs[i]
			if ymin > math.fabs(ys[i + 1] - ys[i]):
				ymin = ys[i + 1] - ys[i]
		print(min(xmin, ymin) / 2)


def key1(arr):
	return dis1(arr)

def key2(arr):
	return dis2(arr)

def l1(x, y):
	return y - x

def l2(x, y):
	return y + x

def mini(a, b):
	x = []
	x1 = a[0] / 2 + b[0] / 2
	y1 = a[1] / 2 + b[1] / 2
	c1 = y1 + x1
	c2 = y1 - x1
	d11 = abs(a[0] - a[1] + c2)
	d12 = abs(-a[0] - a[1] + c1)
	d21 = abs(b[0] - b[1] + c2)
	d22 = abs(-b[0] - b[1] + c1)
	t1 = [d11, d21]
	t2 = [d12, d22]
	t1 = list(set(t1))
	t2 = list(set(t2))
	x += t1
	x += t2
	return min(x)

def dis1(x, y):
	return y - x

def dis2(x, y):
	return x + y

def merge(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [0] * n1
	R = [0] * n2
	for i in range(0, n1):
		L[i] = arr[l + i]
	for j in range(0, n2):
		R[j] = arr[m + 1 + j]
	i = 0
	j = 0
	k = l
	while i < n1 and j < n2:
		if dis1(L[i]) <= dis1(R[j]):
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergeSort(arr, l, r):
	if l < r:
		m = (l + r) // 2
		mergeSort(arr, l, m)
		mergeSort(arr, m + 1, r)
		merge(arr, l, m, r)

def merge1(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [0] * n1
	R = [0] * n2
	for i in range(0, n1):
		L[i] = arr[l + i]
	for j in range(0, n2):
		R[j] = arr[m + 1 + j]
	i = 0
	j = 0
	k = l
	while i < n1 and j < n2:
		if dis2(L[i]) <= dis2(R[j]):
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergeSort1(arr, l, r):
	if l < r:
		m = (l + r) // 2
		mergeSort1(arr, l, m)
		mergeSort1(arr, m + 1, r)
		merge1(arr, l, m, r)
t = int(input())
for i in range(t):
	n = int(input())
	d1 = []
	d2 = []
	for j in range(n):
		(x, y) = map(int, input().split())
		d1.append(dis1(x, y))
		d2.append(dis2(x, y))
	d1.sort()
	min1 = 10000000000
	d2.sort()
	min2 = 10000000000
	for j in range(n - 1):
		if abs(d1[j + 1] - d1[j]) < min1:
			min1 = abs(d1[j + 1] - d1[j])
	for j in range(n - 1):
		if abs(d2[j + 1] - d2[j]) < min2:
			min2 = abs(d2[j + 1] - d2[j])
	ans = min(min1, min2) / 2
	print(ans)


def printPairs(array, n):
	if n <= 1:
		return
	minDiff = array[1] - array[0]
	for i in range(2, n):
		minDiff = min(minDiff, array[i] - array[i - 1])
	return minDiff
t = int(input())
for _ in range(t):
	n = int(input())
	setx = set()
	sety = set()
	for i in range(n):
		(aa, bb) = [int(i) for i in input().split()]
		sety.add(bb + aa)
		setx.add(aa - bb)
	if len(list(setx)) != n:
		print(0)
	elif len(list(sety)) != n:
		print(0)
	else:
		sortedx = sorted(list(setx))
		sortedy = sorted(list(sety))
		xdiff = printPairs(sortedx, len(sortedx))
		ydiff = printPairs(sortedy, len(sortedy))
		xx = min(xdiff, ydiff)
		print(xx / 2)


t = int(input())
for i in range(t):
	n = int(input())
	points = []
	for j in range(n):
		k = input()
		l = k.split()
		points.append(l)
	c1 = []
	c2 = []
	for p in points:
		ad = int(p[0]) - int(p[1])
		c1.append(ad)
		am = int(p[0]) + int(p[1])
		c2.append(am)
	c1.sort()
	c2.sort()
	dif1 = []
	dif2 = []
	for i in range(len(c1) - 1):
		dif1.append(c1[i + 1] - c1[i])
		dif2.append(c2[i + 1] - c2[i])
	mini1 = min(dif1)
	mini2 = min(dif2)
	minimum = min(mini1, mini2)
	print(minimum / 2)


def findMinDiff(arr, n):
	arr = sorted(arr)
	diff = 10 ** 20
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < diff:
			diff = arr[i + 1] - arr[i]
	return diff
for i in range(int(input())):
	N = int(input())
	a = []
	l1 = []
	l2 = []
	for j in range(N):
		(X, Y) = [int(x) for x in input().split()]
		a.append([X, Y])
	for k in range(N):
		l1.append((a[k][0] + a[k][1]) / 2)
		l2.append((a[k][0] - a[k][1]) / 2)
	p = findMinDiff(l1, len(l1))
	q = findMinDiff(l2, len(l2))
	print(min(p, q))


import math
root2 = math.sqrt(2)
for t in range(int(input())):
	num = int(input())
	a = []
	for i in range(num):
		a.append(list(map(int, input().split())))
	b = []
	c = []
	for i in range(num):
		b.append(a[i][1] - a[i][0])
		c.append(a[i][1] + a[i][0])
	c.sort(reverse=True)
	b.sort(reverse=True)
	d = []
	e = []
	for i in range(num - 1):
		d.append(b[i] - b[i + 1])
		e.append(c[i] - c[i + 1])
	f = min(min(d), min(e))
	f = f / 2
	print(f)


from math import sqrt as sq
for i in range(int(input())):
	n = int(input())
	l = []
	li = []
	d = 10 ** 9 + 1
	D = 10 ** 9 + 1
	for k in range(n):
		poi = list(map(int, input().split()))
		li.append(poi[0] - poi[1])
		l.append(poi[0] + poi[1])
	l.sort()
	li.sort()
	for i in range(n - 1):
		d1 = abs(l[i] - l[i + 1])
		if d1 < d:
			d = d1
	for j in range(n - 1):
		d2 = abs(li[j] - li[j + 1])
		if d2 < D:
			D = d2
	de = min(D, d)
	print(de / 2)


for _ in range(int(input())):
	n = int(input())
	nipun = []
	singla = []
	for i in range(n):
		(p, q) = map(int, input().split())
		c1 = p - q
		c2 = -(p + q)
		nipun.append(c1)
		singla.append(c2)
	nipun.sort()
	singla.sort()
	nipun1 = []
	singla1 = []
	for i in range(n - 1):
		maxi1 = abs(nipun[i] - nipun[i + 1])
		maxi2 = abs(singla[i] - singla[i + 1])
		nipun1.append(maxi1)
		singla1.append(maxi2)
	count = 0
	for i in range(n - 1):
		if nipun1[i] == 0 or singla1[i] == 0:
			count = 1
			break
	if count == 1:
		print('0')
	else:
		max3 = min(nipun1)
		max4 = min(singla1)
		if max3 < max4:
			print(max3 / 2)
		else:
			print(max4 / 2)


t = int(input())
for j in range(t):
	a = []
	b = []
	c = []
	d = []
	n = int(input())
	for k in range(n):
		(x, y) = map(int, input().split())
		a.append(x + y)
		b.append(-x + y)
	a.sort()
	b.sort()
	for i in range(n - 1):
		c.append((a[i + 1] - a[i]) / 2)
		d.append((b[i + 1] - b[i]) / 2)
	print(min(min(c), min(d)))


t = int(input())
for i in range(t):
	n = int(input())
	x = []
	y = []
	dx = []
	dy = []
	for j in range(n):
		c = list(map(int, input().split()))
		x.append(c[0] - c[1])
		y.append(c[0] + c[1])
	x.sort()
	y.sort()
	for j in range(1, n):
		dx.append(x[j] - x[j - 1])
		dy.append(y[j] - y[j - 1])
	a = min(dx)
	b = min(dy)
	print('{0:.6f}'.format(min(a, b) / 2))


T = int(input())
for a in range(T):
	N = int(input())
	x = [0] * N
	y = [0] * N
	lsum = [0] * N
	lsub = [0] * N
	for l in range(N):
		[x[l], y[l]] = (int(i) for i in input().split())
		lsum[l] = x[l] + y[l]
		lsub[l] = x[l] - y[l]
	lsum.sort()
	lsub.sort()
	flag = 0
	minsum = float('inf')
	minsub = float('inf')
	for f in range(N - 1):
		if abs(lsum[f + 1] - lsum[f]) < minsum:
			minsum = abs(lsum[f + 1] - lsum[f])
			if minsum == 0:
				flag = 1
				break
	for f in range(N - 1):
		if abs(lsub[f + 1] - lsub[f]) < minsub:
			minsub = abs(lsub[f + 1] - lsub[f])
			if minsub == 0:
				flag = 1
				break
	if flag == 1:
		print(0)
	else:
		temp = min(minsub, minsum)
		ans = temp / 2
		print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = []
	brr = []
	for j in range(0, n):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		arr.insert(0, x - y)
		brr.insert(0, x + y)
	arr.sort()
	brr.sort()
	m1 = arr[1] - arr[0]
	for k in range(1, n - 1):
		if arr[k + 1] - arr[k] < m1:
			m1 = arr[k + 1] - arr[k]
	m2 = brr[1] - brr[0]
	for k in range(1, n - 1):
		if brr[k + 1] - brr[k] < m2:
			m2 = brr[k + 1] - brr[k]
	if min(m1, m2) % 2 == 0:
		print(min(m1, m2) // 2)
	else:
		print(min(m1, m2) / 2)


from math import sqrt
x = int(input())
dist = float('inf')
for i in range(x):
	y = int(input())
	first = []
	second = []
	for j in range(y):
		t = list(map(float, input().split()))
		x = t[0]
		y = t[1]
		first.append((x - y) / sqrt(2))
		second.append((x + y) / sqrt(2))
	first.sort()
	second.sort()
	count = 0
	temp1 = dist
	temp2 = dist
	for i in range(len(first) - 1):
		if first[i] == first[i + 1]:
			count += 1
		if second[i] == second[i + 1]:
			count += 1
		l = abs(first[i] - first[i + 1])
		if l < temp1:
			temp1 = l
		m = abs(second[i] - second[i + 1])
		if m < temp2:
			temp2 = m
	res = min(temp2, temp1)
	if count > 0:
		print(0)
	else:
		print(res / 2 * sqrt(2))


T = int(input())
for a in range(T):
	N = int(input())
	res_points_1 = []
	res_points_2 = []
	min_dist = 10 ** 16
	for b in range(N):
		(x, y) = list(map(int, input().split()))
		res_points_1.append(x - y)
		res_points_2.append(x + y)
	res_points_1.sort()
	res_points_2.sort()
	for c in range(N - 1):
		dist_1 = res_points_1[c + 1] - res_points_1[c]
		dist_2 = res_points_2[c + 1] - res_points_2[c]
		min_dist = min(dist_1, dist_2, min_dist)
	if min_dist % 2 == 0:
		print(int(min_dist / 2))
	else:
		print(min_dist / 2)


T = int(input())
for i in range(T):
	n = int(input())
	pts = []
	for j in range(n):
		pts.append([])
		g = input()
		g = g.split(' ')
		x = int(g[0])
		y = int(g[1])
		xn = x + y
		yn = y - x
		pts[j].append(xn)
		pts[j].append(yn)
		pts[j].append(j)
	pts.sort(key=lambda x: x[0])
	dist = {}
	for i in range(n - 1):
		dist[pts[i][2]] = pts[i + 1][0] - pts[i][0]
	dist[pts[n - 1][2]] = pts[n - 1][0] - pts[n - 2][0]
	pts.sort(key=lambda x: x[1])
	for i in range(n - 1):
		diff = pts[i + 1][1] - pts[i][1]
		if diff < dist[pts[i][2]]:
			dist[pts[i][2]] = diff
	diff = pts[n - 1][1] - pts[n - 2][1]
	if diff < dist[pts[n - 1][2]]:
		dist[pts[n - 1][2]] = diff
	m = 1000000000
	for i in dist:
		if dist[i] < m:
			m = dist[i]
	print(m / 2)


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	gg = find_gcd(x, y)
	return x * y // gg
mm = 1000000007
yp = 0

def solve():
	t = nu()
	for _ in range(t):
		n = nu()
		x = set()
		y = set()
		fl = False
		for i in range(n):
			(l, r) = num()
			px = l + r
			py = r - l
			if px in x:
				fl = True
			if py in y:
				fl = True
			x.add(px)
			y.add(py)
		x = list(x)
		y = list(y)
		x.sort()
		y.sort()
		mnx = 9999999999999
		mny = 9999999999999
		if fl:
			print(0)
		else:
			for i in range(1, len(x)):
				mnx = min(mnx, x[i] - x[i - 1])
			for i in range(1, len(y)):
				mny = min(mny, y[i] - y[i - 1])
			print(min(mny, mnx) / 2)
solve()


t = int(input())
for i in range(t):
	n = int(input())
	x_s = set()
	y_s = set()
	for i in range(n):
		(x, y) = map(int, input().split())
		x_s.add(x - y)
		y_s.add(x + y)
	if len(x_s) != n or len(y_s) != n:
		print(0)
	else:
		lx = sorted(list(x_s))
		ly = sorted(list(y_s))
		xmin = (lx[1] - lx[0]) / 2
		ymin = (ly[1] - ly[0]) / 2
		for i in range(n - 1):
			if (lx[i + 1] - lx[i]) / 2 < xmin:
				xmin = (lx[i + 1] - lx[i]) / 2
			if (ly[i + 1] - ly[i]) / 2 < ymin:
				ymin = (ly[i + 1] - ly[i]) / 2
		print(min(xmin, ymin))


for i in range(int(input())):
	n = int(input())
	points_diff = []
	points_sum = []
	for t in range(n):
		(x, y) = tuple(map(int, input().split()))
		points_diff.append(y - x)
		points_sum.append(y + x)
	points_diff.sort()
	points_sum.sort()
	f_diff = []
	f_sum = []
	for i in range(1, n):
		f_diff.append(abs(points_diff[i] - points_diff[i - 1]))
		f_sum.append(abs(points_sum[i] - points_sum[i - 1]))
	print(min(min(f_diff), min(f_sum)) / 2)


from math import sqrt
C = 20000000009

def dis1(a, b):
	return abs(a + b + C)

def dis2(a, b):
	return abs(b - a + C)
t = int(input())
for _ in range(t):
	n = int(input())
	d1 = []
	d2 = []
	for i in range(n):
		(a, b) = [int(x) for x in input().split()]
		d1.append(dis1(a, b))
		d2.append(dis2(a, b))
	d1.sort()
	d2.sort()
	mn = C
	for i in range(1, len(d1)):
		mn = min(mn, d1[i] - d1[i - 1])
	for i in range(1, len(d2)):
		mn = min(mn, d2[i] - d2[i - 1])
	mn = mn / sqrt(2)
	mn = mn / 2
	mn = mn * sqrt(2)
	print('%0.8f' % mn)


t = int(input())
for _ in range(0, t):
	intercept1 = []
	intercept2 = []
	n = int(input())
	for i in range(0, n):
		(x, y) = map(int, input().split())
		intercept1.append(y + x)
		intercept2.append(y - x)
	intercept1.sort()
	intercept2.sort()
	mn1 = 10 ** 10
	mn2 = 10 ** 10
	for i in range(1, n):
		diff1 = intercept1[i] - intercept1[i - 1]
		mn1 = min(mn1, diff1)
		diff2 = intercept2[i] - intercept2[i - 1]
		mn2 = min(mn2, diff2)
		ans = min(mn1, mn2)
	print(ans / 2)


for _ in range(int(input())):
	(x1, y1) = ([], [])
	n = int(input())
	p = []
	for i in range(n):
		(x, y) = map(int, input().split())
		p.append([x, y])
		x1.append(y + x)
		y1.append(y - x)
	min = 999999999
	x1.sort()
	y1.sort()
	for i in range(n - 1):
		if x1[i + 1] - x1[i] < min:
			min = x1[i + 1] - x1[i]
	for i in range(n - 1):
		if y1[i + 1] - y1[i] < min:
			min = y1[i + 1] - y1[i]
	print(min / 2.0)


t = int(input())
for _ in range(t):
	n = int(input())
	xpy = []
	xmy = []
	for i in range(n):
		(x, y) = map(int, input().split())
		xpy.append(x + y)
		xmy.append(x - y)
	xpy.sort()
	xmy.sort()
	mini = abs(xpy[1] - xpy[0])
	for i in range(n - 1):
		if xpy[i] == xpy[i + 1] or xmy[i] == xmy[i + 1]:
			mini = 0
			break
		if abs(xpy[i + 1] - xpy[i]) < mini:
			mini = abs(xpy[i + 1] - xpy[i])
		if abs(xmy[i + 1] - xmy[i]) < mini:
			mini = abs(xmy[i + 1] - xmy[i])
	print(mini / 2)


import math
for _ in range(int(input())):
	smartn = list()
	smartp = list()
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
		c1 = x + y
		c2 = x - y
		smartn.append(c2)
		smartp.append(c1)
	smartp.sort()
	smartn.sort()
	mn = math.inf
	for i in range(n - 1):
		mn = min(mn, smartn[i + 1] - smartn[i])
		mn = min(mn, smartp[i + 1] - smartp[i])
	if mn:
		print(mn / 2)
	else:
		print(mn)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = []
	arr3 = []
	for i in range(n):
		(x, y) = map(int, input().strip().split(' '))
		arr.append(y - x)
		arr3.append(y + x)
	arr = sorted(arr)
	arr3 = sorted(arr3)
	arr2 = []
	for i in range(n - 1):
		arr2.append((arr[i + 1] - arr[i]) / 2)
		arr2.append((arr3[i + 1] - arr3[i]) / 2)
	print(min(arr2))


a = int(input())
i = 0
while i < a:
	b = int(input())
	p = []
	n = []
	j = 0
	while j < b:
		(x, y) = map(int, input().split(' '))
		sub = y - x
		add = y + x
		p.append(sub)
		n.append(add)
		j = j + 1
	n = sorted(n)
	p = sorted(p)
	h = len(p) - 1
	pd = []
	for v in range(len(p) - 1):
		gs = abs(p[v] - p[v + 1])
		pd.append(gs)
	q = 0
	while q < len(n) - 1:
		o = q + 1
		l = abs(n[q] - n[o])
		pd.append(l)
		q = q + 1
	arnav = min(pd) / 2
	print(arnav)
	i = i + 1


def findmindist():
	n = int(input())
	n_copy = n
	dist_pos = []
	dist_neg = []
	while n != 0:
		(x, y) = [int(z) for z in input().split(' ')]
		dist_pos.append(y - x)
		dist_neg.append(y + x)
		n -= 1
	dist_pos.sort()
	dist_neg.sort()
	result = abs(dist_neg[1] - dist_neg[0])
	for i in range(0, n_copy - 1):
		result = min(result, min(abs(dist_pos[i + 1] - dist_pos[i]), abs(dist_neg[i + 1] - dist_neg[i])))
	return result
t = int(input())
while t != 0:
	print(findmindist() / 2)
	t -= 1


import io, sys, os
import math as ma
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())

def solve():
	t = nu()
	for _ in range(t):
		n = nu()
		x = set()
		y = set()
		fl = False
		for i in range(n):
			(l, r) = num()
			px = l + r
			py = r - l
			if px in x:
				fl = True
			if py in y:
				fl = True
			x.add(px)
			y.add(py)
		x = list(x)
		y = list(y)
		x.sort()
		y.sort()
		mnx = 9999999999999
		mny = 9999999999999
		if fl:
			print(0)
		else:
			for i in range(1, len(x)):
				mnx = min(mnx, x[i] - x[i - 1])
			for i in range(1, len(y)):
				mny = min(mny, y[i] - y[i - 1])
			print(min(mny, mnx) / 2)

def __starting_point():
	solve()
__starting_point()


import numpy as np
t = int(input())
while t:
	n = int(input())
	X = []
	Y = []
	for i in range(n):
		(x, y) = map(int, input().split())
		(x, y) = (x - y, x + y)
		X.append(x)
		Y.append(y)
	X = set(X)
	Y = set(Y)
	if len(X) == n - 1 or len(Y) == n - 1:
		print(0)
	else:
		X = list(X)
		Y = list(Y)
		X.sort()
		Y.sort()
		for i in range(len(X) - 1):
			X[i] = X[i + 1] - X[i]
		X = X[:-1]
		for i in range(len(Y) - 1):
			Y[i] = Y[i + 1] - Y[i]
		Y = Y[:-1]
		print(min(min(X) / 2.0, min(Y) / 2.0))
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	xx = []
	yy = []
	for j in range(n):
		(x, y) = map(int, input().split())
		xx.append(x - y)
		yy.append(x + y)
	xx.sort()
	min1 = 100000000000
	for j in range(n - 1):
		if abs(xx[j + 1] - xx[j]) < min1:
			min1 = abs(xx[j + 1] - xx[j])
	yy.sort()
	min2 = 100000000000
	for j in range(n - 1):
		if abs(yy[j + 1] - yy[j]) < min2:
			min2 = abs(yy[j + 1] - yy[j])
	ans = min(min2, min1) / 2
	print(ans)


t = int(input())
while t:
	v = int(input())
	L1 = []
	Lp = []
	Ln = []
	Lpd = []
	Lnd = []
	for i in range(0, v):
		(m, n) = map(int, input().split())
		L1.append(m)
		L1.append(n)
	for i in range(0, v * 2, 2):
		x = L1[i]
		y = L1[i + 1]
		m = 1
		Lp.append(y - m * x)
		m = -1
		Ln.append(y - m * x)
	Ln.sort()
	Lp.sort()
	for k in range(0, v - 1):
		Lpd.append(abs(Lp[k + 1] - Lp[k]))
		Lnd.append(abs(Ln[k + 1] - Ln[k]))
	Lpd.sort()
	Lnd.sort()
	if Lpd[0] == 0 or Lnd[0] == 0:
		print(0)
	elif Lpd[0] < Lnd[0]:
		print(Lpd[0] / 2)
	elif Lnd[0] < Lpd[0]:
		print(Lnd[0] / 2)
	else:
		print(Lpd[0] / 2)
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	v1 = []
	v2 = []
	for i in range(n):
		(a, b) = map(int, input().split())
		c1 = a - b
		c2 = -(a + b)
		v1.append(c1)
		v2.append(c2)
	v1.sort()
	v2.sort()
	v3 = []
	v4 = []
	for i in range(n - 1):
		maxi1 = abs(v1[i] - v1[i + 1])
		maxi2 = abs(v2[i] - v2[i + 1])
		v3.append(maxi1)
		v4.append(maxi2)
	count = 0
	for i in range(n - 1):
		if v3[i] == 0 or v4[i] == 0:
			count = 1
			break
	if count == 1:
		print('0')
	else:
		max3 = min(v3)
		max4 = min(v4)
		if max3 < max4:
			print(max3 / 2)
		else:
			print(max4 / 2)


t = int(input())
for i in range(t):
	n = int(input())
	c1 = []
	cmin1 = []
	for j in range(n):
		(x, y) = map(int, input().split(' '))
		c1.append(y - x)
		cmin1.append(y + x)
	c1.sort()
	cmin1.sort()
	m1 = c1[len(c1) - 1] - c1[0]
	mmin1 = cmin1[len(cmin1) - 1] - cmin1[0]
	for k in range(len(c1) - 1):
		t1 = c1[k + 1] - c1[k]
		if m1 > t1:
			m1 = t1
		t2 = cmin1[k + 1] - cmin1[k]
		if mmin1 > t2:
			mmin1 = t2
	print(min(m1, mmin1) / 2)


for k in range(int(input())):
	n = int(input())
	arr1 = []
	arr2 = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		arr1.append(a + b)
		arr2.append(b - a)
	arr1.sort()
	arr2.sort()
	l1 = []
	l2 = []
	for i in range(len(arr1) - 1):
		l1.append(arr1[i + 1] - arr1[i])
		l2.append(arr2[i + 1] - arr2[i])
	x = min(l1)
	y = min(l2)
	print('{0:.6f}'.format(min(x, y) / 2))


from math import sqrt, atan, sin

def distance(i, j):
	try:
		slope = (i[1] - j[1]) / (i[0] - j[0])
		if slope < 0:
			return sin(atan(abs((-1 - slope) / (1 - slope)))) * sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) / 2
		else:
			return sin(atan(abs((1 - slope) / (1 + slope)))) * sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) / 2
	except ZeroDivisionError:
		return (i[1] - j[1]) / 2 ** 1.5

def key_find(x):
	return x[2]
test_case = int(input())
while test_case > 0:
	n = int(input())
	points = list()
	for i in range(n):
		points.append([int(i) for i in input().split()])
	diff_x_y = list()
	diff_y_x = list()
	for i in range(n):
		diff_x_y.append(tuple([points[i][0], points[i][1], points[i][0] - points[i][1]]))
		diff_y_x.append(tuple([points[i][0], points[i][1], points[i][0] + points[i][1]]))
	diff_x_y.sort(key=key_find)
	diff_y_x.sort(key=key_find)
	mini_list1 = list()
	mini_list2 = list()
	for i in range(n - 1):
		mini_list1.append(tuple([diff_x_y[i][:2], diff_x_y[i + 1][:2], diff_x_y[i + 1][2] - diff_x_y[i][2]]))
		mini_list2.append(tuple([diff_y_x[i][:2], diff_y_x[i + 1][:2], diff_y_x[i + 1][2] - diff_y_x[i][2]]))
	first_min = min(mini_list1, key=key_find)
	second_min = min(mini_list2, key=key_find)
	if first_min[2] == 0 or second_min[2] == 0:
		print(0)
	elif first_min[2] < second_min[2]:
		print(round(abs(distance(first_min[0][:2], first_min[1][:2])) * 2 ** 0.5, 6))
	else:
		print(round(abs(distance(second_min[0][:2], second_min[1][:2])) * 2 ** 0.5, 6))
	test_case -= 1


import math
import sys
z = math.sin(math.pi / 4)

def func(arr, n):
	arr = sorted(arr)
	diff = sys.maxsize
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < diff:
			diff = arr[i + 1] - arr[i]
	return diff
for i in range(int(input())):
	n = int(input())
	arx = []
	ary = []
	for j in range(n):
		(a, b) = map(float, input().split())
		c = (a + b) * z
		d = (a - b) * z
		arx.append(c)
		ary.append(d)
	g = func(arx, n)
	h = func(ary, n)
	if g < h:
		print(g * z)
	else:
		print(h * z)


try:
	testcase = int(input())
	while testcase > 0:
		n = int(input())
		l1 = []
		l2 = []
		l3 = []
		for i in range(n):
			(x, y) = input().split()
			x = int(x)
			y = int(y)
			l1.append((x, y))
		for i in l1:
			dist1 = abs(i[1] + i[0])
			if i[1] > 0 and i[0] < 0 and (i[1] < abs(i[0])):
				l3.append(-1 * dist1)
			elif i[1] > 0 and i[0] < 0 and (i[1] > abs(i[0])):
				l3.append(dist1)
			elif i[1] < 0 and i[0] > 0 and (abs(i[1]) < i[0]):
				l3.append(dist1)
			elif i[1] < 0 and i[0] > 0 and (abs(i[1]) > i[0]):
				l3.append(-1 * dist1)
			elif i[1] == 0 and i[0] > 0:
				l3.append(dist1)
			elif i[1] == 0 and i[0] < 0:
				l3.append(-1 * dist1)
			elif i[1] > 0 and i[0] == 0:
				l3.append(dist1)
			elif i[1] < 0 and i[0] == 0:
				l3.append(-1 * dist1)
			elif i[1] == 0 and i[0] == 0:
				l3.append(0)
			elif i[1] > 0 and i[0] > 0:
				l3.append(dist1)
			elif i[1] < 0 and i[0] < 0:
				l3.append(-1 * dist1)
			elif abs(i[0]) == abs(i[1]):
				l3.append(dist1)
			dist = abs(i[1] - i[0])
			if i[1] < i[0]:
				l2.append(-1 * dist)
			else:
				l2.append(dist)
		l2 = sorted(l2)
		l3 = sorted(l3)
		min1 = l2[1] - l2[0]
		for i in range(n - 1):
			if l2[i + 1] - l2[i] < min1:
				min1 = l2[i + 1] - l2[i]
		min2 = l3[1] - l3[0]
		for i in range(n - 1):
			if l3[i + 1] - l3[i] < min2:
				min2 = l3[i + 1] - l3[i]
		ans = min(min1, min2)
		print(ans / 2)
		testcase = testcase - 1
except:
	pass


try:
	for i in range(int(input())):
		a = int(input())
		s = []
		d = []
		for j in range(a):
			(x, y) = map(int, input().split())
			s.append(x + y)
			d.append(x - y)
		s.sort()
		d.sort()
		for i in range(a - 1, 0, -1):
			s[i] = s[i] - s[i - 1]
			d[i] = d[i] - d[i - 1]
		print(min(min(s[1:]), min(d[1:])) / 2)
except:
	pass


import math

def fun2(paramfun1, n):
	if n <= 1:
		return
	fun2param = paramfun1[1] - paramfun1[0]
	for i in range(2, n):
		fun2param = min(fun2param, paramfun1[i] - paramfun1[i - 1])
	for i in range(1, n):
		if paramfun1[i] - paramfun1[i - 1] == fun2param:
			return (paramfun1[i - 1], paramfun1[i])

def fun1(param1, param2):
	(x, y) = param1
	qx = 1 / 2 ** 0.5 * x - 1 / 2 ** 0.5 * y
	qy = 1 / 2 ** 0.5 * x + 1 / 2 ** 0.5 * y
	return (round(qx, 7), round(qy, 7))
for _ in range(int(input())):
	n = int(input())
	par1 = set()
	par2 = set()
	xxx = math.radians(45)
	for i in range(n):
		(a, b) = [int(i) for i in input().split()]
		(a, b) = fun1((a, b), xxx)
		par1.add(a)
		par2.add(b)
	if len(list(par1)) != n or len(list(par2)) != n:
		print(0)
	else:
		par1 = sorted(list(par1))
		par2 = sorted(list(par2))
		(x1, x2) = fun2(par1, len(par1))
		(y1, y2) = fun2(par2, len(par2))
		if abs(x1 - x2) > abs(y1 - y2):
			print(round(abs(y1 - y2) / 2 * math.sqrt(2), 7))
		else:
			print(round(abs(x1 - x2) / 2 * math.sqrt(2), 7))


from itertools import combinations

def minans(arr, n):
	minv = 10 ** 12
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < minv:
			minv = arr[i + 1] - arr[i]
	return minv
t = int(input())
for i in range(t):
	n = int(input())
	l1 = []
	l2 = []
	for j in range(n):
		s = input().split(' ')
		x = int(s[0])
		y = int(s[1])
		t1 = (x - y) / 2
		t2 = (x + y) / 2
		l1.append(t1)
		l2.append(t2)
	l1 = sorted(l1)
	l2 = sorted(l2)
	minv = min(minans(l1, n), minans(l2, n))
	if minv.is_integer():
		print(int(minv))
	else:
		print(minv)


import math
import operator
root2 = math.sqrt(2)

def sign(x, y, coeff):
	if y + coeff * x > 0:
		return 1
	else:
		return -1

def dist(x, y):
	dist1 = abs(x + y) / root2
	dist2 = abs(y - x) / root2
	sign1 = sign(x, y, 1)
	sign2 = sign(x, y, -1)
	return [sign1 * dist1, sign2 * dist2]
for _ in range(int(input())):
	min1 = 10 ** 9 + 7
	min2 = min1
	n = int(input())
	l = []
	distpos = []
	distneg = []
	for v in range(n):
		(x, y) = [float(num) for num in input().split()]
		l.append([x, y])
		k = dist(x, y)
		distpos.append(k[0])
		distneg.append(k[1])
	a1 = []
	a2 = []
	distpos.sort()
	distneg.sort()
	for j in range(n - 1):
		if min1 > abs(distpos[j + 1] - distpos[j]):
			min1 = abs(distpos[j + 1] - distpos[j])
		if min2 > distneg[j + 1] - distneg[j]:
			min2 = abs(distneg[j + 1] - distneg[j])
	minval = min(min1, min2)
	val = minval / 2 * root2
	if val == 0.0:
		print(0)
	else:
		print(val)


t = int(input())
for _ in range(t):
	n = int(input())
	co = []
	suma = []
	diff = []
	for i in range(n):
		(x, y) = map(int, input().strip().split())
		co.append([x, y])
		suma.append(x + y)
		diff.append(x - y)
	suma.sort()
	diff.sort()
	mina = 10 ** 9
	mina = abs((suma[0] - suma[1]) / 2)
	mina = min(mina, abs((diff[0] - diff[1]) / 2))
	for i in range(1, n - 1):
		mina = min(mina, abs((suma[i] - suma[i + 1]) / 2), abs((diff[i] - diff[i + 1]) / 2))
		if mina == 0.0:
			break
	print(mina)


t = int(input())
for zz in range(t):
	n = int(input())
	lisplus = []
	lisminus = []
	dic = {}
	dic2 = {}
	lis = []
	lines = n - 1
	for i in range(n):
		point = list(map(int, input().split()))
		lisplus.append(point)
		lisminus.append([point[0], -point[1]])
	lisplus = sorted(lisplus, key=sum)
	lisminus = sorted(lisminus, key=sum)
	if lines > n:
		print('0')
		continue
	else:
		i = len(lisplus) - 1
		j = len(lisminus) - 1
		checki = 1
		checkj = 1
		ini = 0
		inj = 0
		distan = []
		while i > 0:
			c1 = sum(lisplus[i]) - sum(lisplus[i - 1])
			c1 = c1 / 2
			dis11 = abs(c1 - sum(lisplus[i]))
			dis12 = abs(c1 - sum(lisplus[i - 1]))
			distan.append(abs(c1))
			i -= 1
		while j > 0:
			c2 = sum(lisminus[j]) - sum(lisminus[j - 1])
			c2 = c2 / 2
			dis21 = abs(c2 - sum(lisminus[j]))
			dis22 = abs(c2 - sum(lisminus[j - 1]))
			distan.append(abs(c2))
			j -= 1
		print(min(distan))


for _ in range(int(input())):
	(positive, negative) = ([], [])
	n = int(input())
	point = []
	for i in range(n):
		(x, y) = map(int, input().split())
		point.append([x, y])
		positive.append(y + x)
		negative.append(y - x)
	mini = 99999999999
	positive.sort()
	negative.sort()
	for i in range(n - 1):
		if positive[i + 1] - positive[i] < mini:
			mini = positive[i + 1] - positive[i]
	for i in range(n - 1):
		if negative[i + 1] - negative[i] < mini:
			mini = negative[i + 1] - negative[i]
	print(mini / 2.0)


import math
test = int(input())
for i in range(test):
	coordinates = int(input())
	add = []
	sub = []
	total = []
	for i in range(coordinates):
		lis = list(map(int, input().split()))
		sub.append(lis[1] - lis[0])
		add.append(lis[1] + lis[0])
		total.append(lis)
	add.sort()
	sub.sort()
	addDiff = []
	subDiff = []
	for i in range(len(add) - 1):
		addDiff.append(abs(add[i] - add[i + 1]))
		subDiff.append(abs(sub[i] - sub[i + 1]))
	k = min(min(addDiff), min(subDiff))
	print(k / 2)


import math
test = eval(input())
for k in range(test):
	n = eval(input())
	(x, y) = ([], [])
	dictfirst = {}
	dictsecond = {}
	varcheck1 = False
	varcheck2 = False
	for p in range(n):
		points = list(map(float, input().split(' ')))
		x.append(points[0])
		y.append(points[1])
	for p in range(n):
		keyfirst = y[p] - x[p]
		keysecond = y[p] + x[p]
		if keyfirst in dictfirst:
			dictfirst[keyfirst] = dictfirst[keyfirst] + 1
			varcheck1 = True
		else:
			dictfirst[keyfirst] = 1
		if keysecond in dictsecond:
			dictsecond[keysecond] = dictsecond[keysecond] + 1
			varcheck2 = True
		else:
			dictsecond[keysecond] = 1
	if varcheck1 or varcheck2:
		print(0)
		continue
	listx = []
	listy = []
	for r in range(n):
		listx.append(x[r] - y[r])
		listy.append(x[r] + y[r])
	listx.sort()
	listy.sort()
	var1 = 8000000000
	var2 = 8000000000
	for j1 in range(1, n):
		if listx[j1] - listx[j1 - 1] < var1:
			var1 = listx[j1] - listx[j1 - 1]
	for j2 in range(1, n):
		if listy[j2] - listy[j2 - 1] < var2:
			var2 = listy[j2] - listy[j2 - 1]
	print(min(var1, var2) / 2)


import cmath
import math

def f(l):
	l1 = []
	for i in range(len(l)):
		w = cmath.polar(l[i])
		z = cmath.rect(w[0], w[1] - cmath.pi / 4)
		l1.append(z)
	l1.sort(key=lambda z: z.real)
	for i in range(len(l1) - 1):
		diff = abs(l1[i].real - l1[i + 1].real)
		if diff == 0:
			print(0)
			return
		if i == 0:
			minDiffX = diff
		else:
			minDiffX = min(diff, minDiffX)
	l1.sort(key=lambda x: x.imag)
	for i in range(len(l1) - 1):
		diff = abs(l1[i].imag - l1[i + 1].imag)
		if diff == 0:
			print(0)
			return
		if i == 0:
			minDiffY = diff
		else:
			minDiffY = min(diff, minDiffY)
	print(min(minDiffX, minDiffY) * math.sin(math.pi / 4))
T = int(input())
while T:
	l = []
	n = int(input())
	while n:
		t = input().split()
		l.append(complex(int(t[0]), int(t[1])))
		n -= 1
	f(l)
	T -= 1


for _ in range(int(input())):
	n = int(input())
	plus = []
	minus = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		plus.append(x + y)
		minus.append(x - y)
	(plus.sort(), minus.sort())
	m = float('inf')
	for i in range(1, n):
		if plus[i] - plus[i - 1] < m:
			m = plus[i] - plus[i - 1]
		if minus[i] - minus[i - 1] < m:
			m = minus[i] - minus[i - 1]
	if m % 2 == 0:
		print(m // 2)
	else:
		print(m / 2)


t = int(input())
for i in range(0, t):
	n = int(input())
	c_pos = []
	c_neg = []
	for j in range(0, n):
		m = input().split()
		c_pos.append(int(m[1]) + int(m[0]))
		c_neg.append(int(m[1]) - int(m[0]))
	c_pos.sort()
	c_neg.sort()
	min = c_neg[1] - c_neg[0]
	for j in range(n - 1):
		if min > c_pos[j + 1] - c_pos[j]:
			min = c_pos[j + 1] - c_pos[j]
		if min > c_neg[j + 1] - c_neg[j]:
			min = c_neg[j + 1] - c_neg[j]
		if min == 0:
			break
	if min == 0:
		print(0)
	else:
		print(min / 2)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	a = []
	b = []
	for j in range(n):
		X = input().split()
		x = int(X[0])
		y = int(X[1])
		a.append(x + y)
		b.append(y - x)
		l.append([x, y])
	a.sort()
	b.sort()
	j = 1
	c = []
	d = []
	while j < n:
		temp = a[j] - a[j - 1]
		c.append(temp)
		t2 = b[j] - b[j - 1]
		d.append(t2)
		j = j + 1
	c.sort()
	d.sort()
	k = (c[0], d[0])
	print(min(k) / 2)


from math import sqrt, atan, sin, pow
from sys import maxsize

class WTBTR:

	def __init__(self, t):
		self.t = t

	@staticmethod
	def distance(i, j):
		try:
			slope = (i[1] - j[1]) / (i[0] - j[0])
			if slope == 1 or slope == -1:
				return 0
			elif slope < 0:
				return sin(atan(abs((-1 - slope) / (1 - slope)))) * sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) / 2
			elif slope > 0:
				return sin(atan(abs((1 - slope) / (1 + slope)))) * sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) / 2
			else:
				return (i[0] - j[0]) / 2 ** 1.5
		except ZeroDivisionError:
			return (i[1] - j[1]) / 2 ** 1.5

	def main(self):
		while self.t > 0:
			self.t -= 1
			n = int(input())
			c = [list(map(int, input().split())) for i in range(n)]
			xy = [tuple([c[i][0], c[i][1], c[i][0] - c[i][1]]) for i in range(n)]
			yx = [tuple([c[i][0], c[i][1], c[i][1] + c[i][0]]) for i in range(n)]
			xy.sort(key=lambda x: x[2])
			yx.sort(key=lambda x: x[2])
			temp1 = [(xy[i][:2], xy[i + 1][:2], xy[i + 1][2] - xy[i][2]) for i in range(n - 1)]
			temp2 = [(yx[i][:2], yx[i + 1][:2], yx[i + 1][2] - yx[i][2]) for i in range(n - 1)]
			minimum1 = min(temp1, key=lambda x: x[2])
			minimum2 = min(temp2, key=lambda x: x[2])
			if minimum1[2] == 0 or minimum2[2] == 0:
				print(0)
			elif minimum1[2] <= minimum2[2]:
				print(round(abs(self.distance(minimum1[0][:2], minimum1[1][:2])) * 2 ** 0.5, 6))
			else:
				print(round(abs(self.distance(minimum2[0][:2], minimum2[1][:2])) * 2 ** 0.5, 6))
a = WTBTR(int(input()))
a.main()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	(mp, mn) = ([], [])
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		mp.append(y - x)
		mn.append(y + x)
	dmin = abs(mp[1] - mp[0])
	mp.sort()
	mn.sort()
	for i in range(n - 1):
		dmin = min(dmin, mp[i + 1] - mp[i])
		dmin = min(dmin, mn[i + 1] - mn[i])
	if dmin % 2 == 0:
		print(dmin // 2)
	else:
		print(dmin / 2)


import math
t = int(input())
for k in range(t):
	n = int(input())
	(sum, diff) = ([], [])
	for i in range(n):
		s = input()
		(x1, y1) = s.split(' ')
		x1 = int(x1)
		y1 = int(y1)
		sum.append(x1 + y1)
		diff.append(x1 - y1)
	sum.sort()
	diff.sort()
	min1 = math.inf
	min2 = math.inf
	for i in range(len(sum) - 1):
		temp1 = abs(sum[i + 1] - sum[i])
		if temp1 < min1:
			min1 = temp1
		temp2 = abs(diff[i + 1] - diff[i])
		if temp2 < min2:
			min2 = temp2
	print(min(min1, min2) / 2)


for _ in range(int(input())):
	n = int(input())
	xset = set()
	yset = set()
	for i in range(n):
		(c, d) = [int(i) for i in input().split()]
		xset.add(c - d)
		yset.add(c + d)
	xmin = 100
	if len(list(xset)) != n or len(list(yset)) != n:
		print(0)
	else:
		xset = sorted(list(xset))
		yset = sorted(list(yset))
		xmin = xset[1] - xset[0]
		ymin = yset[1] - yset[0]
		for i in range(0, len(xset) - 1):
			if xmin > xset[i + 1] - xset[i]:
				xmin = xset[i + 1] - xset[i]
			if ymin > yset[i + 1] - yset[i]:
				ymin = yset[i + 1] - yset[i]
		print(min(xmin, ymin) / 2)


t = int(input())
for i in range(t):
	n = int(input())
	x = []
	y = []
	pos = []
	neg = []
	b = True
	for j in range(n):
		(a, b) = map(int, input().split(' '))
		x.append(a)
		y.append(b)
		r = b + a
		s = b - a
		pos.append(r)
		neg.append(s)
	c_pos = []
	c_neg = []
	pos.sort()
	neg.sort()
	for j in range(n - 1):
		r = pos[j + 1] - pos[j]
		s = neg[j + 1] - neg[j]
		c_pos.append(r)
		c_neg.append(s)
	c_neg.sort()
	c_pos.sort()
	q = min(min(c_pos), min(c_neg))
	q = q / 2
	print(q)


for _ in range(int(input())):
	(newx, newy) = ([], [])
	n = int(input())
	po = []
	for i in range(n):
		(x, y) = map(int, input().split())
		po.append([x, y])
		newy.append(y - x)
		newx.append(y + x)
	min = 1000000001
	newy.sort()
	newx.sort()
	for j in range(n - 1):
		if newx[j + 1] - newx[j] < min:
			min = newx[j + 1] - newx[j]
	for j in range(n - 1):
		if newy[j + 1] - newy[j] < min:
			min = newy[j + 1] - newy[j]
	print(min / 2.0)


t = int(input())
for test in range(t):
	n = int(input())
	a_set = set()
	b_set = set()
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		a_set.add(x - y)
		b_set.add(x + y)
	a_set = list(a_set)
	b_set = list(b_set)
	if len(a_set) != n or len(b_set) != n:
		print(0)
	else:
		a_set = sorted(a_set)
		b_set = sorted(b_set)
		a1 = a_set[1] - a_set[0]
		b1 = b_set[1] - b_set[0]
		for i in range(2, n):
			a1 = min(a1, a_set[i] - a_set[i - 1])
			b1 = min(b1, b_set[i] - b_set[i - 1])
		print(min(a1, b1) / 2)


t = int(input())
for _ in range(t):
	n = int(input())
	c = []
	l = []
	for i in range(n):
		(x, y) = map(int, input().split())
		c.append(x - y)
		l.append(x + y)
	c = sorted(c)
	l = sorted(l)
	dis = []
	lis = []
	for i in range(len(c) - 1):
		dis.append(abs(c[i] - (c[i] / 2 + c[i + 1] / 2)))
		lis.append(abs(l[i] - (l[i] / 2 + l[i + 1] / 2)))
	print(min(min(dis), min(lis)))


from decimal import *
getcontext().prec = 1
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	i = 0
	b = []
	while i < n:
		(x, y) = map(int, input().split())
		a.append(x + y)
		b.append(x - y)
		i += 1
	a.sort()
	b.sort()
	m = 1000000007
	for i in range(1, n):
		k = abs(a[i] - a[i - 1])
		l = abs(b[i] - b[i - 1])
		m = min(m, k, l)
	print(Decimal(m / 2))


def findMinDiff(arr, n):
	diff = 10 ** 20
	pos = 0
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < diff:
			diff = arr[i + 1] - arr[i]
			pos = i
	return diff
t = int(input())
for i in range(t):
	n = int(input())
	l1 = list()
	l2 = list()
	for j in range(n):
		(x, y) = map(int, input().split())
		l1.append(x + y)
		l2.append(x - y)
	l1.sort()
	l2.sort()
	d1 = findMinDiff(l1, n)
	d2 = findMinDiff(l2, n)
	df = min(d1, d2)
	if df == 0:
		print(0)
	else:
		print(abs(df) / 2)


import bisect
ans = []
test = int(input())
for x in range(test):
	n = int(input())
	line = []
	for l in range(n):
		on = []
		li = input()
		li = list(map(int, li.split(' ')))
		on.append(-li[0] + li[1])
		on.append(-li[0] - li[1])
		line.append(on)
	list1 = []
	list2 = []
	mini = 1
	i = 0
	for j in range(i + 1, n):
		dist1 = line[i][0] - line[j][0]
		dist2 = line[i][1] - line[j][1]
		if dist1 == 0 or dist2 == 0:
			mini = 0
			break
		else:
			list1.append(dist1)
			list2.append(dist2)
	if not mini:
		ans.append(float(mini))
	elif n == 2:
		mini = min(abs(list1[0]), abs(list2[0]))
		ans.append(float(mini) / 2)
	else:
		list1.sort()
		list2.sort()
		mini = list1[1] - list1[0]
		for i in range(1, n - 1):
			val1 = abs(list1[i] - list1[i - 1])
			val2 = abs(list2[i] - list2[i - 1])
			val = min(val1, val2, abs(list1[i - 1]), abs(list2[i - 1]))
			if val < mini:
				mini = val
		mini = min(abs(list1[n - 2]), abs(list2[n - 2]), mini)
		ans.append(float(mini) / 2)
for x in ans:
	if x.is_integer():
		print(int(x))
	else:
		print(x)


l = int(input())
for k in range(l):
	t = int(input())
	c = []
	cx = []
	mi = []
	count = 0
	for i in range(t):
		z = input()
		z = list(map(int, z.split()))
		cons = z[1] - z[0]
		con = z[0] + z[1]
		c.append(cons)
		cx.append(con)
	c.sort()
	cx.sort()
	le = len(c)
	for j in range(le - 1):
		if c[j] != c[j + 1] and cx[j] != cx[j + 1]:
			mi.append(abs(c[j] - c[j + 1]))
			mi.append(abs(cx[j] - cx[j + 1]))
		else:
			count += 1
			break
	if count == 0:
		print(min(mi) / 2)
	else:
		print(0)


t = int(input())
assert 1 <= t <= 100
for _ in range(t):
	n = int(input())
	assert 2 <= n <= 10000
	points = []
	for i in range(n):
		(x, y) = map(int, input().split())
		points.append((x, y))
	d = float('inf')
	first = []
	findex = [None] * n
	second = []
	sindex = [None] * n
	for (i, (x, y)) in enumerate(points):
		first.append((x + y, i))
		second.append((x - y, i))
	first.sort()
	second.sort()
	for (j, (c, i)) in enumerate(first):
		findex[i] = j
	for (j, (c, i)) in enumerate(second):
		sindex[i] = j
	for (i, (x, y)) in enumerate(points):
		if findex[i]:
			d = min(d, abs(x + y - first[findex[i] - 1][0]))
		if findex[i] < n - 1:
			d = min(d, abs(x + y - first[findex[i] + 1][0]))
		if sindex[i]:
			d = min(d, abs(x - y - second[sindex[i] - 1][0]))
		if sindex[i] < n - 1:
			d = min(d, abs(x - y - second[sindex[i] + 1][0]))
	print(d / 2)


test = int(input())
import math
for t in range(test):
	n = int(input())
	X = []
	Y = []
	for i in range(n):
		l = list(map(int, input().split(' ')))
		x = l[0]
		y = l[1]
		a = x + y
		b = -x + y
		X.append(a)
		Y.append(b)
	X.sort()
	Y.sort()
	min = 10000000000
	for i in range(n - 1):
		here = abs(X[i] - X[i + 1])
		if here < min:
			min = here
	for i in range(n - 1):
		here = abs(Y[i] - Y[i + 1])
		if here < min:
			min = here
	print(min / 2)


import math
t = int(input())
for x in range(t):
	n = int(input())
	cordno = []
	cordpo = []
	no = []
	po = []
	for y in range(n):
		(a, b) = map(int, input().split())
		cordno.append([a, b, a + b])
		cordpo.append([a, b, b - a])
		no.append(a + b)
		po.append(b - a)
	cordno.sort(key=lambda x: x[2])
	cordpo.sort(key=lambda x: x[2])
	if len(set(no)) != n or len(set(po)) != n:
		print(0)
		continue
	for y in range(n - 1):
		c1 = float((cordno[y][0] + cordno[y + 1][0]) / 2) + float((cordno[y][1] + cordno[y + 1][1]) / 2)
		c2 = float((cordpo[y][0] + cordpo[y + 1][0]) / 2) - float((cordpo[y][1] + cordpo[y + 1][1]) / 2)
		if y == 0:
			m1 = abs(float(cordno[y][0] + cordno[y][1] - c1))
			m2 = abs(float(cordpo[y][1] - cordpo[y][0] + c2))
		else:
			d1 = abs(float(cordno[y][0] + cordno[y][1] - c1))
			d2 = abs(float(cordpo[y][1] - cordpo[y][0] + c2))
			if d1 < m1:
				m1 = d1
			if d2 < m2:
				m2 = d2
	print(min(m1, m2))


import math
output = []
for test_case in range(int(input())):
	n = input()
	x = []
	y = []
	flag = 0
	carr1 = []
	carr2 = []
	for entry in range(int(n)):
		arr = input().split(' ')
		x.append(int(arr[0]))
		y.append(int(arr[1]))
		carr1.append(int(arr[1]) - int(arr[0]))
		carr2.append(int(arr[1]) + int(arr[0]))
	carr1.sort()
	carr2.sort()
	min = math.inf
	for i in range(len(x) - 1):
		min_c1 = abs(carr1[i] - carr1[i + 1])
		min_c2 = abs(carr2[i] - carr2[i + 1])
		min_c = 0
		if min_c1 < min_c2:
			min_c = min_c1
		else:
			min_c = min_c2
		if min_c < min:
			min = min_c
	if min == 0:
		output.append(0)
	else:
		output.append(min / 2)
for o in output:
	print(o)


t = int(input())
for x in range(t):
	n = int(input())
	ls = []
	lsm = []
	lsp = []
	for y in range(n):
		ls.append(list(map(int, input().strip().split())))
	mini = 10000000000000
	for i in range(n):
		lsm.append(ls[i][1] - ls[i][0])
	for j in range(n):
		lsp.append(ls[j][1] + ls[j][0])
	lsm.sort()
	lsp.sort()
	for k in range(n - 1):
		temp = lsm[k + 1] - lsm[k]
		if temp < mini:
			mini = temp
	for l in range(n - 1):
		tmp = lsp[l + 1] - lsp[l]
		if tmp < mini:
			mini = tmp
	print(mini / 2)


def findMinDiff(arr, n):
	arr = sorted(arr)
	diff = 10 ** 20
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < diff:
			diff = arr[i + 1] - arr[i]
	return diff
arr = [0, 1, -1]
n = len(arr)
test = int(input())
for i in range(test):
	n = int(input())
	XX = list()
	YY = list()
	for k in range(n):
		(m, n1) = map(int, input().split(' '))
		XX.append(m + n1)
		YY.append(m - n1)
	XX.sort()
	YY.sort()
	diff = 10 ** 20
	for i in range(n - 1):
		if XX[i + 1] - XX[i] < diff:
			diff = XX[i + 1] - XX[i]
	for i in range(n - 1):
		if YY[i + 1] - YY[i] < diff:
			diff = YY[i + 1] - YY[i]
	print(0.5 * diff)


T = int(input())
for i in range(0, T):
	N = int(input())
	v = []
	a = []
	for j in range(0, N):
		(x, y) = map(int, input().split())
		a.append(y - x)
		v.append(x + y)
	a.sort()
	v.sort()
	diff = abs(v[0] - v[1])
	for j in range(1, len(a)):
		diff = min(abs(a[j] - a[j - 1]), diff, abs(v[j] - v[j - 1]))
	print(diff / 2.0)


from math import inf
t = int(input())
for i in range(0, t):
	n = int(input())
	subtract = []
	add = []
	for j in range(1, n + 1):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		subtract.append(x - y)
		add.append(x + y)
	subtract.sort()
	add.sort()
	smallForSubtract = inf
	smallForAdd = inf
	for k in range(0, n - 1):
		smallForSubtract = min(smallForSubtract, abs(subtract[k + 1] - subtract[k]))
		smallForAdd = min(smallForAdd, abs(add[k + 1] - add[k]))
	final = min(smallForAdd, smallForSubtract) / 2
	print(final)


import bisect

def insert(list, n):
	bisect.insort(list, n)
	return list
t = int(input())
for i in range(0, t):
	n = int(input())
	arr = []
	brr = []
	for j in range(0, n):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		insert(arr, x - y)
		insert(brr, x + y)
	m1 = arr[1] - arr[0]
	for k in range(1, n - 1):
		if arr[k + 1] - arr[k] < m1:
			m1 = arr[k + 1] - arr[k]
	m2 = brr[1] - brr[0]
	for k in range(1, n - 1):
		if brr[k + 1] - brr[k] < m2:
			m2 = brr[k + 1] - brr[k]
	print(min(m1, m2) / 2)


def main():
	for _ in range(int(input())):
		n = int(input())
		x = []
		y = []
		d1 = {}
		d2 = {}
		for i in range(n):
			(a, b) = list(map(int, input().split()))
			x.append([(a + b) / 2, (b - a) / 2])
			y.append([(b - a) / 2, (a + b) / 2])
			d1.setdefault((a + b) / 2, 0)
			d1[(a + b) / 2] += 1
			d2.setdefault((b - a) / 2, 0)
			d2[(b - a) / 2] += 1
		x = sorted(x)
		y = sorted(y)
		flag = 0
		for i in d1.values():
			if i > 1:
				flag = 1
				break
		if flag:
			print(0)
			continue
		for i in d2.values():
			if i > 1:
				flag = 1
				break
		if flag:
			print(0)
			continue
		ans = 0
		ans1 = 1000000000.0
		ans2 = 1000000000.0
		for i in range(n - 1):
			l1 = x[i]
			l2 = x[i + 1]
			if ans1 > abs(l1[0] - l2[0]):
				ans1 = abs(l1[0] - l2[0])
		for i in range(n - 1):
			l1 = y[i]
			l2 = y[i + 1]
			if ans2 > abs(l1[0] - l2[0]):
				ans2 = abs(l1[0] - l2[0])
		ans = min(ans1, ans2)
		print('%.6f' % ans)
main()


t = int(input())
while t != 0:
	n = int(input())
	Xtrans = []
	Ytrans = []
	for x in range(0, n):
		(x, y) = map(int, input().split())
		X = x + y
		Y = y - x
		Xtrans.append(X)
		Ytrans.append(Y)
	Xtrans.sort()
	Ytrans.sort()
	for x in range(0, len(Ytrans) - 1):
		if x == 0:
			minimumY = abs(Ytrans[x] - Ytrans[x + 1]) / 2
		elif abs(Ytrans[x] - Ytrans[x + 1]) / 2 < minimumY:
			minimumY = abs(Ytrans[x] - Ytrans[x + 1]) / 2
	for x in range(0, len(Xtrans) - 1):
		if x == 0:
			minimumX = abs(Xtrans[x] - Xtrans[x + 1]) / 2
		elif abs(Xtrans[x] - Xtrans[x + 1]) / 2 < minimumX:
			minimumX = abs(Xtrans[x] - Xtrans[x + 1]) / 2
	print(min(minimumX, minimumY))
	t -= 1


t = int(input())
while t:
	l1 = []
	l2 = []
	n = int(input())
	for i in range(n):
		(x, y) = [int(x) for x in input().split()]
		l1.append(x + y)
		l2.append(y - x)
	l1.sort()
	l2.sort()
	diff = 10 ** 11
	for i in range(n - 1):
		if l1[i + 1] - l1[i] < diff:
			diff = l1[i + 1] - l1[i]
		if l2[i + 1] - l2[i] < diff:
			diff = l2[i + 1] - l2[i]
	print(diff / 2)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	a = []
	b = []
	for j in range(N):
		(X, Y) = [int(k) for k in input().split(' ')]
		a.append(Y - X)
		b.append(Y + X)
	a.sort()
	b.sort()
	min_a = a[1] - a[0]
	min_b = b[1] - b[0]
	for j in range(1, N - 1):
		aaa = a[j + 1] - a[j]
		bbb = b[j + 1] - b[j]
		if aaa < min_a:
			min_a = aaa
		if bbb < min_b:
			min_b = bbb
	print(min(min_a, min_b) / 2)