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



Sample input:
3
1 2
3 4
5 6


Sample output:
15

Submission status: Accepted

Solution code:
N = int(input())
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
    x,y = 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][0]
tymin = float('inf')
tymax = 0
for i in range(N-1):
    # print(i, dx, (xmax, xmin), end=' ==> ')
    tymin = min(tymin, p[i][1])
    xmax = max(xmax, p[i][1])
    xmin = min(tymin, p[i+1][0])
    dx = min(dx, xmax - xmin)
    # print(i, dx, (xmax, xmin))

# print(ret, (ymax-ymin) * (xmax-xmin) ,(ymax,ymin), (xmax,xmin), dx)
print(min(ret, (ymax-ymin) * dx))

Submission status: Accepted

Solution code:
N = int(input())
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
    x,y = 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):
    # print(i, dx, (xmax, xmin), end=' ==> ')
    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(i, dx, (xmax, xmin))

# print(ret, (ymax-ymin) * (xmax-xmin) ,(ymax,ymin), (xmax,xmin), dx)
print(min(ret, (ymax-ymin) * dx))

Submission status: Accepted

Solution code:
# E
import numpy as np

N = int(input())

X = [0]*N
Y = [0]*N

for i in range(N):
    x, y = map(int, input().split())
    X[i] = min(x, y)
    Y[i] = max(x, y)


# CASE1
res1 = (max(Y) - min(Y)) * (max(X) - min(X))

# CASE2
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))))

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc073/tasks/arc073_c

全体の最大値と、最小値は必ず4つ中に含まれる
最大を必ず赤に割り振るとする

(1)最小が最大とペアでないとき、→自由な方における
(2)ペアの時、→青にしか置けない

ありうる分け方は2つ
(A)最小を赤にすると決めた時
    青の最大値を最小化して、最小値を最大化するのがよさそう？

(B)最小を青にするとき
    →赤の最小値を最大化、青の最大値を最小化するのが良い
    →貪欲に大きい方を赤&小さい方を青に選んでいけばよい

問題は(A)の時か…

青には、最小と最大の余り物は必ず含まれる。
また、残りのペアの内、最小値の最大 <= 青最大 　最大値の最小>=青最小
は必ず満たされる。


尺取り法！！
で、Nこのペアから1つづつ取るときの最大と最小の差の最小値を求められる

x>yにしておこう
"""
from collections import deque
N = int(input())

xy = []
maxind = 0
minind = 0

for i in range(N):

    x,y = map(int,input().split())
    if x < y:
        t = x
        x = y
        y = t

    xy.append([x,y])
        
    if x > xy[maxind][0]:
        maxind = i
    if y < xy[minind][1]:
        minind = i

rmin = float("inf")
bmax = float("-inf")

for i in range(N): #最大と最小が別サイドの場合(貪欲)

    x,y = xy[i]

    if i == maxind and i == minind:
        continue
    elif i == maxind:
        bmax = max(bmax,y)
        continue
    elif i == minind:
        rmin = min(rmin,x)
        continue
    
    rmin = min(rmin,max(x,y))
    bmax = max(bmax,min(x,y))


ans = (xy[maxind][0] - rmin) * (bmax - xy[minind][1])
#print (ans)


if maxind != minind: #最大と最小を同じサイドに置く場合(尺取り法)
    
    side_R = xy[maxind][0] - xy[minind][1]

    apnum = 0
    aplis = [0] * N

    wait = []

    for i in range(N):

        if i == maxind:
            wait.append([xy[i][1],i])
        elif i == minind:
            wait.append([xy[i][0],i])
        else:
            wait.append([xy[i][0],i])
            wait.append([xy[i][1],i])

    q = deque([])
    wait.sort()

    print (cejcoiececji)

    for num,ind in wait:

        if aplis[ind] == 0:
            apnum += 1
        aplis[ind] += 1
        q.append([num,ind])

        if apnum == N:

            while len(q) > 0 and aplis[q[0][1]] > 1:
                pn,pi = q.popleft()
                aplis[pi] -= 1

            ans = min(ans, side_R * (q[-1][0] - q[0][0]))

print (ans)

Submission status: Runtime Error

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc073/tasks/arc073_c

全体の最大値と、最小値は必ず4つ中に含まれる
最大を必ず赤に割り振るとする

(1)最小が最大とペアでないとき、→自由な方における
(2)ペアの時、→青にしか置けない

ありうる分け方は2つ
(A)最小を赤にすると決めた時
    青の最大値を最小化して、最小値を最大化するのがよさそう？

(B)最小を青にするとき
    →赤の最小値を最大化、青の最大値を最小化するのが良い
    →貪欲に大きい方を赤&小さい方を青に選んでいけばよい

問題は(A)の時か…

青には、最小と最大の余り物は必ず含まれる。
また、残りのペアの内、最小値の最大 <= 青最大 　最大値の最小>=青最小
は必ず満たされる。


尺取り法！！
で、Nこのペアから1つづつ取るときの最大と最小の差の最小値を求められる

x>yにしておこう
"""
from collections import deque
N = int(input())

xy = []
maxind = 0
minind = 0

for i in range(N):

    x,y = map(int,input().split())
    if x < y:
        t = x
        x = y
        y = t

    xy.append([x,y])
        
    if x > xy[maxind][0]:
        maxind = i
    if y < xy[minind][1]:
        minind = i

rmin = float("inf")
bmax = float("-inf")

for i in range(N): #最大と最小が別サイドの場合(貪欲)

    x,y = xy[i]

    if i == maxind and i == minind:
        continue
    elif i == maxind:
        bmax = max(bmax,y)
        continue
    elif i == minind:
        rmin = min(rmin,x)
        continue
    
    rmin = min(rmin,max(x,y))
    bmax = max(bmax,min(x,y))


ans = (xy[maxind][0] - rmin) * (bmax - xy[minind][1])
#print (ans)

print (sakopwdwicjwoi)

if maxind != minind: #最大と最小を同じサイドに置く場合(尺取り法)
    
    side_R = xy[maxind][0] - xy[minind][1]

    apnum = 0
    aplis = [0] * N

    wait = []

    for i in range(N):

        if i == maxind:
            wait.append([xy[i][1],i])
        elif i == minind:
            wait.append([xy[i][0],i])
        else:
            wait.append([xy[i][0],i])
            wait.append([xy[i][1],i])

    q = deque([])
    wait.sort()

    for num,ind in wait:

        if aplis[ind] == 0:
            apnum += 1
        aplis[ind] += 1
        q.append([num,ind])

        if apnum == N:

            while len(q) > 0 and aplis[q[0][1]] > 1:
                pn,pi = q.popleft()
                aplis[pi] -= 1

            ans = min(ans, side_R * (q[-1][0] - q[0][0]))

print (ans)

Submission status: Runtime Error

Solution code:
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)
#print(A,C,D,si,ti)
if N==1:
    print(0)
    sys.exit()
ans=(max(C)-min(C))*(max(D)-min(D))
cur=min(D)
ma=min(D)
T=10**19
for a,b in A:
    if a>ma:
        T=min(best,cur-ma)
        break
    T=min(T,cur-a)
    cur=max(cur,b)

print(min(ans,(max(D)-min(C))*T))

Submission status: Runtime Error

Solution code:
from bisect import insort

n=int(input())
x,y,p=[],[],[]
for i in range(n):
    a,b=map(int,input().split())
    if a > b: a,b=b,a
    x.append(a)
    y.append(b)
    p.append((a,i,True))
    p.append((b,i,False))
p.sort()
ans=(max(x)-min(x))*(max(y)-min(y))
if p[0][1] != p[-1][1]:
    raise ValueError
print(ans)

Submission status: Runtime Error

Solution code:
n = input()
P = []
mx = {}
my = {}
for i in xrange(n):
    x, y = map(int, raw_input().split())
    if x > y: x, y = y, x
    mx[x] = i
    my[y] = i
    P.append((x, y))

kx = sorted(mx)
mi_x = min(mx); ma_x = max(mx)
ky = sorted(my)
mi_y = min(my); ma_y = max(my)

if ma_x < mi_y or ma_y < mi_x:
    print (ma_x - mi_x) * (ma_y - mi_y)
    exit(0)

ans = (ma_x - mi_x) * (ma_y - mi_y)
xm = ()
for i in xrange(n):
    i = mx[kx[i]]
    if xm <= kx[i]:
        break
    y = P[i][1]
    if y <= min(ma_x, ma_y):
        xm = min(xm, y)
    else:
        break
ans = min((ma_x - xm) * (ma_y - kx[0]), ans)

ym = 0
for i in xrange(n-1, -1, -1):
    i = my[ky[i]]
    if ky[i] <= ym:
        break
    x = P[i][0]
    if max(mi_x, mi_y) <= x:
        ym = max(ym, x)
    else:
        break
ans = min((ky[-1] - mi_x) * (ym - mi_y), ans)
print ans

Submission status: Runtime Error

Solution code:
n = input()
P = []
mx = {}
my = {}
for i in xrange(n):
    x, y = map(int, raw_input().split())
    if x > y: x, y = y, x
    mx[x] = i
    my[y] = i
    P.append((x, y))

kx = sorted(mx)
mi_x = min(mx); ma_x = max(mx)
ky = sorted(my)
mi_y = min(my); ma_y = max(my)

if ma_x < mi_y or ma_y < mi_x:
    print (ma_x - mi_x) * (ma_y - mi_y)
    exit(0)

ans = (ma_x - mi_x) * (ma_y - mi_y)
xm = ()
for i in xrange(n):
    i = mx[kx[i]]
    if xm <= kx[i]:
        break
    y = P[i][1]
    if y <= min(ma_x, ma_y):
        xm = min(xm, y)
    else:
        break
ans = min((ma_x - xm) * (ma_y - kx[0]), ans)

ym = 0
for i in xrange(n-1, -1, -1):
    i = my[ky[i]]
    if ky[i] <= ym:
        break
    x = P[i][0]
    if max(mi_x, mi_y) <= x:
        ym = max(ym, x)
    else:
        break
ans = min((ky[-1] - mi_x) * (ym - mi_y), ans)

Submission status: Runtime Error

Solution code:
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()
    if n == 1:
        return 0
    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]
            tr = am * (max(km,bm)-min(ki,bt))
            if r > tr:
                r = tr
            if km >= bm:
                break

    return r


print(main())