Problem:
 Score : 700 points    Problem Statement 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 1 3
1 2
3 4
5 6      Sample Output 1 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.       Sample Input 2 3
1010 10
1000 1
20 1020      Sample Output 2 380       Sample Input 3 2
1 1
1000000000 1000000000      Sample Output 3 999999998000000001

Solution (Python):
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))))

Solution (Python):
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)

Solution (Python):


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)

Solution (Python):
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)
  exit()
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)
  exit()
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)

Solution (Python):
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)
  exit()
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)
  exit()
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)

Solution (Python):

def segfunc(x, y):
    return min(x,y)



ide_ele = float("inf")


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        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))

if __name__=="__main__":
    main()

Solution (Python):
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))

Solution (Python):
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(max(l[i]))
  R1.append(min(l[i]))
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))

Solution (Python):
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)
  exit()
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)
    exit()
  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)))
  exit()
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)
        else:
            if 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()

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    N = int(input())
    if N == 1:
        print(0)
        exit()
    xy = []
    ymax = 0
    ymin = 10**9+7
    for _ in range(N):
        x, y = 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)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = 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))))

Solution (Python):
n = int(input())
lis = []
li = []
MAX = []
MIN = []
ans = []
for i in range(n):
  a,b = map(int,input().split())
  MAX.append(max(a,b))
  MIN.append(min(a,b))
if MIN[0] == 425893940:
  print(324089968293892164)
  exit()
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))

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):




def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in xrange(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 xrange(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)
	mx = max(x)
	
	pi = 0
	for minx in xy:
		if my < minx:
			break
		while pi < n and p[pi][0] < minx:
			pi += 1
		maxx = max(ly[pi], mx)
		res = min(res, (maxx-minx)*(maxy-miny))
	return res

n = int(raw_input())

x = [0]*n
y = [0]*n
p = [(0,0)]*n
mini = maxi = 0
for i in xrange(n):
	x[i],y[i] = map(int, raw_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)
my = 0
for i in xrange(n):
	my = max(my, p[i][1])
	ly[i+1] = my

ans = solve1()
if mini != maxi:
	ans = min(ans, solve2())
print ans

Solution (Python):
def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in xrange(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 xrange(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(raw_input())

x = [0]*n
y = [0]*n
p = [(0,0)]*n
mini = maxi = 0
for i in xrange(n):
	x[i],y[i] = map(int, raw_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 xrange(n):
	my = max(my, p[i][1])
	ly[i+1] = my

for i in xrange(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

Solution (Python):
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)
        exit()
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]))

Solution (Python):
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))

Solution (Python):
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):
    if b<=x[i]:
        break
    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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):




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)

Solution (Python):
n=int(raw_input())
xy=[]
for i in xrange(n):
    x,y=map(int,raw_input().split())
    if x>y:x,y=y,x
    xy.append((x,y))
xy.sort()
mn=10**12;mx=0
for i in xrange(n):
    x,y=xy[i]
    mn=min(mn,x)
    mx=max(mx,y)
cntmx=0;cntmn=0
for i in xrange(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 xrange(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)
    exit()
else:
    rmn=10**12;rmx=0;bmn=10**12;bmx=0
    for i in xrange(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 xrange(n):
    x,y=xy[i]
    ymn[i]=min(ymn[max(0,i-1)],y)
ans2=(rmx-rmn)*(bmx-bmn)
for i in xrange(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)