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:
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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(ans1, ans2)
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
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
# X \leq Y に変換
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)

Submission status: Accepted

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)
A.sort()
#print(A,C,D,si,ti)
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

  # print(MAX,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))]

  # print(MAX,MIN)

  # print("lis li",lis,li,MAX,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

  # print(lis,li)
ans.append((max(lis)-min(lis)) * (max(li)-min(li)))

print(min(ans))

Submission status: Accepted

Solution code:
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, MAX
MIN = X[0]
MAX = max(Y)

# 確定2玉を別グループに
ans = (max(X) - MIN) * (MAX - min(Y))

# 確定2玉を同じグループに

# 全体のMAX・MINが確定している場所は、もう片方を使うしかない
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)

Submission status: Accepted

Solution code:
# seishin.py
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)

# R_min = MIN, B_max = MAX
res = (max(X) - MIN) * (MAX - min(Y))

# R_min = MIN, R_max = MAX
base = MAX - MIN
heapify(P)

# 出来る限りスライドさせながら(B_max - B_min)を最小化
r = max(X)
while P:
    x, y = heappop(P)
    res = min(res, base * (r - x))
    if y != -1:
        # Bに入ってたxをRに入れて代わりにyをBに入れる
        heappush(P, (y, -1))
        r = max(r, y)
    else:
        # (x, y) のyの方がB_minに該当
        # => これ以上B_minを落とせない
        break

print(res)

Submission status: Accepted

Solution code:
#for t in xrange(int(raw_input())):
#n,m = map(int, raw_input().split())
#n = int(raw_input())

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
balls = sorted(tuple(sorted(map(int,input().split()))) for i in range(N))

# Rmin=MIN, Bmax=MAX
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)

# Rmin=MIN, Rmax=MAX
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

N = int(raw_input())
balls = input_str(N)
balls = sorted([sorted([int(x), int(y)]) for x, y in balls], key=lambda x: x[0])
#rmin == min, bmax == max
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)
#rmin == min, rmax == max
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)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
 
inf = 1 << 30
 
def solve():
    n = int(sys.stdin.readline())
 
    # r_max = MAX, b_min = MIN にしたとき
 
    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)

    # print('r_max = MAX, b_min = MIN -> ', ans1, file=sys.stderr)
 
    # r_max = MAX, r_min = MIN にしたとき
 
    ans2 = (r_max - b_min)
 
    p.sort(key=itemgetter(0))

    # print(*p, sep='\n', file=sys.stderr)
 
    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])

        # print(b_min, b_max, b_max - b_min, file=sys.stderr)
 
        dif_b = min(dif_b, b_max - b_min)
 
        if y_min < p[i + 1][0]:
            break
 
    ans2 *= dif_b

    # print('r_max = MAX, r_min = MIN ->', ans2, file=sys.stderr)
 
    ans = min(ans1, ans2)
 
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
 
inf = 1 << 30
 
def solve():
    n = int(sys.stdin.readline())
 
    # r_max = MAX, b_min = MIN にしたとき
 
    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)
 
    # r_max = MAX, r_min = 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)

        if p[i][1] < p[i + 1][0]:
            break
 
    ans2 *= dif_b
 
    ans = min(ans1, ans2)
 
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
 
inf = 1 << 30
 
def solve():
    n = int(sys.stdin.readline())
 
    # r_max = MAX, b_min = MIN にしたとき
 
    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)
 
    # r_max = MAX, r_min = 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)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
 
inf = 1 << 30
 
def solve():
    n = int(sys.stdin.readline())
 
    # r_max = MAX, b_min = MIN にしたとき
 
    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)
 
    # r_max = MAX, r_min = 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):
        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)
 
if __name__ == '__main__':
    solve()

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')
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)
    if tymin < p[i+1][0]:
        break
    # print(i, dx, (xmax, xmin))

print(min(ret, (ymax-ymin) * dx))