Read problem statements in [Vietnamese],
[Bengali], [Mandarin Chinese], and [Russian] as well. 

Given $N$ points in a $2D$ space, find the minimum sum of areas of rectangles required to cover all the points given that we can use at most $2$ non-overlapping rectangles whose sides can touch. The rectangles must be axis-aligned, meaning the sides are vertical and horizontal.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains $N + 1$ lines of input.
The first line contains a single integer $N$, the number of points. 
The next $N$ lines each contains two integers $x_{i}$, $y_{i}$, the coordinates of the $i$-th point.

Note: Points need not be distinct.

------ Output ------
For each test case, output in a single line the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ x_{i}, y_{i} ≤ 10^{9}$
The sum of $N$ over all test cases is at most $10^{5}$.

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

1

100 100

4

1 100

100 100

100 1

1 1

5

1 100

100 100

100 1

1 1

50 50
----- Sample Output 1 ------ 
0

0

4851
----- explanation 1 ------ 
Case 1: Since there is only one point, the minimum area of a rectangle to cover this point is $0$.

Case 2: We can have rectangles as $2$ opposite sides of the square. Since the width of the rectangles is $0$, the total area is also $0$.

Case 3: The optimal solution is with the rectangles having endpoints $\{(1, 1), (100, 1), (1, 50), (100, 50)\}$ and $\{(1, 100), (1, 100), (100, 100), (100, 100)\}$. Therefore the total area is $49 \cdot 99 + 0 \cdot 99 = 4851$

Difficulty: HARD
Tags: Geometry

Range queries

Mathematics

Constructive algorithms
Skill types: Range queries

Starter code:

Solutions:
from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def solve(p):
	(minium_X, maximum_X) = (defaultdict(INF), defaultdict(NINF))
	(minium_Y, maximum_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		minium_X[y] = min(minium_X[y], x)
		maximum_X[y] = max(maximum_X[y], x)
		minium_Y[x] = min(minium_Y[x], y)
		maximum_Y[x] = max(maximum_Y[x], y)
	X = list(minium_Y.keys())
	Y = list(minium_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, minium_Y[x]), max(mx, maximum_Y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, minium_Y[x]), max(mx, maximum_Y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, minium_X[y]), max(mx, maximum_X[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, minium_X[y]), max(mx, maximum_X[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	ans = solve(p)
	print(ans)


def get_min_area_by_horizontal_split(points):
	points.sort()
	xs = [point[0] for point in points]
	first_rectangle = [(points[0][1], points[0][1])]
	for (x, y) in points[1:]:
		bottom = min(first_rectangle[-1][0], y)
		top = max(first_rectangle[-1][1], y)
		first_rectangle.append((bottom, top))
	first_heights = [top - bottom for (bottom, top) in first_rectangle]
	second_rectangle = [(points[-1][1], points[-1][1])]
	for (x, y) in points[-2::-1]:
		bottom = min(second_rectangle[-1][0], y)
		top = max(second_rectangle[-1][1], y)
		second_rectangle.append((bottom, top))
	second_rectangle = second_rectangle[::-1]
	second_heights = [top - bottom for (bottom, top) in second_rectangle]
	min_area = 10 ** 18
	first_left = xs[0]
	second_right = xs[-1]
	iterator = zip(xs[:-1], first_heights[:-1], xs[1:], second_heights[1:])
	for (first_right, first_height, second_left, second_height) in iterator:
		first_width = first_right - first_left
		first_area = first_width * first_height
		second_width = second_right - second_left
		second_area = second_width * second_height
		min_area = min(min_area, first_area + second_area)
	return min_area
n_testcase = int(input())
for testcase in range(n_testcase):
	n = int(input())
	points = [tuple((int(x) for x in input().split())) for i in range(n)]
	if n <= 2:
		print(0)
		continue
	points_sorted_by_x = sorted(points)
	points_sorted_by_y = sorted([(y, x) for (x, y) in points])
	min_area = min(get_min_area_by_horizontal_split(points_sorted_by_x), get_min_area_by_horizontal_split(points_sorted_by_y))
	print(min_area)


for _ in range(int(input())):
	n = int(input())
	points = []
	for i in range(n):
		points.append(tuple(map(int, input().split())))
	if n <= 2:
		print(0)
		continue
	A = float('inf')
	X = list(sorted(points))
	(minpref, maxpref, minsuff, maxsuff) = ([X[0][1]], [X[0][1]], [X[-1][1]], [X[-1][1]])
	for i in range(1, n):
		minpref.append(min(minpref[i - 1], X[i][1]))
		maxpref.append(max(maxpref[i - 1], X[i][1]))
		minsuff.append(min(minsuff[i - 1], X[n - i - 1][1]))
		maxsuff.append(max(maxsuff[i - 1], X[n - i - 1][1]))
	for i in range(n - 1):
		w0 = X[i][0] - X[0][0]
		h0 = maxpref[i] - minpref[i]
		w1 = X[n - 1][0] - X[i + 1][0]
		h1 = maxsuff[n - i - 2] - minsuff[n - i - 2]
		A = min(A, w0 * h0 + w1 * h1)
	Y = list(sorted(points, key=lambda x: (x[1], x[0])))
	(minpref, maxpref, minsuff, maxsuff) = ([Y[0][0]], [Y[0][0]], [Y[-1][0]], [Y[-1][0]])
	for i in range(1, n):
		minpref.append(min(minpref[i - 1], Y[i][0]))
		maxpref.append(max(maxpref[i - 1], Y[i][0]))
		minsuff.append(min(minsuff[i - 1], Y[n - i - 1][0]))
		maxsuff.append(max(maxsuff[i - 1], Y[n - i - 1][0]))
	for i in range(n - 1):
		w0 = maxpref[i] - minpref[i]
		h0 = Y[i][1] - Y[0][1]
		w1 = maxsuff[n - i - 2] - minsuff[n - i - 2]
		h1 = Y[n - 1][1] - Y[i + 1][1]
		A = min(A, w0 * h0 + w1 * h1)
	print(A)


from operator import itemgetter

def AreaCalculation(sorted_list):
	Area_1 = [0] * N
	first = sorted_list[0][0]
	index = 0
	(mx_w, mn_w) = (sorted_list[0][1], sorted_list[0][1])
	for (a, b) in sorted_list:
		h = a - first
		mx_w = max(mx_w, b)
		mn_w = min(mn_w, b)
		Area_1[index] = h * (mx_w - mn_w)
		index += 1
	Area_2 = [0] * N
	last = sorted_list[-1][0]
	index = N - 1
	(mx_w, mn_w) = (sorted_list[-1][1], sorted_list[-1][1])
	for (a, b) in sorted_list[::-1]:
		h = last - a
		mx_w = max(mx_w, b)
		mn_w = min(mn_w, b)
		Area_2[index] = h * (mx_w - mn_w)
		index -= 1
	area = float('inf')
	for i in range(N - 1):
		area = min(area, Area_1[i] + Area_2[i + 1])
	return area

def MinimumDualArea(N, L1, L2):
	if N <= 2:
		return 0
	L1.sort()
	L2.sort()
	return min(AreaCalculation(L1), AreaCalculation(L2))
T = int(input())
for case in range(T):
	N = int(input())
	L1 = []
	L2 = []
	for i in range(N):
		(x, y) = tuple(map(int, input().split()))
		L1.append((x, y))
		L2.append((y, x))
	print(MinimumDualArea(N, L1, L2))


import math
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort(key=lambda x: x[1])
	l.sort(key=lambda x: x[0])
	pref1 = [[l[0][1], l[0][1]]]
	pref2 = [[l[-1][1], l[-1][1]]]
	ma = l[0][1]
	mi = l[0][1]
	for i in range(1, n):
		ma = max(ma, l[i][1])
		mi = min(mi, l[i][1])
		pref1.append([ma, mi])
	ma = l[-1][1]
	mi = l[-1][1]
	for i in range(n - 2, -1, -1):
		ma = max(ma, l[i][1])
		mi = min(mi, l[i][1])
		pref2.append([ma, mi])
	pref2 = pref2[::-1]
	a = l[0][0]
	b = l[-1][0]
	m = math.inf
	ans = []
	for i in range(n - 1):
		x = abs(a - l[i][0]) * abs(pref1[i][0] - pref1[i][1])
		y = abs(l[i + 1][0] - b) * abs(pref2[i + 1][0] - pref2[i + 1][1])
		ans.append(x + y)
		m = min(x + y, m)
	a1 = m
	l.sort(key=lambda x: x[1])
	pref1 = [[l[0][0], l[0][0]]]
	pref2 = [[l[-1][0], l[-1][0]]]
	ma = l[0][0]
	mi = l[0][0]
	for i in range(1, n):
		ma = max(ma, l[i][0])
		mi = min(mi, l[i][0])
		pref1.append([ma, mi])
	ma = l[-1][0]
	mi = l[-1][0]
	for i in range(n - 2, -1, -1):
		ma = max(ma, l[i][0])
		mi = min(mi, l[i][0])
		pref2.append([ma, mi])
	pref2 = pref2[::-1]
	a = l[0][1]
	b = l[-1][1]
	m = math.inf
	ans = []
	for i in range(n - 1):
		x = abs(a - l[i][1]) * abs(pref1[i][0] - pref1[i][1])
		y = abs(l[i + 1][1] - b) * abs(pref2[i + 1][0] - pref2[i + 1][1])
		ans.append(x + y)
		m = min(x + y, m)
	x = min(m, a1)
	if x == math.inf:
		print(0)
	else:
		print(x)


import math

def calc(L, n):
	pre_min = [0] * n
	suf_min = [0] * n
	pre_max = [0] * n
	suf_max = [0] * n
	pre_max[0] = L[0][1]
	pre_min[0] = L[0][1]
	for i in range(1, n):
		pre_max[i] = max(pre_max[i - 1], L[i][1])
		pre_min[i] = min(pre_min[i - 1], L[i][1])
	suf_max[n - 1] = L[n - 1][1]
	suf_min[n - 1] = L[n - 1][1]
	for i in range(n - 2, -1, -1):
		suf_max[i] = max(suf_max[i + 1], L[i][1])
		suf_min[i] = min(suf_min[i + 1], L[i][1])
	ans = math.inf
	for i in range(n - 1):
		s1 = L[i][0] - L[0][0]
		s2 = pre_max[i] - pre_min[i]
		s3 = suf_max[i + 1] - suf_min[i + 1]
		s4 = L[n - 1][0] - L[i + 1][0]
		ans = min(ans, s1 * s2 + s3 * s4)
	return ans
t = int(input())
for z in range(t):
	n = int(input())
	points = []
	points_y = []
	for i in range(n):
		p = list(map(int, input().split()))
		points.append(p)
		points_y.append(p[::-1])
	if n <= 2:
		print(0)
	else:
		points.sort()
		points_y.sort()
		print(min(calc(points, n), calc(points_y, n)))


try:
	import sys
	from sys import stdin

	def indx(li, val):
		(f, l, ind) = (0, len(li), -1)
		while f <= l and ind == -1:
			mid = (f + l) // 2
			if li[mid] == val:
				ind = mid
			elif val < li[mid]:
				l = mid - 1
			else:
				f = mid + 1
		return ind

	def solveA(x, Y, ar, n):
		(max_h, min_h) = (0, sys.maxsize)
		for i in range(n - 1):
			(max_h, min_h) = (max(x[i][1], max_h), min(x[i][1], min_h))
			d1 = max_h - min_h
			ind = indx(Y, x[i][1])
			del Y[ind]
			d2 = Y[-1] - Y[0]
			new_ar = d1 * (x[i][0] - x[0][0]) + d2 * (x[n - 1][0] - x[i + 1][0])
			ar = min(ar, new_ar)
		return ar

	def solveB(y, X, ar, n):
		(max_wd, min_wd) = (0, sys.maxsize)
		for i in range(n - 1):
			(max_wd, min_wd) = (max(y[i][1], max_wd), min(y[i][1], min_wd))
			d3 = max_wd - min_wd
			ind = indx(X, y[i][1])
			del X[ind]
			d4 = X[-1] - X[0]
			new_ar = d3 * (y[i][0] - y[0][0]) + d4 * (y[n - 1][0] - y[i + 1][0])
			ar = min(ar, new_ar)
		return ar

	def solve(n):
		(x, y, X, Y, ar) = ([], [], [], [], sys.maxsize)
		for i in range(n):
			(a, b) = map(int, sys.stdin.readline().split())
			(x.append([a, b]), y.append([b, a]), X.append(a), Y.append(b))
		x.sort()
		y.sort()
		X.sort()
		Y.sort()
		re = solveA(x, Y, ar, n)
		result = solveB(y, X, re, n)
		if n == 1:
			print(0)
		else:
			print(result)

	def main():
		for _ in range(int(sys.stdin.readline())):
			n = int(sys.stdin.readline())
			solve(n)
	main()
except Exception:
	pass


def calc(a, n):
	p1 = [0] * n
	p2 = [0] * n
	s1 = [0] * n
	s2 = [0] * n
	p1[0] = a[0][1]
	p2[0] = a[0][1]
	for i in range(1, n):
		p1[i] = max(p1[i - 1], a[i][1])
		p2[i] = min(p2[i - 1], a[i][1])
	s1[n - 1] = a[n - 1][1]
	s2[n - 1] = a[n - 1][1]
	for i in range(n - 2, -1, -1):
		s1[i] = max(s1[i + 1], a[i][1])
		s2[i] = min(s2[i + 1], a[i][1])
	ans = float('inf')
	for i in range(0, n - 1):
		r1l = p1[i] - p2[i]
		r1b = a[i][0] - a[0][0]
		r2l = s1[i + 1] - s2[i + 1]
		r2b = a[n - 1][0] - a[i + 1][0]
		ans = min(ans, r1l * r1b + r2l * r2b)
	return ans
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a1 = []
	a2 = []
	for i in range(0, n):
		b = [int(x) for x in input().split()]
		a1.append(b)
		a2.append(b[::-1])
	if n <= 2:
		print(0)
		continue
	a1.sort()
	ans1 = calc(a1, n)
	a2.sort()
	ans2 = calc(a2, n)
	print(min(ans1, ans2))


import math

def dv(n, a):
	a.sort()
	bfl = [-1] * n
	bfr = [-1] * n
	bfl[0] = a[0][1]
	for i in range(1, n):
		bfl[i] = max(bfl[i - 1], a[i][1])
	bfr[n - 1] = a[n - 1][1]
	for i in range(n - 2, -1, -1):
		bfr[i] = max(bfr[i + 1], a[i][1])
	sfl = [math.inf] * n
	sfr = [math.inf] * n
	sfl[0] = a[0][1]
	for i in range(1, n):
		sfl[i] = min(sfl[i - 1], a[i][1])
	sfr[n - 1] = a[n - 1][1]
	for i in range(n - 2, -1, -1):
		sfr[i] = min(sfr[i + 1], a[i][1])
	res = math.inf
	for i in range(n - 1):
		al = (a[i][0] - a[0][0]) * (bfl[i] - sfl[i])
		ar = (a[n - 1][0] - a[i + 1][0]) * (bfr[i + 1] - sfr[i + 1])
		res = min(res, al + ar)
	if res == math.inf:
		return 0
	return res

def dh(n, a):
	a.sort(key=lambda x: x[1])
	bfl = [-1] * n
	bfr = [-1] * n
	bfl[0] = a[0][0]
	for i in range(1, n):
		bfl[i] = max(bfl[i - 1], a[i][0])
	bfr[n - 1] = a[n - 1][0]
	for i in range(n - 2, -1, -1):
		bfr[i] = max(bfr[i + 1], a[i][0])
	sfl = [math.inf] * n
	sfr = [math.inf] * n
	sfl[0] = a[0][0]
	for i in range(1, n):
		sfl[i] = min(sfl[i - 1], a[i][0])
	sfr[n - 1] = a[n - 1][0]
	for i in range(n - 2, -1, -1):
		sfr[i] = min(sfr[i + 1], a[i][0])
	res = math.inf
	for i in range(n - 1):
		al = (a[i][1] - a[0][1]) * (bfl[i] - sfl[i])
		ar = (a[n - 1][1] - a[i + 1][1]) * (bfr[i + 1] - sfr[i + 1])
		res = min(res, al + ar)
	if res == math.inf:
		return 0
	return res

def func(n, a):
	dividevertically = dv(n, a)
	dividehori = dh(n, a)
	return min(dividehori, dividevertically)
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(tuple(map(int, input().split())))
	print(func(n, a))


test = int(input())
for i in range(0, test):
	n = int(input())
	finall = []
	for i in range(0, n):
		lis = list(map(int, input().split()))
		finall.append(lis)
	if n <= 2:
		print(0)
		continue
	final = sorted(finall)
	max_pref = [final[0][1]]
	min_pref = [final[0][1]]
	max_suf = []
	min_suf = []
	for i in range(1, len(final)):
		if final[i][1] > max_pref[i - 1]:
			max_pref.append(final[i][1])
			max_suf.append(0)
			min_suf.append(0)
		else:
			max_pref.append(max_pref[i - 1])
			max_suf.append(0)
			min_suf.append(0)
		if final[i][1] < min_pref[i - 1]:
			min_pref.append(final[i][1])
			max_suf.append(0)
			min_suf.append(0)
		else:
			min_pref.append(min_pref[i - 1])
			max_suf.append(0)
			min_suf.append(0)
	max_suf[len(final) - 1] = final[len(final) - 1][1]
	min_suf[len(final) - 1] = final[len(final) - 1][1]
	for j in range(len(final) - 2, -1, -1):
		if final[j][1] > max_suf[j + 1]:
			max_suf[j] = final[j][1]
		else:
			max_suf[j] = max_suf[j + 1]
		if final[j][1] < min_suf[j + 1]:
			min_suf[j] = final[j][1]
		else:
			min_suf[j] = min_suf[j + 1]
	mini = (final[len(final) - 1][0] - final[0][0]) * (max_pref[len(final) - 1] - min_pref[len(final) - 1])
	for i in range(0, len(final) - 1):
		width1 = final[i][0] - final[0][0]
		height1 = max_pref[i] - min_pref[i]
		width2 = final[len(final) - 1][0] - final[i + 1][0]
		height2 = max_suf[i + 1] - min_suf[i + 1]
		ans1 = width1 * height1 + width2 * height2
		if ans1 < mini:
			mini = ans1
	final = sorted(finall, key=lambda x: x[1])
	max_pref = [final[0][0]]
	min_pref = [final[0][0]]
	max_suf = []
	min_suf = []
	for i in range(1, len(final)):
		if final[i][0] > max_pref[i - 1]:
			max_pref.append(final[i][0])
			max_suf.append(0)
			min_suf.append(0)
		else:
			max_pref.append(max_pref[i - 1])
			max_suf.append(0)
			min_suf.append(0)
		if final[i][0] < min_pref[i - 1]:
			min_pref.append(final[i][0])
			max_suf.append(0)
			min_suf.append(0)
		else:
			min_pref.append(min_pref[i - 1])
			max_suf.append(0)
			min_suf.append(0)
	max_suf[len(final) - 1] = final[len(final) - 1][0]
	min_suf[len(final) - 1] = final[len(final) - 1][0]
	for j in range(len(final) - 2, -1, -1):
		if final[j][0] > max_suf[j + 1]:
			max_suf[j] = final[j][0]
		else:
			max_suf[j] = max_suf[j + 1]
		if final[j][0] < min_suf[j + 1]:
			min_suf[j] = final[j][0]
		else:
			min_suf[j] = min_suf[j + 1]
	mini2 = (final[len(final) - 1][1] - final[0][1]) * (max_pref[len(final) - 1] - min_pref[len(final) - 1])
	for i in range(0, len(final) - 1):
		width1 = max_pref[i] - min_pref[i]
		height1 = final[i][1] - final[0][1]
		width2 = max_suf[i + 1] - min_suf[i + 1]
		height2 = final[len(final) - 1][1] - final[i + 1][1]
		ans1 = width1 * height1 + width2 * height2
		if ans1 < mini2:
			mini2 = ans1
	print(min(mini, mini2))


import collections
import itertools
import sys
import numpy as np

def singleArea(n, points):
	if n == 1:
		return 0
	points.sort(key=lambda x: x[1])
	(pr, pst) = (collections.deque(), collections.deque())
	(mnx, mny, mxx, mxy) = (points[0][0], points[0][1], points[0][0], points[0][1])
	for i in range(n - 1):
		(x, y) = points[i]
		if x < mnx:
			mnx = x
		if y < mny:
			mny = y
		if x > mxx:
			mxx = x
		if y > mxy:
			mxy = y
		pr.append([abs(mxx - mnx), abs(mny - mxy)])
	(mnx, mny, mxx, mxy) = (points[-1][0], points[-1][1], points[-1][0], points[-1][1])
	points.reverse()
	for i in range(n - 1):
		(x, y) = points[i]
		if x < mnx:
			mnx = x
		if y < mny:
			mny = y
		if x > mxx:
			mxx = x
		if y > mxy:
			mxy = y
		pst.appendleft([abs(mxx - mnx), abs(mny - mxy)])
	ar = sys.maxsize
	for (x, y) in itertools.zip_longest(pr, pst):
		temp = x[0] * x[1] + y[0] * y[1]
		if temp < ar:
			ar = temp
	return ar

def dualArea(n: int, points: list):
	if n == 1:
		return 0
	points.sort()
	(pr, pst) = (collections.deque(), collections.deque())
	(mnx, mny, mxx, mxy) = (points[0][0], points[0][1], points[0][0], points[0][1])
	for i in range(n - 1):
		(x, y) = points[i]
		if x < mnx:
			mnx = x
		if y < mny:
			mny = y
		if x > mxx:
			mxx = x
		if y > mxy:
			mxy = y
		pr.append([abs(mxx - mnx), abs(mny - mxy)])
	(mnx, mny, mxx, mxy) = (points[-1][0], points[-1][1], points[-1][0], points[-1][1])
	points.reverse()
	for i in range(n - 1):
		(x, y) = points[i]
		if x < mnx:
			mnx = x
		if y < mny:
			mny = y
		if x > mxx:
			mxx = x
		if y > mxy:
			mxy = y
		pst.appendleft([abs(mxx - mnx), abs(mny - mxy)])
	ar = sys.maxsize
	for (x, y) in itertools.zip_longest(pr, pst):
		temp = x[0] * x[1] + y[0] * y[1]
		if temp < ar:
			ar = temp
	return ar
for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	print(min(singleArea(n, arr), dualArea(n, arr)))


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
mini = -2 * pow(10, 9)
maxi = -1 * mini
from collections import defaultdict

def smallareas(hash1, a):
	l = []
	m = []
	for i in hash1:
		temp = hash1[i]
		l.append([i, temp[0]])
		m.append([i, temp[-1]])
	l.sort()
	m.sort()
	for i in range(1, a):
		l[i][1] = min(l[i][1], l[i - 1][1])
		m[i][1] = max(m[i][1], m[i - 1][1])
	left = mini
	right = maxi
	top = mini
	bottom = maxi
	top = max(top, l[-1][0])
	bottom = min(bottom, l[-1][0])
	left = max(left, hash1[l[-1][0]][0])
	right = min(right, hash1[l[-1][0]][-1])
	breadth = right - left
	length = top - bottom
	lower = length * breadth
	top1 = l[-2][0]
	bottom1 = l[0][0]
	left1 = l[-2][-1]
	right1 = m[-2][-1]
	breadth = right1 - left1
	length = top1 - bottom1
	upper = length * breadth
	ans1 = lower + upper
	top = l[-1][0]
	for i in range(a - 3, -1, -1):
		left = min(left, hash1[l[i + 1][0]][0])
		right = max(right, hash1[l[i + 1][0]][-1])
		bottom = l[i + 1][0]
		breadth = right - left
		length = top - bottom
		lower = length * breadth
		top1 = l[i][0]
		bottom1 = l[0][0]
		left1 = l[i][-1]
		right1 = m[i][-1]
		breadth = right1 - left1
		length = top1 - bottom1
		upper = length * breadth
		ans1 = min(ans1, lower + upper)
	return ans1
for _ in range(int(input())):
	n = int(input())
	(hash1, hash2) = (defaultdict(list), defaultdict(list))
	for i in range(n):
		(a, b) = map(int, input().split())
		hash1[a].append(b)
		hash2[b].append(a)
	(a, b) = (len(hash1), len(hash2))
	if a > 2 and b > 2:
		for i in hash1:
			hash1[i].sort()
		for i in hash2:
			hash2[i].sort()
		print(min(smallareas(hash1, a), smallareas(hash2, b)))
	else:
		print(0)


def maximum(arr1, index):
	return max(arr1, key=lambda a: a[not index])[not index]

def minimum(arr1, index):
	return min(arr1, key=lambda a: a[not index])[not index]

def prefix_suffix(arr):
	prefix_min = [0] * (len(arr) + 2)
	suffix_min = [0] * (len(arr) + 2)
	prefix_max = [0] * (len(arr) + 2)
	suffix_max = [0] * (len(arr) + 2)
	prefix_min[0] = float('inf')
	suffix_min[-1] = float('inf')
	for i in range(1, len(arr) + 1):
		prefix = arr[i - 1]
		suffix = arr[-i]
		prefix_min[i] = min(prefix_min[i - 1], prefix)
		prefix_max[i] = max(prefix_max[i - 1], prefix)
		suffix_min[-i - 1] = min(suffix_min[-i], suffix)
		suffix_max[-i - 1] = max(suffix_max[-i], suffix)
	return (prefix_min, prefix_max, suffix_min, suffix_max)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		point = list(map(int, input().split()))
		arr.append(point)
	if n == 1:
		print(0)
	else:
		x_sort = sorted(arr, key=lambda a: a[0])
		y_sort = sorted(arr, key=lambda b: b[1])
		area_x = float('inf')
		x = prefix_suffix(list(map(lambda a: a[1], x_sort)))
		prefix_min_x = x[0]
		prefix_max_x = x[1]
		suffix_min_x = x[2]
		suffix_max_x = x[3]
		for i in range(1, n):
			x_1 = (prefix_max_x[i] - prefix_min_x[i]) * (x_sort[i - 1][0] - x_sort[0][0])
			x_2 = (suffix_max_x[i + 1] - suffix_min_x[i + 1]) * (x_sort[-1][0] - x_sort[i][0])
			area_x = min(area_x, x_1 + x_2)
		area_y = float('inf')
		y = prefix_suffix(list(map(lambda a: a[0], y_sort)))
		prefix_min_y = y[0]
		prefix_max_y = y[1]
		suffix_min_y = y[2]
		suffix_max_y = y[3]
		for i in range(1, n):
			y_1 = (prefix_max_y[i] - prefix_min_y[i]) * (y_sort[i - 1][1] - y_sort[0][1])
			y_2 = (suffix_max_y[i + 1] - suffix_min_y[i + 1]) * (y_sort[-1][1] - y_sort[i][1])
			area_y = min(area_y, y_1 + y_2)
		print(int(min(area_x, area_y)))


def height(A, n):
	a = []
	mn = 1000000000.0 + 1
	mx = -1
	for i in range(n - 1):
		if A[i] < mn:
			mn = A[i]
		if A[i] > mx:
			mx = A[i]
		a.append(mx - mn)
	return a

def sort(L):
	return sorted(L, key=lambda x: x[0])

def fun(A, n):
	l2 = []
	for i in range(n):
		l2.append(A[i][1])
	h1 = height(l2, n)
	h2 = height(l2[::-1], n)
	h2 = h2[::-1]
	area = 1e+19 + 1
	for i in range(n - 1):
		temp = h1[i] * (A[i][0] - A[0][0]) + h2[i] * (A[-1][0] - A[i + 1][0])
		if temp < area:
			area = temp
	if area == 1e+19:
		return 0
	else:
		return area
for i in range(int(input())):
	n = int(input())
	(Lx, Ly) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		Lx.append([a, b])
		Ly.append([b, a])
	Lx = sort(Lx)
	Ly = sort(Ly)
	area1 = fun(Lx, n)
	area2 = fun(Ly, n)
	print(min(area1, area2))


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from math import inf
from sys import stdin
read_line = lambda : stdin.readline().strip()
read_point = lambda : tuple(map(int, read_line().split()))
box_area = lambda left, right: (right[1] - left[1]) * (right[0] - left[0])

def solve(p):
	sort_by_x = sorted(p, key=lambda x: (x[0], -x[1]))
	box_left = []
	(min_x, min_y) = sort_by_x[0]
	(max_x, max_y) = sort_by_x[0]
	for (x, y) in sort_by_x:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		box_left.append([(min_x, min_y), (max_x, max_y)])
	box_right = []
	(min_x, min_y) = sort_by_x[-1]
	(max_x, max_y) = sort_by_x[-1]
	for (x, y) in sort_by_x[::-1]:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		box_right.append([(min_x, min_y), (max_x, max_y)])
	area = inf
	for i in range(len(sort_by_x)):
		area_left = box_area(*box_left[i])
		area_right = box_area(*box_right[len(sort_by_x) - 2 - i])
		new_area = area_left + area_right
		if new_area < area:
			area = new_area
	return area

def main():
	for _ in range(int(input())):
		N = int(input())
		p = [read_point() for _ in range(N)]
		x = solve(p)
		y = solve([(y, x) for (x, y) in p])
		solution = min(x, y)
		print(solution)
main()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	(row, col) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		col.append([a, b])
		row.append([a, b])
	if n <= 2:
		print(0)
		continue
	row = sorted(row, key=lambda x: x[0])
	col = sorted(col, key=lambda x: x[1])
	(pre_min, pre_max, suff_min, suff_max) = ([math.inf] * n, [-1] * n, [math.inf] * n, [-1] * n)
	(pre_min[0], pre_max[0]) = (row[0][1], row[0][1])
	for i in range(1, n):
		pre_min[i] = min(pre_min[i - 1], row[i][1])
		pre_max[i] = max(pre_max[i - 1], row[i][1])
	(suff_min[-1], suff_max[-1]) = (row[-1][1], row[-1][1])
	for i in range(n - 2, -1, -1):
		suff_min[i] = min(suff_min[i + 1], row[i][1])
		suff_max[i] = max(suff_max[i + 1], row[i][1])
	(ypre_min, ypre_max, ysuff_min, ysuff_max) = ([math.inf] * n, [-1] * n, [math.inf] * n, [-1] * n)
	(ypre_min[0], ypre_max[0]) = (col[0][0], col[0][0])
	(ysuff_min[-1], ysuff_max[-1]) = (col[-1][0], col[-1][0])
	for i in range(1, n):
		ypre_min[i] = min(ypre_min[i - 1], col[i][0])
		ypre_max[i] = max(ypre_max[i - 1], col[i][0])
	for i in range(n - 2, -1, -1):
		ysuff_min[i] = min(ysuff_min[i + 1], col[i][0])
		ysuff_max[i] = max(ysuff_max[i + 1], col[i][0])
	area1 = math.inf
	for i in range(n - 1):
		x1_1 = pre_max[i] - pre_min[i]
		x1_2 = row[i][0] - row[0][0]
		x2_1 = suff_max[i + 1] - suff_min[i + 1]
		x2_2 = row[-1][0] - row[i + 1][0]
		area1 = min(area1, x1_1 * x1_2 + x2_1 * x2_2)
	area2 = math.inf
	for i in range(n - 1):
		x1_1 = ypre_max[i] - ypre_min[i]
		x1_2 = col[i][1] - col[0][1]
		x2_1 = ysuff_max[i + 1] - ysuff_min[i + 1]
		x2_2 = col[-1][1] - col[i + 1][1]
		area2 = min(area2, x1_1 * x1_2 + x2_1 * x2_2)
	print(min(area1, area2))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = set()
	for __ in range(n):
		a.add(tuple(map(int, input().split())))
	a = list(a)
	a.sort()
	n = len(a)
	if n <= 2:
		print(0)
		continue
	mp = defaultdict(list)
	for x in a:
		mp[x[0]].append(x[1])
	keys = list(mp.keys())
	keys_len = len(keys)
	for key in keys:
		if len(mp[key]) > 1:
			mp[key] = [min(mp[key]), max(mp[key])]
	pre = []
	maxy = -1
	miny = 10 ** 9 + 1
	for i in range(keys_len):
		if i == 0:
			if len(mp[keys[i]]) == 1:
				maxy = mp[keys[i]][0]
				miny = mp[keys[i]][0]
			else:
				maxy = max(mp[keys[i]][0], mp[keys[i]][1])
				miny = min(mp[keys[i]][0], mp[keys[i]][1])
		elif len(mp[keys[i]]) == 1:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			maxy = max(aa, ba, ca)
			miny = min(aa, ba, ca)
		else:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			da = mp[keys[i]][1]
			maxy = max(aa, ba, ca, da)
			miny = min(aa, ba, ca, da)
		pre.append((miny, maxy))
	post = []
	maxy = -1
	miny = 10 ** 9 + 1
	for i in range(keys_len - 1, -1, -1):
		if i == keys_len - 1:
			if len(mp[keys[i]]) == 1:
				maxy = mp[keys[i]][0]
				miny = mp[keys[i]][0]
			else:
				maxy = max(mp[keys[i]][0], mp[keys[i]][1])
				miny = min(mp[keys[i]][0], mp[keys[i]][1])
		elif len(mp[keys[i]]) == 1:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			maxy = max(aa, ba, ca)
			miny = min(aa, ba, ca)
		else:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			da = mp[keys[i]][1]
			maxy = max(aa, ba, ca, da)
			miny = min(aa, ba, ca, da)
		post.append((miny, maxy))
	post = post[::-1]
	area = 10 ** 20
	for i in range(keys_len - 1):
		area = min(area, (pre[i][1] - pre[i][0]) * (keys[i] - keys[0]) + (post[i + 1][1] - post[i + 1][0]) * (keys[-1] - keys[i + 1]))
	b = []
	for x in a:
		b.append((x[1], x[0]))
	b.sort()
	n = len(b)
	mp = defaultdict(list)
	for x in b:
		mp[x[0]].append(x[1])
	keys = list(mp.keys())
	keys_len = len(keys)
	for key in keys:
		if len(mp[key]) > 1:
			mp[key] = [min(mp[key]), max(mp[key])]
	pre = []
	maxy = -1
	miny = 10 ** 9 + 1
	for i in range(keys_len):
		if i == 0:
			if len(mp[keys[i]]) == 1:
				maxy = mp[keys[i]][0]
				miny = mp[keys[i]][0]
			else:
				maxy = max(mp[keys[i]][0], mp[keys[i]][1])
				miny = min(mp[keys[i]][0], mp[keys[i]][1])
		elif len(mp[keys[i]]) == 1:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			maxy = max(aa, ba, ca)
			miny = min(aa, ba, ca)
		else:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			da = mp[keys[i]][1]
			maxy = max(aa, ba, ca, da)
			miny = min(aa, ba, ca, da)
		pre.append((miny, maxy))
	post = []
	maxy = -1
	miny = 10 ** 9 + 1
	for i in range(keys_len - 1, -1, -1):
		if i == keys_len - 1:
			if len(mp[keys[i]]) == 1:
				maxy = mp[keys[i]][0]
				miny = mp[keys[i]][0]
			else:
				maxy = max(mp[keys[i]][0], mp[keys[i]][1])
				miny = min(mp[keys[i]][0], mp[keys[i]][1])
		elif len(mp[keys[i]]) == 1:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			maxy = max(aa, ba, ca)
			miny = min(aa, ba, ca)
		else:
			aa = maxy
			ba = miny
			ca = mp[keys[i]][0]
			da = mp[keys[i]][1]
			maxy = max(aa, ba, ca, da)
			miny = min(aa, ba, ca, da)
		post.append((miny, maxy))
	post = post[::-1]
	for i in range(keys_len - 1):
		area = min(area, (pre[i][1] - pre[i][0]) * (keys[i] - keys[0]) + (post[i + 1][1] - post[i + 1][0]) * (keys[-1] - keys[i + 1]))
	print(area)


def area(rectangle):
	[A, B] = rectangle
	return abs(B[0] - A[0]) * abs(B[1] - A[1])

def solve(points):
	if len(points) <= 2:
		return 0
	points_x = sorted(points, key=lambda x: x[0])
	ymx = {}
	for p in points_x:
		if p[0] not in ymx:
			ymx[p[0]] = [p[1], p[1]]
			continue
		if p[1] < ymx[p[0]][0]:
			ymx[p[0]][0] = p[1]
		elif p[1] > ymx[p[0]][1]:
			ymx[p[0]][1] = p[1]
	y_right = {points_x[-1][0]: ymx[points_x[-1][0]]}
	for i in range(N - 2, -1, -1):
		y_right[points_x[i][0]] = [min(y_right[points_x[i + 1][0]][0], ymx[points_x[i][0]][0]), max(y_right[points_x[i + 1][0]][1], ymx[points_x[i][0]][1])]
	r1_x = [points_x[0][0], points_x[0][0]]
	r2_x = [points_x[-1][0], points_x[-1][0]]
	r1_y = [ymx[points_x[0][0]][0], ymx[points_x[0][0]][1]]
	r2_y = [y_right[points_x[-1][0]][0], y_right[points_x[-1][0]][1]]
	area_max = float('inf')
	for i in range(N - 1):
		r1_x[1] = points_x[i][0]
		r2_x[0] = points_x[i + 1][0]
		if r1_y[0] > ymx[points_x[i][0]][0]:
			r1_y[0] = ymx[points_x[i][0]][0]
		if r1_y[1] < ymx[points_x[i][0]][1]:
			r1_y[1] = ymx[points_x[i][0]][1]
		r2_y = y_right[points_x[i + 1][0]]
		new_area = area([[r1_x[0], r1_y[0]], [r1_x[1], r1_y[1]]]) + area([[r2_x[0], r2_y[0]], [r2_x[1], r2_y[1]]])
		if new_area < area_max:
			area_max = new_area
	points = [[y, x] for [x, y] in points]
	points_x = sorted(points, key=lambda x: x[0])
	ymx = {}
	for p in points_x:
		if p[0] not in ymx:
			ymx[p[0]] = [p[1], p[1]]
			continue
		if p[1] < ymx[p[0]][0]:
			ymx[p[0]][0] = p[1]
		elif p[1] > ymx[p[0]][1]:
			ymx[p[0]][1] = p[1]
	y_right = {points_x[-1][0]: ymx[points_x[-1][0]]}
	for i in range(N - 2, -1, -1):
		y_right[points_x[i][0]] = [min(y_right[points_x[i + 1][0]][0], ymx[points_x[i][0]][0]), max(y_right[points_x[i + 1][0]][1], ymx[points_x[i][0]][1])]
	r1_x = [points_x[0][0], points_x[0][0]]
	r2_x = [points_x[-1][0], points_x[-1][0]]
	r1_y = [ymx[points_x[0][0]][0], ymx[points_x[0][0]][1]]
	r2_y = [y_right[points_x[-1][0]][0], y_right[points_x[-1][0]][1]]
	full_rect = [[points_x[0][0], y_right[points[0][0]][0]], [points_x[-1][0], y_right[points[0][0]][1]]]
	for i in range(N - 1):
		r1_x[1] = points_x[i][0]
		r2_x[0] = points_x[i + 1][0]
		if r1_y[0] > ymx[points_x[i][0]][0]:
			r1_y[0] = ymx[points_x[i][0]][0]
		if r1_y[1] < ymx[points_x[i][0]][1]:
			r1_y[1] = ymx[points_x[i][0]][1]
		r2_y = y_right[points_x[i + 1][0]]
		new_area = area([[r1_x[0], r1_y[0]], [r1_x[1], r1_y[1]]]) + area([[r2_x[0], r2_y[0]], [r2_x[1], r2_y[1]]])
		if new_area < area_max:
			area_max = new_area
	return area_max
for _ in range(int(input())):
	N = int(input())
	points = [[int(x) for x in input().split()] for i in range(N)]
	print(solve(points))


from collections import defaultdict

def neginf():
	return float('-inf')

def inf():
	return float('inf')

def solve(p):
	(minX, maxX) = (defaultdict(inf), defaultdict(neginf))
	(minY, maxY) = (defaultdict(inf), defaultdict(neginf))
	for (x, y) in p:
		minX[y] = min(minX[y], x)
		maxX[y] = max(maxX[y], x)
		minY[x] = min(minY[x], y)
		maxY[x] = max(maxY[x], y)
	X = list(minY.keys())
	Y = list(minX.keys())
	X.sort()
	Y.sort()
	area = inf()
	(pref, suff) = ([], [])
	(mn, mx) = (inf(), neginf())
	for x in X:
		(mn, mx) = (min(mn, minY[x]), max(mx, maxY[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (inf(), neginf())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, minY[x]), max(mx, maxY[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (inf(), neginf())
	for y in Y:
		(mn, mx) = (min(mn, minX[y]), max(mx, maxX[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (inf(), neginf())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, minX[y]), max(mx, maxX[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
T = int(input())
for _ in range(T):
	N = int(input())
	arr = []
	for i in range(N):
		List = list(map(int, input().split()))
		arr.append(List)
	val = solve(arr)
	print(val)


import math
MAX = 0
MIN = 1

def task():
	n = int(input())
	points = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		points.append([a, b])
	if n <= 2:
		return 0
	points.sort(key=lambda x: x[0])
	mx = -1
	mn = math.inf
	leftRect = list()
	for p in points:
		mx = max(mx, p[1])
		mn = min(mn, p[1])
		leftRect.append((mx, mn))
	mx = -1
	mn = math.inf
	minArea = math.inf
	for i in range(n - 1, 0, -1):
		p = points[i]
		mx = max(mx, p[1])
		mn = min(mn, p[1])
		areaRight = (points[-1][0] - p[0]) * (mx - mn)
		areaLeft = (points[i - 1][0] - points[0][0]) * (leftRect[i - 1][MAX] - leftRect[i - 1][MIN])
		minArea = min(minArea, areaLeft + areaRight)
	points.sort(key=lambda x: x[1])
	mx = -1
	mn = math.inf
	bottomRect = list()
	for p in points:
		mx = max(mx, p[0])
		mn = min(mn, p[0])
		bottomRect.append((mx, mn))
	mx = -1
	mn = math.inf
	for i in range(n - 1, 0, -1):
		p = points[i]
		mx = max(mx, p[0])
		mn = min(mn, p[0])
		areaTop = (points[-1][1] - p[1]) * (mx - mn)
		areaBottom = (points[i - 1][1] - points[0][1]) * (bottomRect[i - 1][MAX] - bottomRect[i - 1][MIN])
		minArea = min(minArea, areaBottom + areaTop)
	return minArea
for _ in range(int(input())):
	print(task())


from collections import defaultdict

def INF():
	return float('inf')

def NINF():
	return float('-inf')

def solve(P):
	(min_X, max_X) = (defaultdict(INF), defaultdict(NINF))
	(min_Y, max_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in P:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		suff.append((X[-1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
T = int(input())
for _ in range(T):
	N = int(input())
	P = []
	for i in range(N):
		li = list(map(int, input().split()))
		P.append(li)
	ans = solve(P)
	print(ans)


from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')
t = int(input())
while t:
	t -= 1
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	(min_X, max_X) = (defaultdict(INF), defaultdict(NINF))
	(min_Y, max_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(minn, maxx) = (INF(), NINF())
	for x in X:
		(minn, maxx) = (min(minn, min_Y[x]), max(maxx, max_Y[x]))
		pref.append((x - X[0]) * (maxx - minn))
	(minn, maxx) = (INF(), NINF())
	for x in X[-1::-1]:
		(minn, maxx) = (min(minn, min_Y[x]), max(maxx, max_Y[x]))
		suff.append((X[-1] - x) * (maxx - minn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(minn, maxx) = (INF(), NINF())
	for y in Y:
		(minn, maxx) = (min(minn, min_X[y]), max(maxx, max_X[y]))
		pref.append((y - Y[0]) * (maxx - minn))
	(minn, maxx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(minn, maxx) = (min(minn, min_X[y]), max(maxx, max_X[y]))
		suff.append((Y[-1] - y) * (maxx - minn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	print(area)


def func(arr):
	n = len(arr)
	if n == 1:
		return 0
	(L1, R1, L2, R2) = ([2000000000] * (n + 1), [2000000000] * (n + 1), [-2000000000] * (n + 1), [-2000000000] * (n + 1))
	res = 2000000000000000000
	arr.sort()
	for i in range(0, n):
		L1[i] = arr[i][1]
		L2[i] = arr[i][1]
		if i:
			L1[i] = min(L1[i - 1], L1[i])
			L2[i] = max(L2[i - 1], L2[i])
	for i in range(n - 1, -1, -1):
		R1[i] = arr[i][1]
		R2[i] = arr[i][1]
		R1[i] = min(R1[i + 1], R1[i])
		R2[i] = max(R2[i + 1], R2[i])
	for i in range(0, n - 1):
		res = min(res, (L2[i] - L1[i]) * (arr[i][0] - arr[0][0]) + (R2[i + 1] - R1[i + 1]) * (arr[n - 1][0] - arr[i + 1][0]))
	return res
tc = int(input())
for i in range(tc):
	n = int(input())
	arr1 = [[0 for i in range(2)] for j in range(n)]
	arr2 = [[0 for i in range(2)] for j in range(n)]
	for i in range(0, n):
		(arr1[i][0], arr1[i][1]) = list(map(int, input().split()))
		arr2[i][0] = arr1[i][1]
		arr2[i][1] = arr1[i][0]
	res1 = func(arr1)
	res2 = func(arr2)
	print(min(res1, res2))


def getmm(points, c):
	ans = [(points[0][c], points[0][c])]
	ansr = [(points[-1][c], points[-1][c])]
	for p in points[1:]:
		ans.append((min(p[c], ans[-1][0]), max(p[c], ans[-1][1])))
	for p in points[-2::-1]:
		ansr.append((min(p[c], ansr[-1][0]), max(p[c], ansr[-1][1])))
	return (ans, ansr[::-1])
te = int(input())
while te != 0:
	te -= 1
	points = []
	n = int(input())
	for i in range(n):
		points.append(list(map(int, input().split())))
	p_x = sorted(points, key=lambda x: x[0])
	p_y = sorted(points, key=lambda x: x[1])
	(mmx, mmx_r) = getmm(p_y, 0)
	(mmy, mmy_r) = getmm(p_x, 1)
	ans = float('inf')
	(l, r) = (p_x[0][0], p_x[-1][0])
	for i in range(1, n):
		r1 = (p_x[i - 1][0] - l) * (mmy[i - 1][1] - mmy[i - 1][0])
		r2 = (r - p_x[i][0]) * (mmy_r[i][1] - mmy_r[i][0])
		ans = min(r1 + r2, ans)
	(b, t) = (p_y[0][1], p_y[-1][1])
	for i in range(1, n):
		r1 = (p_y[i - 1][1] - b) * (mmx[i - 1][1] - mmx[i - 1][0])
		r2 = (t - p_y[i][1]) * (mmx_r[i][1] - mmx_r[i][0])
		ans = min(r1 + r2, ans)
	print(0 if ans == float('inf') else ans)


import sys
import math
from collections import *
from queue import *
from bisect import *
MOD = int(1000000000.0 + 7)
inf = float('inf')
ninf = float('-inf')
input = sys.stdin.readline

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

def infInitialise():
	return defaultdict(lambda : inf)

def negInitialise():
	return defaultdict(lambda : ninf)

def helper(res):
	(minm_X, maxm_X, minm_Y, maxm_Y) = (infInitialise(), negInitialise(), infInitialise(), negInitialise())
	for (x, y) in res:
		minm_X[y] = min(minm_X[y], x)
		maxm_X[y] = max(maxm_X[y], x)
		ml = min(minm_X[y], maxm_X[y])
		minm_Y[x] = min(minm_Y[x], y)
		maxm_Y[x] = max(maxm_Y[x], y)
	(X, Y, combinedArea) = ([], [], inf)
	for k in minm_Y.keys():
		X.append(k)
	for k in minm_X.keys():
		Y.append(k)
	(mn, mx, preArr, sufArr, fl) = (inf, ninf, [], [], 0)
	X.sort()
	Y.sort()
	for x in X:
		if minm_Y[x] <= mn:
			mn = minm_Y[x]
		if mx < maxm_Y[x]:
			mx = max(mx, maxm_Y[x])
		preArr.append((x - X[0]) * (mx - mn))
	(mn, mx, fl, X_axis) = (inf, -inf, 0, X[-1::-1])
	for x in X_axis:
		if minm_Y[x] <= mn:
			mn = minm_Y[x]
		if mx < maxm_Y[x]:
			mx = max(mx, maxm_Y[x])
		sufArr.append((X[0 - 1] - x) * (mx - mn))
	temp = []
	for k in range(len(sufArr) - 1, -1, -1):
		temp.append(sufArr[k])
	temp.append(0)
	(sufArr, mn, mx, fl) = (temp, inf, ninf, 0)
	for i in range(len(X)):
		suk = preArr[i - 1 + 1] + sufArr[i + 1]
		combinedArea = min(combinedArea, suk)
	(prefArr, sufArr, fl) = ([], [], 0)
	for y in Y:
		cal1 = y - Y[0]
		(mn, mx) = (min(mn, minm_X[y]), max(mx, maxm_X[y]))
		cal2 = mx - mn
		prefArr.append(cal1 * cal2)
	(mn, mx, fl, Y_axis) = (inf, ninf, 0, Y[-1::-1])
	for y in Y_axis:
		cal1 = Y[-1] - y
		(mn, mx) = (min(mn, minm_X[y]), max(mx, maxm_X[y]))
		cal2 = mx - mn
		sufArr.append(cal1 * cal2)
	temp = []
	for k in range(len(sufArr) - 1, -1, -1):
		temp.append(sufArr[k])
	temp.append(0)
	sufArr = temp
	nY = len(Y)
	for i in range(nY):
		suk = prefArr[i] + sufArr[i + 1]
		combinedArea = min(combinedArea, suk)
	return combinedArea
for _ in range(int(input())):
	res = []
	(n,) = ii()
	for i in range(n):
		arr = ii()
		res.append(arr)
	ans = helper(res)
	print(ans)


import sys
import time

def timebata():
	return time.perf_counter()

def mini(x, y):
	if x < y:
		return x
	else:
		return y

def maxa(x, y):
	if x > y:
		return x
	else:
		return y

def miaaaji(arr, n):
	arr = [-1 for i in range(n)]
	return arr
for _ in range(int(input())):
	points = []
	xmin = sys.maxsize - 2
	xmax = 0
	ymin = sys.maxsize - 2
	ymax = 0
	n = int(input())
	for ii in range(n):
		(x, y) = map(int, input().split())
		points.append((x, y))
		if x > xmax:
			xmax = x
		xmin = mini(x, xmin)
		ymax = maxa(y, ymax)
		if y > ymin:
			a11 = timebata()
			ymin = y
	if n == 1:
		t11 = timebata()
		print(0)
	else:
		t22 = timebata()
		points = sorted(points, key=lambda x: (x[0], x[1]))
		t33 = timebata()
		lydpmin = []
		for i in range(n):
			lydpmin.append(-1)
		lydpmax = []
		for i in range(n):
			lydpmax.append(-1)
		lulu8 = points[0][1]
		lydpmin[0] = lulu8
		lydpmax[0] = lulu8
		for i in range(1, n):
			at1 = max(points[i][1], lydpmax[i - 1])
			lydpmax[i] = at1
			at2 = min(points[i][1], lydpmin[i - 1])
			lydpmin[i] = at2
		rampam = -1
		e1 = timebata()
		rydpmin = []
		for i in range(n):
			rydpmin.append(-1)
		e2 = timebata()
		rydpmax = []
		for i in range(n):
			rydpmax.append(-1)
		lulu1 = points[-1][1]
		rydpmin[-1] = lulu1
		rydpmax[-1] = lulu1
		for i in range(n - 2, -1, -1):
			ar5 = max(points[i][1], rydpmax[i + 1])
			rydpmax[i] = ar5
			ar6 = min(points[i][1], rydpmin[i + 1])
			rydpmin[i] = ar6
		lxdpmin = []
		for i in range(n):
			lxdpmin.append(-1)
		lxdpmax = []
		for i in range(n):
			lxdpmax.append(-1)
		lulu = points[0][0]
		lxdpmin[0] = lulu
		lxdpmax[0] = lulu
		for i in range(1, n):
			bb = max(points[i][0], lxdpmax[i - 1])
			lxdpmax[i] = bb
			bb1 = min(points[i][0], lxdpmin[i - 1])
			lxdpmin[i] = bb1
		rxdpmin = []
		for i in range(n):
			rxdpmin.append(-1)
		rxdpmax = []
		for i in range(n):
			rxdpmax.append(-1)
		lulu2 = points[-1][0]
		rxdpmin[-1] = lulu2
		rxdpmax[-1] = lulu2
		for i in range(n - 2, -1, -1):
			e3 = timebata()
			rxdpmax[i] = max(points[i][0], rxdpmax[i + 1])
			e4 = timebata()
			ll1 = points[i][0]
			rxdpmin[i] = min(ll1, rxdpmin[i + 1])
		f1 = lxdpmax[0] - lxdpmin[0]
		f2 = lydpmax[0] - lydpmin[0]
		ar1 = f1 * f2
		f3 = rxdpmax[1] - rxdpmin[1]
		f4 = rydpmax[1] - rydpmin[1]
		ar2 = f3 * f4
		fuddu = timebata()
		arsum = ar1 + ar2
		for i in range(1, n):
			tic = timebata()
			f11 = lxdpmax[i - 1] - lxdpmin[i - 1]
			f22 = lydpmax[i - 1] - lydpmin[i - 1]
			ar1 = f11 * f22
			f33 = rxdpmax[i] - rxdpmin[i]
			f44 = rydpmax[i] - rydpmin[i]
			ar2 = f33 * f44
			temparsum = ar1 + ar2
			if temparsum < arsum:
				arsum = temparsum
		chch = 0
		if arsum == chch:
			print(0)
		else:
			points = sorted(points, key=lambda x: (x[1], x[0]))
			z1 = timebata()
			lydpmin = []
			for i in range(n):
				lydpmin.append(-1)
			lydpmax = []
			for i in range(n):
				lydpmax.append(-1)
			lulu3 = points[0][1]
			lydpmin[0] = lulu3
			lydpmax[0] = lulu3
			for i in range(1, n):
				tac1 = timebata()
				lydpmax[i] = max(points[i][1], lydpmax[i - 1])
				tac2 = timebata()
				lydpmin[i] = min(points[i][1], lydpmin[i - 1])
			rydpmin = []
			for i in range(n):
				rydpmin.append(-1)
			rydpmax = []
			for i in range(n):
				rydpmax.append(-1)
			lulu5 = points[-1][1]
			rydpmin[-1] = lulu5
			rydpmax[-1] = lulu5
			for i in range(n - 2, -1, -1):
				an3 = max(points[i][1], rydpmax[i + 1])
				rydpmax[i] = an3
				an4 = min(points[i][1], rydpmin[i + 1])
				rydpmin[i] = an4
			lxdpmin = [-1]
			for i in range(n):
				lxdpmin.append(-1)
			lxdpmax = []
			for i in range(n):
				lxdpmax.append(-1)
			lulu6 = points[0][0]
			lxdpmin[0] = lulu6
			lxdpmax[0] = lulu6
			for i in range(1, n):
				an1 = max(points[i][0], lxdpmax[i - 1])
				lxdpmax[i] = an1
				an2 = min(points[i][0], lxdpmin[i - 1])
				lxdpmin[i] = an2
			rxdpmin = []
			for i in range(n):
				rxdpmin.append(-1)
			rxdpmax = []
			for i in range(n):
				rxdpmax.append(-1)
			lulu4 = points[-1][0]
			rxdpmin[-1] = lulu4
			rxdpmax[-1] = lulu4
			ppp = n - 2
			ccc = -1
			for i in range(ppp, -1, ccc):
				toc = timebata()
				pd1 = points[i][0]
				rxdpmax[i] = max(pd1, rxdpmax[i + 1])
				pd2 = min(points[i][0], rxdpmin[i + 1])
				rxdpmin[i] = pd2
			tic1 = timebata()
			nx1 = lxdpmax[0] - lxdpmin[0]
			toc2 = timebata()
			nx2 = lydpmax[0] - lydpmin[0]
			ar1 = nx1 * nx2
			nx3 = rxdpmax[1] - rxdpmin[1]
			nx4 = rydpmax[1] - rydpmin[1]
			ar2 = nx3 * nx4
			temparsum = ar1 + ar2
			if temparsum < arsum:
				pcr = timebata()
				arsum = temparsum
			for i in range(1, n):
				pcr1 = timebata()
				mkc1 = lxdpmax[i - 1] - lxdpmin[i - 1]
				mkc2 = lydpmax[i - 1] - lydpmin[i - 1]
				ar1 = mkc1 * mkc2
				mkc3 = rxdpmax[i] - rxdpmin[i]
				mkc4 = rydpmax[i] - rydpmin[i]
				ar2 = mkc3 * mkc4
				temparsum = ar1 + ar2
				if temparsum < arsum:
					arsum = temparsum
			print(arsum)


import collections
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	min_X = defaultdict(lambda : float('inf'))
	max_X = defaultdict(lambda : float('-inf'))
	min_Y = defaultdict(lambda : float('inf'))
	max_Y = defaultdict(lambda : float('-inf'))
	for i in range(n):
		(x, y) = map(int, input().split())
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	areax = float('inf')
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	local_y_max = float('-inf')
	local_y_min = float('inf')
	left_areas = []
	for i in X:
		local_y_max = max(max_Y[i], local_y_max)
		local_y_min = min(min_Y[i], local_y_min)
		area_left = (i - X[0]) * (local_y_max - local_y_min)
		left_areas.append(area_left)
	rev_X = X[-1::-1]
	local_y_max = float('-inf')
	local_y_min = float('inf')
	right_areas = []
	for i in rev_X:
		local_y_max = max(max_Y[i], local_y_max)
		local_y_min = min(min_Y[i], local_y_min)
		area_right = (X[-1] - i) * (local_y_max - local_y_min)
		right_areas.append(area_right)
	right_areas = right_areas[-1::-1]
	right_areas.append(0)
	for i in range(len(X)):
		areax = min(areax, left_areas[i] + right_areas[i + 1])
	local_x_max = float('-inf')
	local_x_min = float('inf')
	bottom_areas = []
	for i in Y:
		local_x_max = max(max_X[i], local_x_max)
		local_x_min = min(min_X[i], local_x_min)
		area_bottom = (i - Y[0]) * (local_x_max - local_x_min)
		bottom_areas.append(area_bottom)
	rev_Y = Y[-1::-1]
	local_x_max = float('-inf')
	local_x_min = float('inf')
	areay = float('inf')
	up_areas = []
	for i in rev_Y:
		local_x_max = max(max_X[i], local_x_max)
		local_x_min = min(min_X[i], local_x_min)
		area_up = (Y[-1] - i) * (local_x_max - local_x_min)
		up_areas.append(area_up)
	up_areas = up_areas[-1::-1]
	up_areas.append(0)
	for i in range(len(Y)):
		areay = min(areay, bottom_areas[i] + up_areas[i + 1])
	if areax <= areay:
		print(areax)
	else:
		print(areay)


from collections import defaultdict as dd

def horizontal(x_pair, N):
	area = 10 ** 18
	max_h = 0
	min_h = 10 ** 18
	h1 = [0] * N
	for val in range(N):
		max_h = max(max_h, x_pair[val][1])
		min_h = min(min_h, x_pair[val][1])
		h1[val] = max_h - min_h
	max_h = 0
	min_h = 10 ** 18
	h2 = [0] * N
	for val in range(N - 1, -1, -1):
		max_h = max(max_h, x_pair[val][1])
		min_h = min(min_h, x_pair[val][1])
		h2[val] = max_h - min_h
	for a in range(N - 1):
		area = min(area, (x_pair[a][0] - x_pair[0][0]) * h1[a] + (x_pair[N - 1][0] - x_pair[a + 1][0]) * h2[a + 1])
	return area

def vertical(y_pair, N, area):
	max_w = 0
	min_w = 10 ** 18
	w1 = [0] * N
	for val in range(N):
		max_w = max(max_w, y_pair[val][1])
		min_w = min(min_w, y_pair[val][1])
		w1[val] = max_w - min_w
	max_w = 0
	min_w = 10 ** 18
	w2 = [0] * N
	for val in range(N - 1, -1, -1):
		max_w = max(max_w, y_pair[val][1])
		min_w = min(min_w, y_pair[val][1])
		w2[val] = max_w - min_w
	for a in range(N - 1):
		area = min(area, (y_pair[a][0] - y_pair[0][0]) * w1[a] + (y_pair[N - 1][0] - y_pair[a + 1][0]) * w2[a + 1])
	return area
T = int(input())
for _ in range(T):
	N = int(input())
	x_pair = []
	y_pair = []
	for _ in range(N):
		(x, y) = map(int, input().split())
		x_pair.append((x, y))
		y_pair.append((y, x))
	if N == 1:
		print(0)
		continue
	x_pair = sorted(x_pair)
	y_pair = sorted(y_pair)
	area = horizontal(x_pair, N)
	area = vertical(y_pair, N, area)
	print(area)


def helper2(sorted_points):
	consolidated_points = []
	curr_x = sorted_points[0][0]
	min_y = sorted_points[0][1]
	max_y = min_y
	for (x, y) in sorted_points:
		if curr_x == x:
			min_y = min(min_y, y)
			max_y = max(max_y, y)
		else:
			consolidated_points.append((curr_x, min_y, max_y))
			curr_x = x
			min_y = y
			max_y = y
	consolidated_points.append((curr_x, min_y, max_y))
	return consolidated_points

def get_rectangle_areas(consolidated_points, x_inc=False):
	min_x = consolidated_points[0][0]
	max_x = min_x
	min_y = consolidated_points[0][1]
	max_y = consolidated_points[0][2]
	areas = [0]
	for (x, y_lower, y_upper) in consolidated_points:
		if x_inc:
			max_x = x
		else:
			min_x = x
		min_y = min(min_y, y_lower)
		max_y = max(max_y, y_upper)
		areas.append((max_x - min_x) * (max_y - min_y))
	return areas

def helper(points):
	points.sort()
	consolidated_points = helper2(points)
	min_area = None
	areas_left_to_right = get_rectangle_areas(consolidated_points, x_inc=True)
	areas_right_to_left = get_rectangle_areas(consolidated_points[::-1], x_inc=False)[::-1]
	for (a1, a2) in zip(areas_left_to_right, areas_right_to_left):
		area = a1 + a2
		min_area = min(area, min_area) if min_area != None else area
	return min_area

def solve(N):
	x_points = []
	y_points = []
	for i in range(N):
		(x, y) = map(int, input().split())
		x_points.append((x, y))
		y_points.append((y, x))
	return min(helper(x_points), helper(y_points))
T = int(input())
for i in range(T):
	print(solve(int(input())))


from collections import defaultdict

def infi():
	return float('inf')

def ninfi():
	return float('-inf')

def calc(p):
	(minx, maxx) = (defaultdict(infi), defaultdict(ninfi))
	(miny, maxy) = (defaultdict(infi), defaultdict(ninfi))
	for (x, y) in p:
		minx[y] = min(minx[y], x)
		maxx[y] = max(maxx[y], x)
		miny[x] = min(miny[x], y)
		maxy[x] = max(maxy[x], y)
	x = list(miny.keys())
	y = list(minx.keys())
	x.sort()
	y.sort()
	area = infi()
	(pref, suff) = ([], [])
	(mn, mx) = (infi(), ninfi())
	for i in x:
		(mn, mx) = (min(mn, miny[i]), max(mx, maxy[i]))
		pref.append((i - x[0]) * (mx - mn))
	(mn, mx) = (infi(), ninfi())
	for i in x[-1::-1]:
		(mn, mx) = (min(mn, miny[i]), max(mx, maxy[i]))
		suff.append((x[-1] - i) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(x)):
		area = min(area, pref[i] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (infi(), ninfi())
	for j in y:
		(mn, mx) = (min(mn, minx[j]), max(mx, maxx[j]))
		pref.append((j - y[0]) * (mx - mn))
	(mn, mx) = (infi(), ninfi())
	for j in y[-1::-1]:
		(mn, mx) = (min(mn, minx[j]), max(mx, maxx[j]))
		suff.append((y[-1] - j) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
t = int(input())
for i in range(t):
	n = int(input())
	p = []
	for j in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	ans = calc(p)
	print(ans)


t = int(input())
from collections import defaultdict

def ninf():
	return float('-inf')

def inf():
	return float('inf')

def answerfinder(coordinates):
	(maxX, minX, maxY, minY) = (defaultdict(ninf), defaultdict(inf), defaultdict(ninf), defaultdict(inf))
	for (x, y) in coordinates:
		(minX[y], maxX[y], minY[x], maxY[x]) = (min(minX[y], x), max(maxX[y], x), min(minY[x], y), max(maxY[x], y))
	X = list(minY.keys())
	Y = list(minX.keys())
	X.sort()
	Y.sort()
	prevarea = []
	nextarea = []
	area = inf()
	(mnx, mxx) = (inf(), ninf())
	for x in X:
		(mnx, mxx) = (min(minY[x], mnx), max(maxY[x], mxx))
		prevarea.append((x - X[0]) * (mxx - mnx))
	(mnx, mxx) = (inf(), ninf())
	for x in X[-1::-1]:
		(mnx, mxx) = (min(minY[x], mnx), max(maxY[x], mxx))
		nextarea.append((X[-1] - x) * (mxx - mnx))
	nextarea = nextarea[-1::-1]
	nextarea.append(0)
	for i in range(len(X)):
		area = min(area, prevarea[i] + nextarea[i + 1])
	prevarea = []
	nextarea = []
	(mnx, mxx) = (inf(), ninf())
	for y in Y:
		(mnx, mxx) = (min(minX[y], mnx), max(maxX[y], mxx))
		prevarea.append((y - Y[0]) * (mxx - mnx))
	(mnx, mxx) = (inf(), ninf())
	for y in Y[-1::-1]:
		(mnx, mxx) = (min(minX[y], mnx), max(maxX[y], mxx))
		nextarea.append((Y[-1] - y) * (mxx - mnx))
	nextarea = nextarea[-1::-1]
	nextarea.append(0)
	for i in range(len(Y)):
		area = min(area, prevarea[i] + nextarea[i + 1])
	return area
for _ in range(t):
	n = int(input())
	coordinates = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		coordinates.append([x, y])
	ans = answerfinder(coordinates)
	print(ans)


for i in range(int(input())):
	n = int(input())
	coordinates = []
	for j in range(n):
		temp = list(map(int, input().split()))
		coordinates.append(temp)
	coordinates.sort()
	y = []
	for j in range(n):
		y.append(coordinates[j][1])
	length = [[0, 0] for j in range(n)]
	miny = 1000000000.0 + 1
	maxy = -1
	for j in range(n):
		miny = min(miny, y[j])
		maxy = max(maxy, y[j])
		length[j][0] = maxy - miny
	miny = 1000000000.0 + 1
	maxy = -1
	for j in range(n - 1, 0, -1):
		miny = min(miny, y[j])
		maxy = max(maxy, y[j])
		length[j - 1][1] = maxy - miny
	areamin = 1e+18 + 1
	for j in range(1, n):
		area = (coordinates[-1][0] - coordinates[j][0]) * length[j - 1][1] + (coordinates[j - 1][0] - coordinates[0][0]) * length[j - 1][0]
		areamin = min(area, areamin)
	for x in coordinates:
		(x[0], x[1]) = (x[1], x[0])
	coordinates.sort()
	x = []
	for j in range(n):
		x.append(coordinates[j][1])
	breadth = [[0, 0] for j in range(n)]
	minx = 1000000000.0 + 1
	maxx = -1
	for j in range(n):
		minx = min(minx, x[j])
		maxx = max(maxx, x[j])
		breadth[j][0] = maxx - minx
	minx = 1000000000.0 + 1
	maxx = -1
	for j in range(n - 1, 0, -1):
		minx = min(minx, x[j])
		maxx = max(maxx, x[j])
		breadth[j - 1][1] = maxx - minx
	for j in range(1, n):
		area = (coordinates[-1][0] - coordinates[j][0]) * breadth[j - 1][1] + (coordinates[j - 1][0] - coordinates[0][0]) * breadth[j - 1][0]
		areamin = min(area, areamin)
	if areamin >= 1e+18 + 1:
		print(0)
	else:
		print(areamin)


from collections import defaultdict
import math

def minimumDualArea(listOfList):
	minx = defaultdict(infinity)
	maxx = defaultdict(negativeinfinity)
	maxy = defaultdict(negativeinfinity)
	miny = defaultdict(infinity)
	for (y, x) in listOfList:
		minx[x] = min(minx[x], y)
		maxx[x] = max(maxx[x], y)
		miny[y] = min(miny[y], x)
		maxy[y] = max(maxy[y], x)
	xcordi = list(miny.keys())
	ycordi = list(minx.keys())
	ycordi.sort()
	xcordi.sort()
	initialArea = infinity()
	preffix = []
	suffix = []
	minc = infinity()
	maxc = negativeinfinity()
	for y in ycordi:
		minc = min(minc, minx[y])
		maxc = max(maxc, maxx[y])
		preffix.append((y - ycordi[0]) * (maxc - minc))
	minc = infinity()
	maxc = negativeinfinity()
	for y in ycordi[len(ycordi)::-1]:
		minc = min(minc, minx[y])
		maxc = max(maxc, maxx[y])
		suffix.append((ycordi[-1] - y) * (maxc - minc))
	suffix = suffix[len(suffix)::-1]
	suffix.append(0)
	i = 0
	while i < len(ycordi):
		initialArea = min(initialArea, preffix[i] + suffix[i + 1])
		i += 1
	suffix = []
	preffix = []
	maxc = negativeinfinity()
	minc = infinity()
	for x in xcordi:
		minc = min(minc, miny[x])
		maxc = max(maxc, maxy[x])
		preffix.append((x - xcordi[0]) * (maxc - minc))
	minc = infinity()
	maxc = negativeinfinity()
	for x in xcordi[len(xcordi)::-1]:
		minc = min(minc, miny[x])
		maxc = max(maxc, maxy[x])
		suffix.append((xcordi[0 - 1] - x) * (maxc - minc))
	suffix = suffix[len(suffix)::-1]
	suffix.append(0)
	i = 0
	while i < len(xcordi):
		initialArea = min(initialArea, preffix[i - 1 + 1] + suffix[i + 1])
		i += 1
	return initialArea

def infinity():
	return float('inf')

def negativeinfinity():
	return float('-inf')
T = int(input())
for i in range(T):
	N = int(input())
	coordinates = []
	for j in range(N):
		xy = list(map(int, input().split()))
		coordinates.append(xy)
	result = minimumDualArea(coordinates)
	print(result)


from bisect import bisect_left

def find_min_area(points):
	points.sort(key=lambda k: k[0])
	curr = 0
	min_area = 99999999999999999999
	y_min = 999999999999999999999
	y_max = 0
	all_y = [point[1] for point in points]
	all_y.sort()
	end = len(points) - 1
	if len(points) == 1:
		return 0
	while curr < len(points) - 1:
		y_max = max(y_max, points[curr][1])
		y_min = min(y_min, points[curr][1])
		idx = bisect_left(all_y, points[curr][1])
		del all_y[idx]
		curr_area = (points[curr][0] - points[0][0]) * (y_max - y_min) + (points[end][0] - points[curr + 1][0]) * (all_y[-1] - all_y[0])
		min_area = min(min_area, curr_area)
		curr += 1
	return min_area
tt = int(input())
for jj in range(tt):
	n = int(input())
	points = [0] * n
	for i in range(n):
		points[i] = list(map(int, input().split()))
	area_by_x = find_min_area(points)
	y_points = [[point[1], point[0]] for point in points]
	area_by_y = find_min_area(y_points)
	print(min(area_by_x, area_by_y))


from collections import defaultdict

def solve(arr):
	(min_X, max_X) = (defaultdict(a), defaultdict(b))
	(min_Y, max_Y) = (defaultdict(a), defaultdict(b))
	for (x, y) in arr:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	for i in range(5):
		sar = 'varu'
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = float('inf')
	(pref, suff) = ([], [])
	(x1, x2) = (float('inf'), float('-inf'))
	for x in X:
		(x1, x2) = (min(x1, min_Y[x]), max(x2, max_Y[x]))
		pref.append((x - X[0]) * (x2 - x1))
	(x1, x2) = (float('inf'), float('-inf'))
	for x in X[-1::-1]:
		(x1, x2) = (min(x1, min_Y[x]), max(x2, max_Y[x]))
		suff.append((X[-1] - x) * (x2 - x1))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i] + suff[i + 1])
	(pref, suff) = ([], [])
	(x1, x2) = (float('inf'), float('-inf'))
	for y in Y:
		(x1, x2) = (min(x1, min_X[y]), max(x2, max_X[y]))
		pref.append((y - Y[0]) * (x2 - x1))
	(x1, x2) = (float('inf'), float('-inf'))
	for y in Y[-1::-1]:
		(x1, x2) = (min(x1, min_X[y]), max(x2, max_X[y]))
		suff.append((Y[-1] - y) * (x2 - x1))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area

def a():
	return float('inf')

def b():
	return float('-inf')
tt = int(input())
for _ in range(tt):
	N = int(input())
	arr = []
	for i in range(N):
		li = list(map(int, input().split()))
		arr.append(li)
	ans = solve(arr)
	print(ans)


from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def solve(p):
	(min__x, max__x) = (defaultdict(INF), defaultdict(NINF))
	(min__y, max__y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		min__x[y] = min(min__x[y], x)
		max__x[y] = max(max__x[y], x)
		min__y[x] = min(min__y[x], y)
		max__y[x] = max(max__y[x], y)
	X = list(min__y.keys())
	Y = list(min__x.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, min__y[x]), max(mx, max__y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min__y[x]), max(mx, max__y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, min__x[y]), max(mx, max__x[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min__x[y]), max(mx, max__x[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
zz = int(input())
for _ in range(zz):
	N = int(input())
	p = []
	for i in range(N):
		li = list(map(int, input().split()))
		p.append(li)
	answer = solve(p)
	print(answer)


from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def sum(p):
	(min_X, max_X) = (defaultdict(INF), defaultdict(NINF))
	(min_Y, max_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
for _ in range(int(input())):
	n = int(input())
	b = []
	for i in range(n):
		l = list(map(int, input().split()))
		b.append(l)
	a = sum(b)
	print(a)


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		p = list(map(int, input().split()))
		l.append(p)
	l.sort()
	y = []
	for i in range(n):
		y.append(l[i][1])
	mx = -1
	mn = 1000000000.0 + 1
	ht = [[0, 0] for i in range(n)]
	for i in range(n):
		mx = max(mx, y[i])
		mn = min(mn, y[i])
		ht[i][0] = mx - mn
	mx = -1
	mn = 1000000000.0 + 1
	for i in range(n - 1, 0, -1):
		mx = max(mx, y[i])
		mn = min(mn, y[i])
		ht[i - 1][1] = mx - mn
	a1 = 1e+19
	a2 = 1e+19
	for i in range(1, n):
		a = (l[i - 1][0] - l[0][0]) * ht[i - 1][0] + (l[-1][0] - l[i][0]) * ht[i - 1][1]
		a1 = min(a1, a)
	for x in l:
		(x[0], x[1]) = (x[1], x[0])
	l.sort()
	x = []
	for i in range(n):
		x.append(l[i][1])
	w = [[0, 0] for i in range(n)]
	mx = -1
	mn = 1000000000.0 + 1
	for i in range(n):
		mx = max(mx, x[i])
		mn = min(mn, x[i])
		w[i][0] = mx - mn
	mx = -1
	mn = 1000000000.0 + 1
	for i in range(n - 1, 0, -1):
		mx = max(mx, x[i])
		mn = min(mn, x[i])
		w[i - 1][1] = mx - mn
	for i in range(1, n):
		a = (l[i - 1][0] - l[0][0]) * w[i - 1][0] + (l[-1][0] - l[i][0]) * w[i - 1][1]
		a2 = min(a2, a)
	ans = min(a1, a2)
	if ans >= 1e+18 + 1:
		print(0)
	else:
		print(ans)


from collections import defaultdict

def INF():
	return float('inf')

def NINF():
	return float('-inf')

def minimumDualarea(P):
	(min_X, max_X) = (defaultdict(INF), defaultdict(NINF))
	(min_Y, max_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in P:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pefix, suffix) = ([], [])
	(minimum, maximum) = (INF(), NINF())
	for x in X:
		(minimum, maximum) = (min(minimum, min_Y[x]), max(maximum, max_Y[x]))
		pefix.append((x - X[0]) * (maximum - minimum))
	(minimum, maximum) = (INF(), NINF())
	for x in X[-1::-1]:
		(minimum, maximum) = (min(minimum, min_Y[x]), max(maximum, max_Y[x]))
		suffix.append((X[-1] - x) * (maximum - minimum))
	suffix = suffix[-1::-1]
	suffix.append(0)
	for i in range(len(X)):
		area = min(area, pefix[i] + suffix[i + 1])
	(pefix, suffix) = ([], [])
	(minimum, maximum) = (INF(), NINF())
	for y in Y:
		(minimum, maximum) = (min(minimum, min_X[y]), max(maximum, max_X[y]))
		pefix.append((y - Y[0]) * (maximum - minimum))
	(minimum, maximum) = (INF(), NINF())
	for y in Y[-1::-1]:
		(minimum, maximum) = (min(minimum, min_X[y]), max(maximum, max_X[y]))
		suffix.append((Y[-1] - y) * (maximum - minimum))
	suffix = suffix[-1::-1]
	suffix.append(0)
	for i in range(len(Y)):
		area = min(area, pefix[i] + suffix[i + 1])
	return area
testcases = int(input())
for iter in range(testcases):
	N = int(input())
	P = []
	for i in range(N):
		li = list(map(int, input().split()))
		P.append(li)
	ans = minimumDualarea(P)
	print(ans)


INF = int(1e+20)

def sweep_area(indices, X, Y):
	minX = [INF] * N
	maxX = [-1] * N
	height = [0] * N
	last_minX = INF
	last_maxX = -1
	y = Y[indices[0]]
	for i in indices:
		last_minX = min(last_minX, X[i])
		last_maxX = max(last_maxX, X[i])
		minX[i] = last_minX
		maxX[i] = last_maxX
		height[i] = abs(Y[i] - y)
	return (minX, maxX, height)

def merge(curX, maxXtop, minXtop, maxXbot, minXbot, wBot, wTop, prevWbot):
	maxX = max(curX)
	minX = min(curX)
	curMaxXtop = max(maxX, maxXtop)
	curMinXtop = min(minX, minXtop)
	curMinXbot = min(minX, minXbot)
	area = (curMaxXtop - curMinXtop) * wTop + (maxXbot - minXbot) * prevWbot
	last_x = curX[0]
	for x in curX:
		if minXtop < x:
			continue
		xBot = max(x, maxXbot)
		xTop = min(last_x, minXtop)
		area1 = (curMaxXtop - xTop) * wTop
		area2 = (xBot - curMinXbot) * wBot
		area = min(area, area1 + area2)
		last_x = x
	return area

def minimum_area(X, Y):
	indices = list(range(N))
	indices.sort(key=lambda i: (-Y[i], X[i]))
	(minXtop, maxXtop, heightTop) = sweep_area(indices, X, Y)
	indices.reverse()
	(minXbot, maxXbot, heightBot) = sweep_area(indices, X, Y)
	i_1 = indices[0]
	x_indices = []
	double_area = INF
	j = -1
	for i in indices + [INF]:
		if i == INF or Y[i_1] != Y[i]:
			if i == INF:
				area = (maxXbot[j] - minXbot[j]) * heightBot[j]
			elif j == -1:
				area = (maxXtop[i] - minXtop[i]) * heightTop[i]
			else:
				curX = [X[k] for k in x_indices]
				area1 = merge(curX, maxXtop[i], minXtop[i], maxXbot[j], minXbot[j], heightBot[i_1], heightTop[i_1], heightBot[j])
				area2 = merge(curX, maxXbot[j], minXbot[j], maxXtop[i], minXtop[i], heightTop[i_1], heightBot[i_1], heightTop[i])
				area = min(area1, area2)
			double_area = min(double_area, area)
			j = i_1
			x_indices = []
		x_indices.append(i)
		i_1 = i
	return double_area

def solve():
	return min(minimum_area(X, Y), minimum_area(Y, X))
test_cases = int(input())
for test_case in range(test_cases):
	N = int(input())
	X = [0] * N
	Y = [0] * N
	for i in range(N):
		(X[i], Y[i]) = map(int, input().split())
	print(solve())


def VerticalLevels(array):
	l = len(array)
	array.append([0, array[-1][1] + 1])
	ans = []
	(start, end) = (0, 0)
	while end < l:
		if array[end][1] == array[end + 1][1]:
			end += 1
		else:
			ans.append(array[start:end + 1])
			end += 1
			start = end
	return ans

def MinArea(Point, TopExtremes, BotExtremes):
	levels = len(Point)
	if levels == 1:
		return 0
	area1 = (TopExtremes[1][1] - TopExtremes[1][0]) * (Point[levels - 1][0][1] - Point[1][0][1])
	area2 = (BotExtremes[levels - 2][1] - BotExtremes[levels - 2][0]) * (Point[levels - 2][0][1] - Point[0][0][1])
	area = min(area1, area2)
	for i in range(1, levels - 1):
		level_i = Point[i]
		l = len(level_i)
		a1 = (TopExtremes[i][1] - TopExtremes[i][0]) * (Point[-1][0][1] - Point[i][0][1])
		a2 = (BotExtremes[i - 1][1] - BotExtremes[i - 1][0]) * (Point[i - 1][0][1] - Point[0][0][1])
		area = min(area, a1 + a2)
		a1 = (TopExtremes[i + 1][1] - TopExtremes[i + 1][0]) * (Point[-1][0][1] - Point[i + 1][0][1])
		a2 = (BotExtremes[i][1] - BotExtremes[i][0]) * (Point[i][0][1] - Point[0][0][1])
		area = min(area, a1 + a2)
		for j in range(l - 1):
			top_left = min(TopExtremes[i + 1][0], level_i[0][0])
			top_right = max(TopExtremes[i + 1][1], level_i[j][0])
			a1 = (top_right - top_left) * (Point[levels - 1][0][1] - Point[i][0][1])
			bot_left = min(BotExtremes[i - 1][0], Point[i][j + 1][0])
			bot_right = max(BotExtremes[i - 1][1], Point[i][-1][0])
			a2 = (bot_right - bot_left) * (Point[i][0][1] - Point[0][0][1])
			area = min(area, a1 + a2)
			bot_left = min(BotExtremes[i - 1][0], Point[i][0][0])
			bot_right = max(BotExtremes[i - 1][1], Point[i][j][0])
			a1 = (bot_right - bot_left) * (Point[i][0][1] - Point[0][0][1])
			top_left = min(TopExtremes[i + 1][0], Point[i][j + 1][0])
			top_right = max(TopExtremes[i + 1][1], Point[i][-1][0])
			a2 = (top_right - top_left) * (Point[-1][0][1] - Point[i][0][1])
			area = min(area, a2 + a1)
	return area

def EachCase():
	n = int(input())
	Point = [0] * n
	for i in range(n):
		Point[i] = list(map(int, input().split()))
	Swapped = [0] * n
	for i in range(n):
		Swapped[i] = Point[i][::-1]
	a = HorizontalCase(Point)
	b = HorizontalCase(Swapped)
	print(min(a, b))

def HorizontalCase(Point):
	Point.sort(key=lambda x: [x[1], x[0]])
	Point = VerticalLevels(Point)
	levels = len(Point)
	BotExtremes = [-1] * levels
	BotExtremes[0] = [Point[0][0][0], Point[0][-1][0]]
	for i in range(1, levels):
		(left, right) = BotExtremes[i - 1]
		BotExtremes[i] = [min(left, Point[i][0][0]), max(right, Point[i][-1][0])]
	TopExtremes = [-1] * levels
	TopExtremes[-1] = [Point[-1][0][0], Point[-1][-1][0]]
	for i in range(levels - 2, -1, -1):
		(left, right) = TopExtremes[i + 1]
		TopExtremes[i] = [min(left, Point[i][0][0]), max(right, Point[i][-1][0])]
	area = MinArea(Point, TopExtremes, BotExtremes)
	return area
testCases = int(input())
for _ in range(testCases):
	EachCase()


from collections import defaultdict

def Inf():
	return float('inf')

def NInf():
	return float('-inf')

def solve(array):
	(min_X, max_X) = (defaultdict(Inf), defaultdict(NInf))
	(min_Y, max_Y) = (defaultdict(Inf), defaultdict(NInf))
	for (x, y) in array:
		min_X[y] = min(min_X[y], x)
		max_X[y] = max(max_X[y], x)
		min_Y[x] = min(min_Y[x], y)
		max_Y[x] = max(max_Y[x], y)
	X = list(min_Y.keys())
	Y = list(min_X.keys())
	X.sort()
	Y.sort()
	area = Inf()
	(pre, last) = ([], [])
	(mn, mx) = (Inf(), NInf())
	for x in X:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		pre.append((x - X[0]) * (mx - mn))
	(mn, mx) = (Inf(), NInf())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		last.append((X[0 - 1] - x) * (mx - mn))
	last = last[-1::-1]
	last.append(0)
	for i in range(len(X)):
		area = min(area, pre[i - 1 + 1] + last[i + 1])
	(pre, last) = ([], [])
	(mn, mx) = (Inf(), NInf())
	for y in Y:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		pre.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (Inf(), NInf())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		last.append((Y[-1] - y) * (mx - mn))
	last = last[-1::-1]
	last.append(0)
	for i in range(len(Y)):
		area = min(area, pre[i] + last[i + 1])
	return area
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		l = list(map(int, input().split()))
		a.append(l)
	ans = solve(a)
	print(ans)


from collections import defaultdict

def INF():
	return float('inf')

def NINF():
	return float('-inf')

def calculate(vec):
	(m1, m2) = (defaultdict(INF), defaultdict(NINF))
	(m3, m4) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in vec:
		m1[y] = min(m1[y], x)
		m2[y] = max(m2[y], x)
		m3[x] = min(m3[x], y)
		m4[x] = max(m4[x], y)
	res1 = list(m3.keys())
	res2 = list(m1.keys())
	res1.sort()
	res2.sort()
	res3 = INF()
	(p, s) = ([], [])
	(a, b) = (INF(), NINF())
	for x in res1:
		(a, b) = (min(a, m3[x]), max(b, m4[x]))
		p.append((x - res1[0]) * (b - a))
	(a, b) = (INF(), NINF())
	for x in res1[-1::-1]:
		(a, b) = (min(a, m3[x]), max(b, m4[x]))
		s.append((res1[-1] - x) * (b - a))
	s = s[-1::-1]
	s.append(0)
	for i in range(len(res1)):
		res3 = min(res3, p[i] + s[i + 1])
	(p, s) = ([], [])
	(a, b) = (INF(), NINF())
	for y in res2:
		(a, b) = (min(a, m1[y]), max(b, m2[y]))
		p.append((y - res2[0]) * (b - a))
	(a, b) = (INF(), NINF())
	for y in res2[-1::-1]:
		(a, b) = (min(a, m1[y]), max(b, m2[y]))
		s.append((res2[-1] - y) * (b - a))
	s = s[-1::-1]
	s.append(0)
	for i in range(len(res2)):
		res3 = min(res3, p[i] + s[i + 1])
	return res3
test = int(input())
for _ in range(test):
	n = int(input())
	vec = []
	for i in range(n):
		arr = list(map(int, input().split()))
		vec.append(arr)
	res = calculate(vec)
	print(res)


from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def solution(p):
	(min_x, max_x) = (defaultdict(INF), defaultdict(NINF))
	(min_y, max_y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		min_x[y] = min(min_x[y], x)
		max_x[y] = max(max_x[y], x)
		min_y[x] = min(min_y[x], y)
		max_y[x] = max(max_y[x], y)
	X = list(min_y.keys())
	Y = list(min_x.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, min_y[x]), max(mx, max_y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min_y[x]), max(mx, max_y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, min_x[y]), max(mx, max_x[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min_x[y]), max(mx, max_x[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
tc = int(input())
for _ in range(tc):
	n = int(input())
	m = []
	for i in range(n):
		li = list(map(int, input().split()))
		m.append(li)
	result = solution(m)
	print(result)


import sys

def compute_dp(points):
	dp = []
	(ax, min_y) = points[0]
	max_y = min_y
	for p in points:
		(bx, by) = p
		min_y = min(by, min_y)
		max_y = max(by, max_y)
		area = abs(bx - ax) * abs(max_y - min_y)
		dp.append(area)
	return dp

def compute_min_area(N, points):
	sorted_x = sorted(points, key=lambda p: p[0])
	dp = compute_dp(sorted_x)
	sorted_x.reverse()
	dp_r = compute_dp(sorted_x)
	dp_r.reverse()
	min_area = dp[N - 1]
	for i in range(N - 1):
		min_area = min(min_area, dp[i] + dp_r[i + 1])
	return min_area
t = int(sys.stdin.readline())
for _ in range(t):
	N = int(sys.stdin.readline())
	points = []
	for _ in range(N):
		p = tuple(map(int, sys.stdin.readline().split()))
		points.append(p)
	if N <= 2:
		print(0)
		continue
	min_area_x = compute_min_area(N, points)
	points_transposed = map(lambda p: (p[1], p[0]), points)
	min_area_y = compute_min_area(N, points_transposed)
	print(min(min_area_x, min_area_y))


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict

def box_area(left, right):
	return (right[1] - left[1]) * (right[0] - left[0])

def find_box(p):
	x = [x for (x, y) in p]
	y = [y for (x, y) in p]
	return ((min(x), min(y)), (max(x), max(y)))

def solve_scan(p):
	sort_by_x = sorted(p, key=lambda x: (x[0], -x[1]))
	min_max_table_left = []
	(min_x, min_y) = sort_by_x[0]
	(max_x, max_y) = sort_by_x[0]
	for (x, y) in sort_by_x:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		min_max_table_left.append([(min_x, min_y), (max_x, max_y)])
	min_max_table_right = []
	(min_x, min_y) = sort_by_x[-1]
	(max_x, max_y) = sort_by_x[-1]
	for (x, y) in sort_by_x[::-1]:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		min_max_table_right.append([(min_x, min_y), (max_x, max_y)])
	area = box_area(*find_box(sort_by_x))
	for i in range(len(sort_by_x)):
		area_left = box_area(*min_max_table_left[i])
		area_right = box_area(*min_max_table_right[len(sort_by_x) - 2 - i])
		new_area = area_left + area_right
		if new_area < area:
			area = new_area
	return area

def main():
	for _ in range(int(input())):
		N = int(input())
		p = [tuple(map(int, input().split())) for _ in range(N)]
		x = solve_scan(p)
		y = solve_scan([(y, x) for (x, y) in p])
		print(f'{min(x, y)}')
main()


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict

def find_middle(P):
	prev_x = P[0][0]
	better = (prev_x, prev_x)
	best_size = 0
	for (x, y) in P[1:]:
		size = x - prev_x
		if size > best_size:
			best_size = size
			better = (prev_x, x)
		prev_x = x
	return better

def box_area(left, right):
	return (right[1] - left[1]) * (right[0] - left[0])

def find_box(p):
	x = [x for (x, y) in p]
	y = [y for (x, y) in p]
	return ((min(x), min(y)), (max(x), max(y)))

def solve_middle(p):
	sort_by_x = sorted(p)
	middle = find_middle(sort_by_x)
	left_middle_points = [i for i in sort_by_x if i[0] <= middle[0]]
	right_middle_points = [i for i in sort_by_x if i[0] >= middle[1]]
	area_left = area_right = 0
	if left_middle_points:
		area_left = box_area(*find_box(left_middle_points))
	if right_middle_points:
		area_right = box_area(*find_box(right_middle_points))
	return area_left + area_right

def solve_scan(p):
	sort_by_x = sorted(p, key=lambda x: (x[0], -x[1]))
	min_max_table_left = []
	(min_x, min_y) = sort_by_x[0]
	(max_x, max_y) = sort_by_x[0]
	for (x, y) in sort_by_x:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		min_max_table_left.append([(min_x, min_y), (max_x, max_y)])
	min_max_table_right = []
	(min_x, min_y) = sort_by_x[-1]
	(max_x, max_y) = sort_by_x[-1]
	for (x, y) in sort_by_x[::-1]:
		if x < min_x:
			min_x = x
		if x > max_x:
			max_x = x
		if y < min_y:
			min_y = y
		if y > max_y:
			max_y = y
		min_max_table_right.append([(min_x, min_y), (max_x, max_y)])
	area = box_area(*find_box(sort_by_x))
	for i in range(len(sort_by_x)):
		area_left = box_area(*min_max_table_left[i])
		area_right = box_area(*min_max_table_right[len(sort_by_x) - 2 - i])
		new_area = area_left + area_right
		if new_area < area:
			area = new_area
	return area

def main():
	for _ in range(int(input())):
		N = int(input())
		p = [tuple(map(int, input().split())) for _ in range(N)]
		x = solve_middle(p)
		y = solve_middle([(y, x) for (x, y) in p])
		z = solve_scan(p)
		w = solve_scan([(y, x) for (x, y) in p])
		print(f'{min(x, y, z, w)}')
main()


import collections
from collections import defaultdict
T = int(input())
for _ in range(T):
	n = int(input())
	xmin = defaultdict(lambda : float('inf'))
	xmax = defaultdict(lambda : float('-inf'))
	ymin = defaultdict(lambda : float('inf'))
	ymax = defaultdict(lambda : float('-inf'))
	for i in range(n):
		(x, y) = map(int, input().split())
		xmin[y] = min(xmin[y], x)
		xmax[y] = max(xmax[y], x)
		ymin[x] = min(ymin[x], y)
		ymax[x] = max(ymax[x], y)
	areax = float('inf')
	X = list(ymin.keys())
	Y = list(xmin.keys())
	X.sort()
	Y.sort()
	lymax = float('-inf')
	lymin = float('inf')
	left_areas = []
	for i in X:
		lymax = max(ymax[i], lymax)
		lymin = min(ymin[i], lymin)
		area_left = (i - X[0]) * (lymax - lymin)
		left_areas.append(area_left)
	rev_X = X[-1::-1]
	lymax = float('-inf')
	lymin = float('inf')
	right_areas = []
	for i in rev_X:
		lymax = max(ymax[i], lymax)
		lymin = min(ymin[i], lymin)
		area_right = (X[-1] - i) * (lymax - lymin)
		right_areas.append(area_right)
	right_areas = right_areas[-1::-1]
	right_areas.append(0)
	for i in range(len(X)):
		areax = min(areax, left_areas[i] + right_areas[i + 1])
	lxmax = float('-inf')
	lxmin = float('inf')
	bottom_areas = []
	for i in Y:
		lxmax = max(xmax[i], lxmax)
		lxmin = min(xmin[i], lxmin)
		area_bottom = (i - Y[0]) * (lxmax - lxmin)
		bottom_areas.append(area_bottom)
	rev_Y = Y[-1::-1]
	lxmax = float('-inf')
	lxmin = float('inf')
	areay = float('inf')
	up_areas = []
	for i in rev_Y:
		lxmax = max(xmax[i], lxmax)
		lxmin = min(xmin[i], lxmin)
		area_up = (Y[-1] - i) * (lxmax - lxmin)
		up_areas.append(area_up)
	up_areas = up_areas[-1::-1]
	up_areas.append(0)
	for i in range(len(Y)):
		areay = min(areay, bottom_areas[i] + up_areas[i + 1])
	print(min(areax, areay))


from collections import defaultdict
test = int(input())
for j in range(test):
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	(min_X, max_X) = (defaultdict(lambda : float('inf')), defaultdict(lambda : float('-inf')))
	(min_Y, max_Y) = (defaultdict(lambda : float('inf')), defaultdict(lambda : float('-inf')))
	for (a, b) in p:
		min_Y[a] = min(min_Y[a], b)
		max_Y[a] = max(max_Y[a], b)
		min_X[b] = min(min_X[b], a)
		max_X[b] = max(max_X[b], a)
	X = sorted(list(min_Y.keys()))
	Y = sorted(list(min_X.keys()))
	area = float('inf')
	prefix = []
	suffix = []
	mn = float('inf')
	mx = float('-inf')
	for y in Y:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		prefix.append((y - Y[0]) * (mx - mn))
	mn = float('inf')
	mx = float('-inf')
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, min_X[y]), max(mx, max_X[y]))
		suffix.append((Y[-1] - y) * (mx - mn))
	suffix = suffix[-1::-1]
	suffix.append(0)
	for i in range(len(Y)):
		area = min(area, prefix[i] + suffix[i + 1])
	prefix = []
	suffix = []
	mn = float('inf')
	mx = float('-inf')
	for x in X:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		prefix.append((x - X[0]) * (mx - mn))
	mn = float('inf')
	mx = float('-inf')
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, min_Y[x]), max(mx, max_Y[x]))
		suffix.append((X[-1] - x) * (mx - mn))
	suffix = suffix[-1::-1]
	suffix.append(0)
	for i in range(len(X)):
		area = min(area, prefix[i - 1 + 1] + suffix[i + 1])
	print(area)


import copy
t = int(input())
for i in range(0, t):
	n = int(input())
	lst_x = []
	lst_y = []
	for j in range(0, n):
		(x, y) = map(int, input().split())
		tup = (x, y)
		lst_x.append(copy.deepcopy(tup))
		tup = (y, x)
		lst_y.append(copy.deepcopy(tup))
	if n > 2:
		lst_x.sort()
		lst_y.sort()
		min_y = [lst_x[0][1]]
		max_y = [lst_x[0][1]]
		min_x = [lst_y[0][1]]
		max_x = [lst_y[0][1]]
		min_y_rev = [lst_x[-1][1]]
		max_y_rev = [lst_x[-1][1]]
		min_x_rev = [lst_y[-1][1]]
		max_x_rev = [lst_y[-1][1]]
		for j in range(1, n):
			min_y.append(min(min_y[-1], lst_x[j][1]))
			max_y.append(max(max_y[-1], lst_x[j][1]))
			min_x.append(min(min_x[-1], lst_y[j][1]))
			max_x.append(max(max_x[-1], lst_y[j][1]))
			min_y_rev.append(min(min_y_rev[-1], lst_x[n - j - 1][1]))
			max_y_rev.append(max(max_y_rev[-1], lst_x[n - j - 1][1]))
			min_x_rev.append(min(min_x_rev[-1], lst_y[n - j - 1][1]))
			max_x_rev.append(max(max_x_rev[-1], lst_y[n - j - 1][1]))
		min_x_rev.reverse()
		min_y_rev.reverse()
		max_x_rev.reverse()
		max_y_rev.reverse()
		m1 = (lst_x[n - 1][0] - lst_x[0][0]) * (max_y[n - 1] - min_y[n - 1])
		for j in range(0, n - 1):
			t = (lst_x[j][0] - lst_x[0][0]) * (max_y[j] - min_y[j]) + (lst_x[n - 1][0] - lst_x[j + 1][0]) * (max_y_rev[j + 1] - min_y_rev[j + 1])
			if t < m1:
				m1 = t
		for j in range(0, n - 1):
			t = (lst_y[j][0] - lst_y[0][0]) * (max_x[j] - min_x[j]) + (lst_y[n - 1][0] - lst_y[j + 1][0]) * (max_x_rev[j + 1] - min_x_rev[j + 1])
			if t < m1:
				m1 = t
		print(m1)
	else:
		print(0)


from collections import defaultdict

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def something(p):
	(rko_x, rko_X) = (defaultdict(INF), defaultdict(NINF))
	(rko_y, rko_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		rko_x[y] = min(rko_x[y], x)
		rko_X[y] = max(rko_X[y], x)
		rko_y[x] = min(rko_y[x], y)
		rko_Y[x] = max(rko_Y[x], y)
	X = list(rko_y.keys())
	Y = list(rko_x.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, rko_y[x]), max(mx, rko_Y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, rko_y[x]), max(mx, rko_Y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, rko_x[y]), max(mx, rko_X[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, rko_x[y]), max(mx, rko_X[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	ans = something(p)
	print(ans)


import math
for _ in range(int(input())):
	N = int(input())
	points = [tuple(map(int, input().split())) for _ in range(N)]
	min_area = math.inf
	transpose = True
	for _ in range(2):
		points.sort()
		start_x = points[0][0]
		end_x = points[-1][0]
		if start_x == end_x:
			min_area = 0
			continue
		min_y = 10 ** 9 + 1
		max_y = -min_y
		max_y_left = [0] * N
		min_y_left = [0] * N
		for (i, (_, y)) in enumerate(points):
			max_y = max(max_y, y)
			min_y = min(min_y, y)
			max_y_left[i] = max_y
			min_y_left[i] = min_y
		min_y = 10 ** 9 + 1
		max_y = -min_y
		max_y_right = [0] * N
		min_y_right = [0] * N
		for (i, (_, y)) in enumerate(reversed(points), 1):
			max_y = max(max_y, y)
			min_y = min(min_y, y)
			max_y_right[N - i] = max_y
			min_y_right[N - i] = min_y
		prev_x = start_x
		for (i, (x, _)) in enumerate(points):
			if prev_x == x:
				continue
			left = (prev_x - start_x) * (max_y_left[i - 1] - min_y_left[i - 1])
			right = (end_x - x) * (max_y_right[i] - min_y_right[i])
			min_area = min(min_area, left + right)
			prev_x = x
		if transpose:
			points = [(y, x) for (x, y) in points]
			transpose = False
	print(min_area)


from collections import deque

def read_int_array():
	return [int(token) for token in input().split(' ')]

def solve_sort_first_dimension(points):
	points.sort(key=lambda p: p[0])
	prefixes = []
	minx = points[0][0]
	miny = points[0][1]
	maxy = points[0][1]
	for (x, y) in points:
		dx = x - minx
		miny = min(miny, y)
		maxy = max(maxy, y)
		dy = maxy - miny
		prefixes.append(dx * dy)
	suffixes = deque()
	maxx = points[-1][0]
	miny = points[-1][1]
	maxy = points[-1][1]
	for (x, y) in reversed(points):
		dx = maxx - x
		miny = min(miny, y)
		maxy = max(maxy, y)
		dy = maxy - miny
		suffixes.appendleft(dx * dy)
	suffixes.popleft()
	return min(map(lambda x: x[0] + x[1], zip(prefixes, suffixes)))

def solve(points):
	if len(points) < 2:
		return 0
	return min([solve_sort_first_dimension(points), solve_sort_first_dimension([(y, x) for (x, y) in points])])

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		points = []
		for i in range(n):
			points.append(read_int_array())
		print(solve(points))
main()


def solve2(coordinates):
	coordinates.sort()
	minX = coordinates[0][0]
	maxX = coordinates[-1][0]
	minY = coordinates[0][1]
	maxY = coordinates[0][1]
	size_left = [0 for i in range(len(coordinates) + 1)]
	for (idx, (x, y)) in enumerate(coordinates):
		minY = min(minY, y)
		maxY = max(maxY, y)
		size_left[idx + 1] = maxY - minY
	minY = coordinates[-1][1]
	maxY = coordinates[-1][1]
	size_right = [0 for i in range(len(coordinates) + 1)]
	for (idx, (x, y)) in reversed(list(enumerate(coordinates))):
		minY = min(minY, y)
		maxY = max(maxY, y)
		size_right[idx] = maxY - minY
	answer = (maxX - coordinates[0][0]) * size_right[0]
	for idx in range(1, len(coordinates)):
		left_rectangle = (coordinates[idx - 1][0] - minX) * size_left[idx]
		right_rectangle = (maxX - coordinates[idx][0]) * size_right[idx]
		answer = min(answer, left_rectangle + right_rectangle)
	return answer

def solve(t):
	N = int(input())
	coordinates = []
	for i in range(N):
		(x, y) = map(int, input().split())
		coordinates.append((x, y))
	answer = solve2(coordinates)
	coordinates = [(y, x) for (x, y) in coordinates]
	answer = min(answer, solve2(coordinates))
	print(answer)
T = int(input())
for t in range(T):
	solve(t + 1)


from collections import defaultdict
import sys

def Negative():
	return -1 * sys.maxsize

def positive():
	return sys.maxsize

def solution(p):
	(a, b) = (defaultdict(positive), defaultdict(Negative))
	(c, d) = (defaultdict(positive), defaultdict(Negative))
	for (x, y) in p:
		a[y] = min(a[y], x)
		b[y] = max(b[y], x)
		c[x] = min(c[x], y)
		d[x] = max(d[x], y)
	X = list(c.keys())
	Y = list(a.keys())
	X.sort()
	Y.sort()
	areasum = positive()
	(pre, suf) = ([], [])
	(mn, mx) = (positive(), Negative())
	for x in X:
		(mn, mx) = (min(mn, c[x]), max(mx, d[x]))
		pre.append((x - X[0]) * (mx - mn))
	(mn, mx) = (positive(), Negative())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, c[x]), max(mx, d[x]))
		suf.append((X[0 - 1] - x) * (mx - mn))
	suf = suf[-1::-1]
	suf.append(0)
	for i in range(len(X)):
		areasum = min(areasum, pre[i - 1 + 1] + suf[i + 1])
	(pre, suf) = ([], [])
	(mn, mx) = (positive(), Negative())
	for y in Y:
		(mn, mx) = (min(mn, a[y]), max(mx, b[y]))
		pre.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (positive(), Negative())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, a[y]), max(mx, b[y]))
		suf.append((Y[-1] - y) * (mx - mn))
	suf = suf[-1::-1]
	suf.append(0)
	for i in range(len(Y)):
		areasum = min(areasum, pre[i] + suf[i + 1])
	return areasum
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	ans = solution(p)
	print(ans)


from collections import defaultdict
import math

class my_methods:

	def isprime(self, n):
		i = 0
		for _ in range(2, n + 1):
			if n % _ == 0:
				i += 1
		a = True if i == 1 else False
		return a

	def iseven(self, n):
		a = True if n % 2 == 0 else False
		return a

	def isodd(self, n):
		a = True if n % 2 != 0 else False
		return a

	def get_odd(self, srt, n):
		if self.isodd(srt) == True:
			a = [x for x in range(srt, n + 1, 2)]
		else:
			a = [x for x in range(srt + 1, n + 1, 2)]
		return a

	def get_even(self, srt, n):
		if self.iseven(srt) == True:
			a = [x for x in range(srt, n + 1, 2)]
		else:
			a = [x for x in range(srt + 1, n + 1, 2)]
		return a

	def get_factors(self, n):
		i = 1
		d = []
		while n >= i ** 2:
			if n % i == 0:
				d.append(i)
				if n != i ** 2:
					d.append(n // i)
			i += 1
		return sorted(d)

	def isremain(self, n):
		a = True if n % i == 0 else False
		return a

	def get_fact(self, n):
		i = 1
		a = 1 if n <= 1 else n * self.get_fact(n - 1)
		return a

	def sq_roots(self, a, b, c):
		d = []
		(x, y) = (-b + math.sqrt(b * 2 - 4 * a * c), -b - math.sqrt(b * 2 - 4 * a * c))
		(z1, z2) = (x // 2 * a, y // 2 * a)
		d.append(int(z1))
		d.append(int(z2))
		return d

	def merge_sort(self, a):
		if len(a) > 1:
			mid = len(a) // 2
			(l, r) = (a[:mid], a[mid:])
			self.merge_Sort(l)
			self.merge_Sort(r)
			(i, j, k) = (0, 0, 0)
			while i < len(l) and j < len(r):
				if l[i] < r[j]:
					a[k] = l[i]
					i += 1
					k += 1
				else:
					a[k] = r[j]
					j += 1
					k += 1
			while i < len(l):
				a[k] = l[i]
				i += 1
				k += 1
			while j < len(r):
				a[k] = r[j]
				j += 1
				k += 1
		return a

def NINF():
	return float('-inf')

def INF():
	return float('inf')

def solve(p):
	(minium_X, maximum_X) = (defaultdict(INF), defaultdict(NINF))
	(minium_Y, maximum_Y) = (defaultdict(INF), defaultdict(NINF))
	for (x, y) in p:
		minium_X[y] = min(minium_X[y], x)
		maximum_X[y] = max(maximum_X[y], x)
		minium_Y[x] = min(minium_Y[x], y)
		maximum_Y[x] = max(maximum_Y[x], y)
	X = list(minium_Y.keys())
	Y = list(minium_X.keys())
	X.sort()
	Y.sort()
	area = INF()
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for x in X:
		(mn, mx) = (min(mn, minium_Y[x]), max(mx, maximum_Y[x]))
		pref.append((x - X[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, minium_Y[x]), max(mx, maximum_Y[x]))
		suff.append((X[0 - 1] - x) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(X)):
		area = min(area, pref[i - 1 + 1] + suff[i + 1])
	(pref, suff) = ([], [])
	(mn, mx) = (INF(), NINF())
	for y in Y:
		(mn, mx) = (min(mn, minium_X[y]), max(mx, maximum_X[y]))
		pref.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (INF(), NINF())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, minium_X[y]), max(mx, maximum_X[y]))
		suff.append((Y[-1] - y) * (mx - mn))
	suff = suff[-1::-1]
	suff.append(0)
	for i in range(len(Y)):
		area = min(area, pref[i] + suff[i + 1])
	return area
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for i in range(n):
		li = list(map(int, input().split()))
		p.append(li)
	ans = solve(p)
	print(ans)


inf = float('inf')
for _ in range(int(input())):
	minX = {}
	maxX = {}
	minY = {}
	maxY = {}
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
		minY[x] = min(minY.get(x, inf), y)
		maxY[x] = max(maxY.get(x, -inf), y)
		minX[y] = min(minX.get(y, inf), x)
		maxX[y] = max(maxX.get(y, -inf), x)
	X = sorted(list(minY.keys()))
	Y = sorted(list(minX.keys()))
	area = inf
	(rect_from_start, rect_from_end) = ([], [])
	(top, bottom) = (-inf, inf)
	for x in X:
		top = max(top, maxY[x])
		bottom = min(bottom, minY[x])
		rect_from_start.append((x - X[0]) * (top - bottom))
	(top, bottom) = (-inf, inf)
	for x in X[::-1]:
		top = max(top, maxY[x])
		bottom = min(bottom, minY[x])
		rect_from_end.append((X[-1] - x) * (top - bottom))
	rect_from_end.reverse()
	rect_from_end.append(0)
	for i in range(len(X)):
		area = min(area, rect_from_end[i + 1] + rect_from_start[i])
	(rect_from_start, rect_from_end) = ([], [])
	(top, bottom) = (-inf, inf)
	for y in Y:
		top = max(top, maxX[y])
		bottom = min(bottom, minX[y])
		rect_from_start.append((y - Y[0]) * (top - bottom))
	(top, bottom) = (-inf, inf)
	for y in Y[::-1]:
		top = max(top, maxX[y])
		bottom = min(bottom, minX[y])
		rect_from_end.append((Y[-1] - y) * (top - bottom))
	rect_from_end.reverse()
	rect_from_end.append(0)
	for i in range(len(Y)):
		area = min(area, rect_from_end[i + 1] + rect_from_start[i])
	print(area)


from collections import defaultdict

def N_INF():
	return float('-inf')

def I_N_F():
	return float('inf')

def result(point):
	(min_A, maxi_A) = (defaultdict(I_N_F), defaultdict(N_INF))
	(min_B, maxi_B) = (defaultdict(I_N_F), defaultdict(N_INF))
	for (x, y) in point:
		min_A[y] = min(min_A[y], x)
		maxi_A[y] = max(maxi_A[y], x)
		min_B[x] = min(min_B[x], y)
		maxi_B[x] = max(maxi_B[x], y)
	A = list(min_B.keys())
	B = list(min_A.keys())
	A.sort()
	B.sort()
	AR = I_N_F()
	(PRF, SFF) = ([], [])
	(mn, mx) = (I_N_F(), N_INF())
	for x in A:
		(mn, mx) = (min(mn, min_B[x]), max(mx, maxi_B[x]))
		PRF.append((x - A[0]) * (mx - mn))
	(mn, mx) = (I_N_F(), N_INF())
	for x in A[-1::-1]:
		(mn, mx) = (min(mn, min_B[x]), max(mx, maxi_B[x]))
		SFF.append((A[0 - 1] - x) * (mx - mn))
	SFF = SFF[-1::-1]
	SFF.append(0)
	for i in range(len(A)):
		AR = min(AR, PRF[i - 1 + 1] + SFF[i + 1])
	(PRF, SFF) = ([], [])
	(mn, mx) = (I_N_F(), N_INF())
	for y in B:
		(mn, mx) = (min(mn, min_A[y]), max(mx, maxi_A[y]))
		PRF.append((y - B[0]) * (mx - mn))
	(mn, mx) = (I_N_F(), N_INF())
	for y in B[-1::-1]:
		(mn, mx) = (min(mn, min_A[y]), max(mx, maxi_A[y]))
		SFF.append((B[-1] - y) * (mx - mn))
	SFF = SFF[-1::-1]
	SFF.append(0)
	for i in range(len(B)):
		AR = min(AR, PRF[i] + SFF[i + 1])
	return AR
test_case = int(input())
for _ in range(test_case):
	num = int(input())
	point = []
	for i in range(num):
		li = list(map(int, input().split()))
		point.append(li)
	z = result(point)
	print(z)


from collections import defaultdict

def neginf():
	return float('-inf')

def inf():
	return float('inf')

def getArea(p):
	(minmX, maxmX) = (defaultdict(inf), defaultdict(neginf))
	(minmY, maxmY) = (defaultdict(inf), defaultdict(neginf))
	for (x, y) in p:
		minmX[y] = min(minmX[y], x)
		maxmX[y] = max(maxmX[y], x)
		minmY[x] = min(minmY[x], y)
		maxmY[x] = max(maxmY[x], y)
	X = list(minmY.keys())
	Y = list(minmX.keys())
	X.sort()
	Y.sort()
	area = inf()
	(p, s) = ([], [])
	(mn, mx) = (inf(), neginf())
	for x in X:
		(mn, mx) = (min(mn, minmY[x]), max(mx, maxmY[x]))
		p.append((x - X[0]) * (mx - mn))
	(mn, mx) = (inf(), neginf())
	for x in X[-1::-1]:
		(mn, mx) = (min(mn, minmY[x]), max(mx, maxmY[x]))
		s.append((X[-1] - x) * (mx - mn))
	s = s[-1::-1]
	s.append(0)
	for i in range(len(X)):
		area = min(area, p[i - 1 + 1] + s[i + 1])
	(p, s) = ([], [])
	(mn, mx) = (inf(), neginf())
	for y in Y:
		(mn, mx) = (min(mn, minmX[y]), max(mx, maxmX[y]))
		p.append((y - Y[0]) * (mx - mn))
	(mn, mx) = (inf(), neginf())
	for y in Y[-1::-1]:
		(mn, mx) = (min(mn, minmX[y]), max(mx, maxmX[y]))
		s.append((Y[-1] - y) * (mx - mn))
	s = s[-1::-1]
	s.append(0)
	for i in range(len(Y)):
		area = min(area, p[i] + s[i + 1])
	return area
t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for i in range(n):
		l = list(map(int, input().split()))
		p.append(l)
	ans = getArea(p)
	print(ans)


import sys
input = sys.stdin.readline
T = int(input())

def solve(point):
	point = sorted(point, key=lambda x: (-x[1], x[0]))
	n = len(point)
	if n == 1:
		return 0
	Lx = [[0, 0] for _ in range(n)]
	Ly = [[0, 0] for _ in range(n)]
	Rx = [[0, 0] for _ in range(n)]
	Ry = [[0, 0] for _ in range(n)]
	Lx[0][0] = Rx[0][0] = point[0][0]
	Ly[0][0] = Ry[0][0] = point[0][1]
	for i in range(1, n):
		Lx[i][0] = min(Lx[i - 1][0], point[i][0])
		Rx[i][0] = max(Rx[i - 1][0], point[i][0])
		Ly[i][0] = min(Ly[i - 1][0], point[i][1])
		Ry[i][0] = max(Ry[i - 1][0], point[i][1])
	Lx[n - 1][1] = Rx[n - 1][1] = point[n - 1][0]
	Ly[n - 1][1] = Ry[n - 1][1] = point[n - 1][1]
	for i in range(n - 2, -1, -1):
		Lx[i][1] = min(Lx[i + 1][1], point[i][0])
		Rx[i][1] = max(Rx[i + 1][1], point[i][0])
		Ly[i][1] = min(Ly[i + 1][1], point[i][1])
		Ry[i][1] = max(Ry[i + 1][1], point[i][1])
	ans = 10 ** 18
	s = [[0, 0] for _ in range(n)]
	for i in range(n):
		s[i][0] = (Rx[i][0] - Lx[i][0]) * (Ry[i][0] - Ly[i][0])
		s[i][1] = (Rx[i][1] - Lx[i][1]) * (Ry[i][1] - Ly[i][1])
		if i:
			ans = min(ans, s[i][1] + s[i - 1][0])
	return ans
for tt in range(T):
	n = int(input())
	point = [[0, 0] for _ in range(n)]
	for i in range(n):
		(point[i][0], point[i][1]) = map(int, input().split())
	ans = solve(point)
	for i in range(n):
		point[i] = [point[i][1], point[i][0]]
	ans = min(ans, solve(point))
	print(ans)