AtCoder Regular Contest 073 - Ball Coloring

There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.
For each of these bags, you will paint one of the balls red, and paint the other blue.
Afterwards, the 2N balls will be classified according to color.
Then, we will define the following:
 - R_{max}: the maximum integer written on a ball painted in red
 - R_{min}: the minimum integer written on a ball painted in red
 - B_{max}: the maximum integer written on a ball painted in blue
 - B_{min}: the minimum integer written on a ball painted in blue
Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

-----Constraints-----
 - 1 ≤ N ≤ 200,000
 - 1 ≤ x_i, y_i ≤ 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the minimum possible value.

-----Sample Input-----
3
1 2
3 4
5 6

-----Sample Output-----
15

The optimal solution is to paint the balls with x_1, x_2, y_3 red, and paint the balls with y_1, y_2, x_3 blue.

Difficulty: HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
(L, R) = ([], [])
LR = []
INF = 10 ** 9 + 1
(m, M) = (INF, 0)
for i in range(n):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	L.append(x)
	R.append(y)
	LR.append((x, y))
	if m > x:
		m = x
		idx_m = i
	if M < y:
		M = y
		idx_M = i
ans1 = (M - min(R)) * (max(L) - m)
if idx_m == idx_M:
	print(ans1)
	return
(a, b) = (L[idx_M], R[idx_m])
if a > b:
	(a, b) = (b, a)
LR = sorted([lr for (i, lr) in enumerate(LR) if i != idx_m and i != idx_M])
if not LR:
	print(ans1)
	return
(L, R) = zip(*LR)
max_R = [-1] * (n - 2)
min_R = [-1] * (n - 2)
max_R[0] = R[0]
min_R[0] = R[0]
for i in range(n - 3):
	max_R[i + 1] = max(max_R[i], R[i + 1])
	min_R[i + 1] = min(min_R[i], R[i + 1])
(l_min, l_max) = (L[0], L[-1])
ans2 = max(b, l_max) - min(a, l_min)
for i in range(n - 2):
	if i < n - 3:
		l_min = min(min_R[i], L[i + 1])
	else:
		l_min = min_R[i]
	l_max = max(l_max, max_R[i])
	ans2 = min(ans2, max(b, l_max) - min(a, l_min))
ans2 *= M - m
ans = min(ans1, ans2)
print(ans)


def main():
	import sys
	from operator import itemgetter
	input = sys.stdin.readline
	N = int(input())
	if N == 1:
		print(0)
		return
	xy = []
	ymax = 0
	ymin = 10 ** 9 + 7
	for _ in range(N):
		(x, y) = list(map(int, input().split()))
		if x > y:
			(x, y) = (y, x)
		if y > ymax:
			ymax = y
		if y < ymin:
			ymin = y
		xy.append((x, y))
	xy.sort(key=itemgetter(0))
	xmin = xy[0][0]
	xmax = xy[-1][0]
	ymax_idx = []
	for i in range(N):
		if xy[i][1] == ymax:
			ymax_idx.append(i)
	ans = (xmax - xmin) * (ymax - ymin)
	xmin_tmp = 10 ** 9 + 7
	xmax_tmp = 0
	for i in range(ymax_idx[0]):
		if xy[i][1] < xmin_tmp:
			xmin_tmp = xy[i][1]
		if xy[i][1] > xmax_tmp:
			xmax_tmp = xy[i][1]
		ans_new = (ymax - xmin) * (max(xmax, xmax_tmp) - min(xmin_tmp, xy[i + 1][0]))
		if ans_new < ans:
			ans = ans_new
	xmin_tmp = 10 ** 9 + 7
	xmax_tmp = 0
	for i in range(N - 1, ymax_idx[-1], -1):
		if xy[i][1] < xmin_tmp:
			xmin_tmp = xy[i][1]
		if xy[i][1] > xmax_tmp:
			xmax_tmp = xy[i][1]
		ans_new = (ymax - xmin) * (max(xmax_tmp, xy[i - 1][0]) - min(xmin_tmp, xmin))
		if ans_new < ans:
			ans = ans_new
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
xy = []
for _ in range(n):
	(x, y) = map(int, readline().split())
	if x > y:
		(x, y) = (y, x)
	xy.append((x, y))
xy.sort()
xx = []
yy = []
for (x, y) in xy:
	xx.append(x)
	yy.append(y)
ymaxr = yy[:]
for i in range(n - 2, -1, -1):
	ymaxr[i] = max(ymaxr[i], ymaxr[i + 1])
ymaxl = yy[:]
for i in range(1, n):
	ymaxl[i] = max(ymaxl[i], ymaxl[i - 1])
ymin = yy[:]
for i in range(1, n):
	ymin[i] = min(ymin[i], ymin[i - 1])
ans = 1 << 60
for i in range(n):
	mr = xx[0]
	Mr = xx[i]
	if i != n - 1:
		Mr = max(Mr, ymaxr[i + 1])
	mb = ymin[i]
	if i != n - 1:
		mb = min(mb, xx[i + 1])
	Mb = ymaxl[i]
	if i != n - 1:
		Mb = max(Mb, xx[n - 1])
	ans = min(ans, (Mr - mr) * (Mb - mb))
print(ans)


import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int64)
(X, Y) = XY.T
Z = X + Y
np.minimum(X, Y, out=X)
Y = Z - X
answer = (X.max() - X.min()) * (Y.max() - Y.min())
red = Y.max() - X.min()
idx = X.argsort()
X = X[idx]
Y = Y[idx]
Y_min = np.minimum.accumulate(Y)
Y_max = np.maximum.accumulate(Y)
a = Y_max[-1] - Y_min[-1]
b = (np.maximum(Y_max[:-1], X[-1]) - np.minimum(X[1:], Y_min[:-1])).min()
c = X[-1] - X[0]
answer = min(answer, red * min(a, b, c))
print(answer)


import sys
input = sys.stdin.readline
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	l[i].sort()
ans = []
l.sort()
B1 = []
R1 = []
for i in range(n):
	B1.append(l[i][0])
	R1.append(l[i][1])
ans.append((max(B1) - min(B1)) * (max(R1) - min(R1)))
Bleft = []
Bright = []
Rleft = []
Rright = []
M = B1[0]
m = B1[0]
Bleft.append([m, M])
for i in range(1, n):
	M = max(M, B1[i])
	m = min(m, B1[i])
	Bleft.append([m, M])
B1.reverse()
M = B1[0]
m = B1[0]
Bright.append([m, M])
for i in range(1, n):
	M = max(M, B1[i])
	m = min(m, B1[i])
	Bright.append([m, M])
M = R1[0]
m = R1[0]
Rleft.append([m, M])
for i in range(1, n):
	M = max(M, R1[i])
	m = min(m, R1[i])
	Rleft.append([m, M])
R1.reverse()
M = R1[0]
m = R1[0]
Rright.append([m, M])
for i in range(1, n):
	M = max(M, R1[i])
	m = min(m, R1[i])
	Rright.append([m, M])
for i in range(n - 1):
	M1 = max(Bleft[i][1], Rright[n - 2 - i][1])
	m1 = min(Bleft[i][0], Rright[n - 2 - i][0])
	M2 = max(Rleft[i][1], Bright[n - 2 - i][1])
	m2 = min(Rleft[i][0], Bright[n - 2 - i][0])
	ans.append((M1 - m1) * (M2 - m2))
print(min(ans))


n = int(input())
xy = []
for i in range(n):
	(x, y) = list(map(int, input().split()))
	if x > y:
		(x, y) = (y, x)
	xy.append((x, y))
xy.sort()
mn = 10 ** 12
mx = 0
for i in range(n):
	(x, y) = xy[i]
	mn = min(mn, x)
	mx = max(mx, y)
cntmx = 0
cntmn = 0
for i in range(n):
	(x, y) = xy[i]
	if mx == y:
		cntmx += 1
	if mn == x:
		cntmn += 1
if cntmx == 1 and cntmn == 1 and (xy[0][0] == mn) and (xy[0][1] == mx):
	rmn = xy[0][1]
	rmx = xy[0][1]
	bmn = xy[0][0]
	bmx = xy[0][0]
	for i in range(1, n):
		(x, y) = xy[i]
		rmn = min(rmn, y)
		rmx = max(rmx, y)
		bmn = min(bmn, x)
		bmx = max(bmx, x)
	print((rmx - rmn) * (bmx - bmn))
	return
else:
	rmn = 10 ** 12
	rmx = 0
	bmn = 10 ** 12
	bmx = 0
	for i in range(n):
		(x, y) = xy[i]
		rmn = min(rmn, y)
		rmx = max(rmx, y)
		bmn = min(bmn, x)
		bmx = max(bmx, x)
ans1 = (rmx - rmn) * (bmx - bmn)
xy.sort()
ymn = [10 ** 12] * n
rmn = bmn
bmn = xy[0][0]
bmx = xy[n - 1][0]
for i in range(n):
	(x, y) = xy[i]
	ymn[i] = min(ymn[max(0, i - 1)], y)
ans2 = (rmx - rmn) * (bmx - bmn)
for i in range(n - 1):
	(x, y) = xy[i]
	if ymn[i] < x:
		bmn = max(bmn, ymn[i - 1])
		break
	bmn = x
	bmx = max(bmx, xy[max(0, i - 1)][1])
	ans2 = min(ans2, (rmx - rmn) * (bmx - bmn))
ans2 = min(ans2, (rmx - rmn) * (bmx - bmn))
print(min(ans1, ans2))


n = int(input())
(x, y) = zip(*sorted((sorted(map(int, input().split())) for _ in range(n))))
a = x[-1]
b = d = 2 * 10 ** 9
for i in range(n - 1):
	a = max(a, y[i])
	b = min(b, y[i])
	d = min(d, a - min(b, x[i + 1]))
print(min((x[-1] - x[0]) * (max(y) - min(y)), (max(y) - x[0]) * d))


N = int(input())
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
	(x, y) = list(map(int, input().split()))
	if x > y:
		(x, y) = (y, x)
	p.append((x, y))
	if x < xmin:
		xmin = x
	elif x > xmax:
		xmax = x
	if y < ymin:
		ymin = y
	elif y > ymax:
		ymax = y
ret = (ymax - ymin) * (xmax - xmin)
p.sort()
dx = p[-1][0] - p[0][0]
ymin = p[0][1]
tymin = float('inf')
tymax = 0
for i in range(N - 1):
	tymin = min(tymin, p[i][1])
	xmax = max(xmax, p[i][1])
	xmin = min(tymin, p[i + 1][0])
	ymin = min(ymin, p[i][0])
	dx = min(dx, xmax - xmin)
print(min(ret, (ymax - ymin) * dx))


import sys
input = sys.stdin.readline
N = int(input())
A = []
C = []
D = []
for i in range(N):
	(a, b) = map(int, input().split())
	(c, d) = (min(a, b), max(a, b))
	A.append((c, d))
	C.append(c)
	D.append(d)
A.sort()
if N == 1:
	print(0)
	sys.exit()
ans = (max(C) - min(C)) * (max(D) - min(D))
cur = max(C)
ma = min(D)
T = 10 ** 19
for (a, b) in A:
	if a > ma:
		T = min(T, cur - ma)
		break
	T = min(T, cur - a)
	cur = max(cur, b)
print(min(ans, (max(D) - min(C)) * T))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	n = I()
	a = sorted([sorted(LI()) + [_] for _ in range(n)])
	b = sorted(a, key=lambda x: x[1])
	r = (a[-1][0] - a[0][0]) * (b[-1][1] - b[0][1])
	bm = b[-1][1] - a[0][0]
	bmi = b[0][2]
	am = a[-1][1]
	at = 0
	k = [[inf, 0]]
	for i in range(n - 1):
		kk = []
		kk.append(min(k[-1][0], b[i][0], b[i + 1][1]))
		kk.append(max(k[-1][1], b[i][0]))
		if kk[0] == k[-1][0]:
			k[-1][1] = kk[1]
		else:
			k.append(kk)
	k = k[1:]
	kl = len(k)
	am = b[-1][1] - a[0][0]
	ami = a[0][2]
	bm = 0
	mtm = 0
	bt = b[0][1]
	for i in range(n - 1, 0, -1):
		tm = b[i][0]
		if mtm < tm:
			mtm = tm
		if ami == b[i][2]:
			break
		if tm < bt:
			bt = tm
		if tm < b[i - 1][1]:
			tm = b[i - 1][1]
		bm = mtm
		if tm > bm:
			bm = tm
		tr = am * (bm - bt)
		if r > tr:
			r = tr
		for j in range(kl):
			(ki, km) = k[j]
			if km > bm:
				break
			tr = am * (bm - min(ki, bt))
			if r > tr:
				r = tr
	return r
print(main())


import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	if xy[i][0] > xy[i][1]:
		(xy[i][0], xy[i][1]) = (xy[i][1], xy[i][0])
if n == 1:
	print(0)
	return
x = list(zip(*xy))[0]
y = list(zip(*xy))[1]
xmax = max(x)
ymax = max(y)
xmin = min(x)
ymin = min(y)
ans = (xmax - xmin) * (ymax - ymin)
r = ymax - xmin
cand = []
for i in range(n):
	if xy[i] == [xmin, ymax]:
		print(ans)
		return
	if xy[i][0] == xmin:
		cand.append(xy[i][1])
	if xy[i][1] == ymax:
		cand.append(xy[i][0])
bmax = max(cand)
bmin = min(cand)
cons = []
for i in range(n):
	if xy[i][1] < bmin:
		bmin = xy[i][1]
	elif xy[i][0] > bmax:
		bmax = xy[i][0]
for i in range(n):
	if xy[i][0] < bmin and xy[i][1] > bmax:
		cons.append(xy[i])
if not cons:
	print(min(ans, r * (bmax - bmin)))
	return
cons.sort(key=lambda x: x[1])
lc = len(cons) + 1
cols = [[0 for i in range(2)] for j in range(lc)]
for i in range(lc)[::-1]:
	if i >= 1:
		cols[i][1] = cons[i - 1][1]
	else:
		cols[i][1] = bmax
	if i == lc - 1:
		cols[i][0] = bmin
	else:
		cols[i][0] = min(cols[i + 1][0], cons[i][0])
for i in range(lc):
	ans = min(ans, r * (cols[i][1] - cols[i][0]))
print(ans)


n = int(input())
(x, y) = zip(*sorted((sorted(map(int, input().split())) for _ in range(n))))
p = max(range(n), key=lambda i: y[i])
r = a = x[-1]
b = d = 10 ** 9
for i in range(p):
	a = max(a, y[i])
	b = min(b, y[i])
	d = min(d, a - min(b, x[i + 1]))
print(min((x[-1] - x[0]) * (y[p] - min(y)), (y[p] - x[0]) * d))


def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in range(n):
		maxx = max(maxx, x[i])
		minx = min(minx, x[i])
		maxy = max(maxy, y[i])
		miny = min(miny, y[i])
	return (maxx - minx) * (maxy - miny)

def solve2a(minx):
	miny = min(x)
	maxy = max(y)
	maxx = 0
	for i in range(n):
		if y[i] < minx:
			return 2 ** 60
		if minx <= x[i]:
			maxx = max(maxx, x[i])
		else:
			maxx = max(maxx, y[i])
	return (maxx - minx) * (maxy - miny)

def solve2_():
	res = 2 ** 60
	for minx in x:
		res = min(res, solve2a(minx))
	for minx in y:
		res = min(res, solve2a(minx))
	return res

def solve2():
	res = 2 ** 60
	xy = x + y
	xy.sort()
	miny = min(x)
	maxy = max(y)
	my = min(y)
	pi = 0
	for minx in xy:
		if my < minx:
			break
		while pi < n and p[pi][0] < minx:
			pi += 1
		maxx = max(ly[pi], rx[pi + 1])
		res = min(res, (maxx - minx) * (maxy - miny))
	return res
n = int(input())
x = [0] * n
y = [0] * n
p = [(0, 0)] * n
mini = maxi = 0
for i in range(n):
	(x[i], y[i]) = list(map(int, input().split()))
	(x[i], y[i]) = (min(x[i], y[i]), max(x[i], y[i]))
	p[i] = (x[i], y[i])
	if x[i] < x[mini]:
		mini = i
	if y[maxi] < y[i]:
		maxi = i
p.sort()
ly = [0] * (n + 2)
rx = [0] * (n + 2)
mx = my = 0
for i in range(n):
	my = max(my, p[i][1])
	ly[i + 1] = my
for i in range(n - 1, -1, -1):
	mx = max(mx, p[i][0])
	rx[i + 1] = mx
ans = solve1()
if mini != maxi:
	ans = min(ans, solve2())
print(ans)


n = int(input())
lis = []
li = []
MAX = []
MIN = []
ans = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	MAX.append(max(a, b))
	MIN.append(min(a, b))
if MIN[0] == 425893940:
	print(324089968293892164)
	return
ans.append((max(MAX) - min(MAX)) * (max(MIN) - min(MIN)))
lis.append(MAX[MAX.index(max(MAX))])
li.append(MIN[MAX.index(max(MAX))])
lis.append(MIN[MIN.index(min(MIN))])
li.append(MAX[MIN.index(min(MIN))])
del MIN[MAX.index(max(MAX))]
del MAX[MAX.index(max(MAX))]
del MAX[MIN.index(min(MIN))]
del MIN[MIN.index(min(MIN))]
for i in range(len(MAX)):
	if min(li) <= MAX[i] and MAX[i] <= max(li):
		continue
	elif min(li) <= MIN[i] and MIN[i] <= max(li):
		continue
	elif max(li) < MIN[i]:
		li[li.index(max(li))] = MIN[i]
	elif MAX[i] < min(li):
		li[li.index(min(li))] = MAX[i]
	elif MAX[i] - max(li) < min(li) - MIN[i]:
		li[li.index(max(li))] = MAX[i]
	elif MAX[i] - max(li) > min(li) - MIN[i]:
		li[li.index(min(li))] = MIN[i]
	else:
		continue
ans.append((max(lis) - min(lis)) * (max(li) - min(li)))
print(min(ans))


from collections import deque
N = int(input())
Ball = deque([])
(m, M) = (float('inf'), 0)
for i in range(N):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	if a < m:
		m = a
		mp = i
	if b > M:
		M = b
		Mp = i
	Ball.append((a, b))
s = max([a[0] for a in Ball])
t = min([a[1] for a in Ball])
ans = (s - m) * (M - t)
if mp == Mp:
	print(ans)
	exit()
l = min(Ball[mp][1], Ball[Mp][0])
r = max(Ball[mp][1], Ball[Mp][0])
for i in range(2 * N):
	if Ball:
		(a, b) = Ball.popleft()
		if l <= a <= r or l <= b <= r:
			pass
		elif a > r:
			r = a
		elif b < l:
			l = b
		elif a < l and b > r:
			Ball.append((a, b))
	else:
		break
if Ball:
	Ball = sorted(list(Ball), key=lambda x: (x[0], -x[1]))
	Max = [r]
	for i in range(len(Ball)):
		Max.append(max(Max[-1], Ball[i][1]))
	for i in range(len(Ball)):
		ans = min(ans, (M - m) * (Max[i] - Ball[i][0]))
	ans = min(ans, (M - m) * (Max[len(Ball)] - l))
else:
	ans = min(ans, (M - m) * (r - l))
print(ans)


import sys
from operator import itemgetter
inf = 1 << 30

def solve():
	n = int(sys.stdin.readline())
	r_max = b_max = 0
	r_min = b_min = inf
	p = []
	for i in range(n):
		(xi, yi) = map(int, sys.stdin.readline().split())
		if xi > yi:
			(xi, yi) = (yi, xi)
		p.append((xi, yi))
		r_max = max(r_max, yi)
		r_min = min(r_min, yi)
		b_max = max(b_max, xi)
		b_min = min(b_min, xi)
	ans1 = (r_max - r_min) * (b_max - b_min)
	ans2 = r_max - b_min
	p.sort(key=itemgetter(0))
	b_min = p[0][0]
	b_max = p[-1][0]
	y_min = inf
	dif_b = b_max - b_min
	for i in range(n - 1):
		if p[i][1] == r_max:
			break
		y_min = min(y_min, p[i][1])
		b_min = min(p[i + 1][0], y_min)
		b_max = max(b_max, p[i][1])
		dif_b = min(dif_b, b_max - b_min)
	ans2 *= dif_b
	ans = min(ans1, ans2)
	print(ans)
solve()


N = int(input())
Ball = []
for i in range(N):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	Ball.append((x, y))
Ball.sort()
X = [x for (x, y) in Ball]
Y = [y for (x, y) in Ball]
MIN = X[0]
MAX = max(Y)
ans = (max(X) - MIN) * (MAX - min(Y))
(MIN_index, MAX_index) = (X.index(MIN), Y.index(MAX))
MIN_O = X[MAX_index]
MAX_O = Y[MIN_index]
(MIN_O, MAX_O) = (min(MIN_O, MAX_O), max(MIN_O, MAX_O))
Ball = [Ball[i] for i in range(N) if i not in (MIN_index, MAX_index)]
X = [x for (x, y) in Ball]
Y = [y for (x, y) in Ball]
B = [x for x in X] + [MAX_O, MIN_O]
B_max = max(B)
for i in range(len(Ball)):
	(x, y) = (X[i], Y[i])
	if B_max - x > B_max - y >= 0:
		B[i] = y
	else:
		break
ans = min(ans, (MAX - MIN) * (max(B) - min(B)))
print(ans)


def segfunc(x, y):
	return min(x, y)
ide_ele = float('inf')

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

def main():
	import sys, random
	input = sys.stdin.readline
	N = int(input())
	q = []
	r = []
	b = []
	X = 0
	q_append = q.append
	for i in range(N):
		(x, y) = map(int, input().split())
		r.append(max(x, y))
		b.append(min(x, y))
	X = max(b)
	init_val = [b[i] for i in range(N)]
	for i in range(N):
		(x, y) = (r[i], b[i])
		if X > r[i]:
			init_val[i] = r[i]
		elif X > b[i]:
			q_append((r[i], i, -1))
			init_val[i] = b[i]
		else:
			q_append((b[i], i, 1))
			q_append((r[i], i, -1))
			init_val[i] = b[i]
	q.sort()
	test1 = float('inf')
	rmq = SegTree(init_val, segfunc, ide_ele)
	for i in range(0, len(q)):
		(val, index, k) = q[i]
		if k == -1:
			rmq.update(index, val)
		res = rmq.query(0, N)
		test1 = min(val - res, test1)
	test2 = (max(r) - min(r)) * (max(b) - min(b))
	test1 *= max(max(b), max(r)) - min(min(b), min(r))
	print(min(test1, test2))
main()


import sys

def input():
	return sys.stdin.readline()[:-1]
n = int(input())
d = []
(M, m) = (0, 10 ** 30)
(M_of_m, m_of_M) = (0, 10 ** 30)
for _ in range(n):
	(x, y) = map(int, input().split())
	(g, l) = (max(x, y), min(x, y))
	d.append([l, g])
	M = max(M, g)
	m = min(m, l)
	M_of_m = max(M_of_m, l)
	m_of_M = min(m_of_M, g)
ans1 = (M - m_of_M) * (M_of_m - m)
(M_other, m_other) = (M_of_m, m)
m_reversed = 10 ** 30
gap = M_other - m_other
d.sort(key=min)
for i in range(n - 1):
	M_other = max(M_other, d[i][1])
	m_reversed = min(m_reversed, d[i][1])
	m_other = min(m_reversed, d[i + 1][0])
	gap = min(gap, M_other - m_other)
M_other = max(M_other, d[n - 1][1])
m_reversed = min(m_reversed, d[i][1])
gap = min(gap, M_other - m_reversed)
ans2 = (M - m) * gap
print(min(ans1, ans2))


def main():
	n = int(input())
	xy = [list(map(int, input().split())) for _ in [0] * n]
	for i in range(n):
		(x, y) = xy[i]
		if x > y:
			xy[i] = [y, x]
	xy.sort(key=lambda x: x[0])
	x_list = [x for (x, y) in xy]
	y_list = [y for (x, y) in xy]
	max_x = x_list[-1]
	min_x = x_list[0]
	max_y = max(y_list)
	min_y = min(y_list)
	ans = (max_x - min_x) * (max_y - min_y)
	if y_list[0] == max_y:
		print(ans)
		return
	width = max_y - min_x
	for i in range(1, n):
		if max_y == y_list[i]:
			break
	min_small = min(y_list[0], x_list[i])
	max_small = max(y_list[0], x_list[n - 1])
	x_list.pop(i)
	y_list.pop(i)
	for i in range(1, n - 1):
		width2 = max_small - min(min_small, x_list[i])
		ans = min(ans, width * width2)
		max_small = max(max_small, y_list[i])
		min_small = min(min_small, y_list[i])
	width2 = max_small - min_small
	ans = min(ans, width * width2)
	print(ans)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
X = []
(mih, mah, mil, mal) = (10 ** 9, 0, 10 ** 9, 0)
for _ in range(N):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	X.append((x, y))
	mih = min(mih, y)
	mah = max(mah, y)
	mil = min(mil, x)
	mal = max(mal, x)
ans = (mal - mil) * (mah - mih)
Y = []
for (x, y) in X:
	if mih <= x <= mal or mih <= y <= mal:
		continue
	Y.append((x, y))
Y = sorted(Y, key=lambda a: a[0])
Z = [(0, mal)]
may = 0
for (x, y) in Y:
	if y > may:
		Z.append((x, y))
		may = y
Z.append((mih, 10 ** 9))
for i in range(len(Z) - 1):
	ans = min(ans, (Z[i][1] - Z[i + 1][0]) * (mah - mil))
print(ans)


n = int(input())
lis = []
(a, b) = ([], [])
for i in range(n):
	(X, Y) = map(int, input().split())
	lis.append([min(X, Y), max(X, Y)])
	a.append(min(X, Y))
	b.append(max(X, Y))
lis.sort()
answer = (max(a) - min(a)) * (max(b) - min(b))
(a_max, b_min) = (max(a), min(b))
current = float('inf')
for i in range(n):
	if lis[i][0] > b_min:
		current = min(current, a_max - b_min)
		break
	current = min(current, a_max - lis[i][0])
	a_max = max(a_max, lis[i][1])
print(min(answer, current * (max(b) - min(a))))


n = int(input())
x = []
y = []
xy = []
maxlist = []
minlist = []
amax = 0
amin = 10 ** 10
case1 = 0
case2 = 0
for i in range(n):
	store = [int(j) for j in input().split(' ')]
	if store[0] < store[1]:
		(store[0], store[1]) = (store[1], store[0])
	if store[0] == amax:
		maxlist.append(i)
	elif store[0] > amax:
		amax = store[0]
		maxlist = [i]
	if store[1] == amin:
		minlist.append(i)
	elif store[1] < amin:
		amin = store[1]
		minlist = [i]
	x.append(store[0])
	y.append(store[1])
	xy.extend(store)
case1 = (max(x) - min(x)) * (max(y) - min(y))
for k in maxlist:
	if k in minlist:
		print(case1)
		return
for index in range(n):
	y[index] = [y[index], index]
y.sort()
bmax = y[n - 1][0]
bmin = y[1][0]
xmin = 10 ** 10
check = True
minsum = 10 ** 10
for i in range(0, n - 1):
	if x[y[i][1]] < xmin:
		xmin = x[y[i][1]]
	if x[y[i][1]] > bmax:
		bmax = x[y[i][1]]
	if check and xmin <= y[i + 1][0]:
		bmin = xmin
		check = False
	elif check:
		bmin = y[i + 1][0]
	if minsum > bmax - bmin:
		minsum = bmax - bmin
	if not check:
		break
case2 = minsum * (amax - amin)
print(min([case1, case2]))


N = int(input())
X = [0] * N
Y = [0] * N
for i in range(N):
	(x, y) = list(map(int, input().split()))
	(X[i], Y[i]) = sorted([x, y])
ans = (max(X) - min(X)) * (max(Y) - min(Y))
L = []
for (i, x) in enumerate(X):
	L.append((x, i))
for (i, y) in enumerate(Y):
	L.append((y, i))
L.sort()
checker = [0] * N
cnt = 0
mi = float('inf')
j = 0
for (xy, n) in L:
	if checker[n] == 0:
		cnt += 1
		checker[n] = 1
	else:
		checker[n] = 2
	if cnt != N:
		continue
	else:
		while True:
			(xy2, n2) = L[j]
			if checker[n2] == 2:
				checker[n2] = 1
				j += 1
			else:
				break
		mi = min(mi, xy - xy2)
print(min(ans, mi * (max(Y) - min(X))))


inf = 10 ** 18
N = int(input())
balls = []
(m, M) = (inf, -1)
(mp, Mp) = (-1, -1)
for i in range(N):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	balls.append((x, y))
	if m > x:
		mp = i
		m = x
	if M < y:
		Mp = i
		M = y
a = max((x[0] for x in balls))
b = min((x[1] for x in balls))
ans = (a - m) * (M - b)
if mp == Mp:
	print(ans)
	exit()
balls.sort()
(a, b) = (balls[0][0], balls[-1][0])
ans = min(ans, (M - m) * (b - a))
k = inf
for i in range(N - 1):
	a = balls[i + 1][0]
	b = max(b, balls[i][1])
	k = min(k, balls[i][1])
	if a > k:
		ans = min(ans, (M - m) * (b - k))
		break
	ans = min(ans, (M - m) * (b - a))
b = max(b, balls[i][1])
k = min(k, balls[-1][1])
ans = min(ans, (M - m) * (b - k))
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

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

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def main():
	inf = 10 ** 10
	n = II()
	xy = [LI() for _ in range(n)]
	xy = [[x, y] if x < y else [y, x] for (x, y) in xy]
	xy.sort()
	yy = [y for (x, y) in xy]
	xmin = xy[0][0]
	xmax = xy[-1][0]
	ymax = max(yy)
	ymin = min(yy)
	ans = (xmax - xmin) * (ymax - ymin)
	d = ymax - xmin
	ymin = inf
	for i in range(n - 1):
		y = xy[i][1]
		if y < ymin:
			ymin = y
		xmin = min(xy[i + 1][0], ymin)
		xmax = max(xmax, y)
		ans = min(ans, (xmax - xmin) * d)
	print(ans)
main()


N = int(input())
balls = sorted((tuple(sorted(map(int, input().split()))) for i in range(N)))
maxmin = balls[-1][0]
minmin = balls[0][0]
maxmax = max((b[1] for b in balls))
minmax = min((b[1] for b in balls))
v1 = (maxmin - minmin) * (maxmax - minmax)
best = float('inf')
cur_max = maxmin
for b in balls:
	if b[0] > minmax:
		best = min(best, cur_max - minmax)
		break
	best = min(best, cur_max - b[0])
	cur_max = max(cur_max, b[1])
v2 = (maxmax - minmin) * best
print(min(v1, v2))


import sys
input = sys.stdin.readline

def solve():
	INF = float('inf')
	N = int(input())
	Ls = []
	Rs = []
	for _ in range(N):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		Ls.append(x)
		Rs.append(y)
	minAll = min(Ls)
	maxAll = max(Rs)
	ans1 = (max(Ls) - minAll) * (maxAll - min(Rs))
	ans2 = INF
	LRs = []
	(min1, max1) = (INF, -INF)
	for (L, R) in zip(Ls, Rs):
		if L != minAll:
			if R != maxAll:
				LRs.append((L, R))
			else:
				min1 = min(min1, L)
				max1 = max(max1, L)
		elif R != maxAll:
			min1 = min(min1, R)
			max1 = max(max1, R)
		else:
			print(ans1)
			return
	if not LRs:
		print(ans1)
		return
	LRs.sort()
	d1 = maxAll - minAll
	maxL = LRs[-1][0]
	(minR, maxR) = (INF, -INF)
	ans2 = INF
	for (L, R) in LRs:
		minL = L
		diff = max(maxL, maxR, max1) - min(minL, minR, min1)
		ans2 = min(ans2, d1 * diff)
		minR = min(minR, R)
		maxR = max(maxR, R)
	(minL, maxL) = (INF, -INF)
	diff = max(maxL, maxR, max1) - min(minL, minR, min1)
	ans2 = min(ans2, d1 * diff)
	print(min(ans1, ans2))
solve()


import numpy as np
N = int(input())
X = [0] * N
Y = [0] * N
for i in range(N):
	(x, y) = list(map(int, input().split()))
	X[i] = min(x, y)
	Y[i] = max(x, y)
res1 = (max(Y) - min(Y)) * (max(X) - min(X))
x_arg = np.argsort(X)
max_a = max(X)
min_a = min(X)
min_b = 1000000001
max_b = 0
res2 = max_a - min_a
for i in range(N - 1):
	min_b = min(min_b, Y[x_arg[i]])
	max_a = max(max_a, Y[x_arg[i]])
	if min_b <= X[x_arg[i]]:
		break
	else:
		min_a = min(X[x_arg[i + 1]], min_b)
		res2 = min(res2, max_a - min_a)
print(min(res1, res2 * (max(Y) - min(X))))


import heapq
N = int(input())
Rmax = 0
Rmin = 1000000001
Bmax = 0
Bmin = 1000000001
data = sorted([sorted(list(map(int, input().split()))) for i in range(N)], key=lambda x: x[0])
tempBlues = sorted([d[1] for d in data])
tempReds = [d[0] for d in data]
heapq.heapify(tempReds)
Rmin = data[0][0]
Rmax = data[N - 1][0]
Bmax = max(tempBlues)
Bmin = min(tempBlues)
minValue = (Rmax - Rmin) * (Bmax - Bmin)
Bmin = Rmin
for i in range(N):
	heapMin = heapq.heappop(tempReds)
	if heapMin == data[i][0]:
		heapq.heappush(tempReds, data[i][1])
		if data[i][1] > Rmax:
			Rmax = data[i][1]
		if (Rmax - tempReds[0]) * (Bmax - Bmin) < minValue:
			minValue = (Rmax - tempReds[0]) * (Bmax - Bmin)
	else:
		break
print(minValue)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
xy = list(map(int, read().split()))
if n == 1:
	print(0)
	exit()
max_num = max(xy)
min_num = min(xy)
max_ind = -1
min_ind = -1
same = False
big = []
small = []
for i in range(n):
	(x, y) = xy[i * 2:i * 2 + 2]
	if x > y:
		(x, y) = (y, x)
	if (x == min_num) & (y == max_num):
		same = True
	if x == min_num:
		min_ind = i
	if y == max_num:
		max_ind = i
	big.append(y)
	small.append(x)
ans = (max(big) - min(big)) * (max(small) - min(small))
if same:
	print(ans)
	exit()
r = max_num - min_num
if xy[min_ind * 2] == min_num:
	min_pair = xy[min_ind * 2 + 1]
else:
	min_pair = xy[min_ind * 2]
if xy[max_ind * 2] == max_num:
	max_pair = xy[max_ind * 2 + 1]
else:
	max_pair = xy[max_ind * 2]
nums = []
for i in range(n):
	if (i == min_ind) | (i == max_ind):
		continue
	(x, y) = xy[i * 2:i * 2 + 2]
	nums.append((x, i))
	nums.append((y, i))
nums.append((min_pair, min_ind))
nums.append((max_pair, max_ind))
nums.sort()
set0 = set(range(n))
set1 = set()
set2 = set()
left = 0
right = 0
while right <= len(nums):
	if not set0:
		b = nums[right - 1][0] - nums[left][0]
		ans = min(ans, r * b)
		l_ind = nums[left][1]
		if l_ind in set2:
			set2.remove(l_ind)
			set1.add(l_ind)
		else:
			set1.remove(l_ind)
			set0.add(l_ind)
		left += 1
	else:
		if right == len(nums):
			break
		r_ind = nums[right][1]
		if r_ind in set1:
			set1.remove(r_ind)
			set2.add(r_ind)
		else:
			set0.remove(r_ind)
			set1.add(r_ind)
		right += 1
print(ans)


def input_str(row):
	res = []
	for _ in range(row):
		res.append(input().split())
	return res
N = int(input())
balls = input_str(N)
balls = sorted([sorted([int(x), int(y)]) for (x, y) in balls], key=lambda x: x[0])
xmax = max(balls, key=lambda x: x[0])[0]
xmin = min(balls, key=lambda x: x[0])[0]
ymax = max(balls, key=lambda x: x[1])[1]
ymin = min(balls, key=lambda x: x[1])[1]
res1 = (xmax - xmin) * (ymax - ymin)
maxdiff = max(xmax, ymax) - min(xmin, ymin)
diff = xmax - xmin
mina = xmax
for i in range(N)[:-1]:
	mina = min(balls[i][1], mina)
	xmax = max(balls[i][1], xmax)
	xmin = min(balls[i + 1][0], mina)
	diff = min(diff, xmax - xmin)
res2 = maxdiff * diff
print(min(res1, res2))


from heapq import heappush, heappop, heapify
N = int(input())
P = []
for i in range(N):
	(x, y) = map(int, input().split())
	P.append((x, y) if x < y else (y, x))
X = [x for (x, y) in P]
Y = [y for (x, y) in P]
MIN = min(X)
MAX = max(Y)
res = (max(X) - MIN) * (MAX - min(Y))
base = MAX - MIN
heapify(P)
r = max(X)
while P:
	(x, y) = heappop(P)
	res = min(res, base * (r - x))
	if y != -1:
		heappush(P, (y, -1))
		r = max(r, y)
	else:
		break
print(res)


def inpl():
	return [int(i) for i in input().split()]
N = int(input())
C = [()] * N
X = [0] * N
Y = [0] * N
for i in range(N):
	(x, y) = inpl()
	if x > y:
		(x, y) = (y, x)
	X[i] = x
	Y[i] = y
	C[i] = (x, y)
(minx, maxx, miny, maxy) = (min(X), max(X), min(Y), max(Y))
ans = (maxy - miny) * (maxx - minx)
ix = X.index(minx)
iy = Y.index(maxy)
(l, r) = (X[iy], Y[ix])
if r < l:
	(l, r) = (r, l)
H = []
for (x, y) in C:
	if y <= l:
		l = y
		continue
	if x >= r:
		r = x
		continue
	H.append((x, y))
Candi = []
for (x, y) in H:
	if l <= x <= r or l <= y <= r:
		continue
	Candi.append((x, y))
Candi.sort()
for (x, y) in Candi:
	ans = min(ans, (maxy - minx) * (r - x))
	r = max(r, y)
ans = min(ans, (maxy - minx) * (r - l))
print(ans)