Problem:


Score : 500 points

Problem Statement

There are N points on the 2D plane, i-th of which is located on (x_i, y_i).
There can be multiple points that share the same coordinate.
What is the maximum possible Manhattan distance between two distinct points?

Here, the Manhattan distance between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq x_i,y_i \leq 10^9

All values in input are integers.

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 answer.

Sample Input 1

3
1 1
2 4
3 2

Sample Output 1

4

The Manhattan distance between the first point and the second point is |1-2|+|1-4|=4, which is maximum possible.

Sample Input 2

2
1 1
1 1

Sample Output 2

0



Sample input:
3
1 1
2 4
3 2


Sample output:
4

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
xy = [LI() for _ in range(n)]
lst = [[x+y, x-y] for x, y in xy]
lst.sort(reverse=True)
ans = lst[0][0] - lst[-1][0]
lst.sort(key=itemgetter(1), reverse=True)
ans = max(ans, abs(lst[0][1] - lst[-1][1]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ma = 2*(10**9)+1
Ma = 0
mb = 10**9
Mb = 2-10**9
for i in range(N):
  a,b = map(int,input().split())
  tempa = a+b
  ma = min(ma,tempa)
  Ma = max(Ma,tempa)
  tempb = b-a
  mb = min(mb,tempb)
  Mb = max(Mb,tempb)
print(max(Ma-ma,Mb-mb))

Submission status: Accepted

Solution code:
n = int(input())

a = []; b = []

for i in range(n):
    x, y = map(int, input().split())

    a.append(x + y)
    b.append(x - y)

sm = a[0]; lr = a[0]; ans = float('-inf')

for i in range(1, n):
    ans = max(ans, lr - a[i])
    ans = max(ans, a[i] - sm)
    
    lr = max(lr, a[i])
    sm = min(sm, a[i])
sm = b[0]; lr = b[0]
for i in range(1, n):
    ans = max(ans, lr - b[i])
    ans = max(ans, b[i] - sm)
    
    lr = max(lr, b[i])
    sm = min(sm, b[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = []
M = []
A = []

def dist(p1, p2):
  return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

for i in range(N):
  x, y = map(int, input().split())
  P.append(x+y)
  M.append(x-y)
  A.append((x, y))

ans1 = dist(A[P.index(max(P))], A[P.index(min(P))])
ans2 = dist(A[M.index(max(M))], A[M.index(min(M))])

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
n = int(input())

x = []
y = []
rdown = []
ldown = []
for i in range(n):
    i1, i2 = map(int, input().split())
    x.append(i1)
    y.append(i2)
    rdown.append(i1+i2)
    ldown.append(i1-i2)

ans1 = max(ldown)-min(ldown)
ans2 = max(rdown)-min(rdown)

ans = max(ans1,ans2)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = map(int,input().split())

MAX = float('-inf')
MIN = float('inf')

for i in range(N):
    MAX = max(MAX, X[i] - Y[i])
    MIN = min(MIN, X[i] - Y[i])

ans = MAX - MIN

MAX = float('-inf')
MIN = float('inf')

for i in range(N):
    MAX = max(MAX, X[i] + Y[i])
    MIN = min(MIN, X[i] + Y[i])

ans = max(ans, MAX - MIN)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
r=[]
for _ in range(n):
    a,b=map(int,input().split())
    r.append([a+b,a-b])
r=list(zip(*r))
print(max(max(r[0])-min(r[0]),max(r[1])-min(r[1])))

Submission status: Accepted

Solution code:
n = int(input())
xy=[list(map(int,input().split())) for i in range(n)]

d1 = []
d2 = []
for x,y in xy:
    d1.append(x-y)
    d2.append(x+y)

ans1=max(d1)-min(d1)
ans2=max(d2)-min(d2)

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
x,y=[0]*N,[0]*N
for i in range(N):
    a,b=map(int,input().split())
    x[i],y[i]=a+b,a-b
x.sort()
y.sort()
print(max(max(x)-min(x),max(y)-min(y)))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7


def run():
    N = int(sysread())
    lis1 = []
    lis2 = []
    lis3 = []
    lis4 = []
    for i in range(N):
        x, y = map(int, sysread().split())
        lis1.append((x+y, x, y))
        lis2.append((x-y, x, y))
        lis3.append((-x+y, x, y))
        lis4.append((-x-y, x, y))
    lis1.sort()
    lis2.sort()
    lis3.sort()
    lis4.sort()
    ans = 0
    # pattern1
    val1, x1, y1 = lis1[-1]
    val2, x2, y2 = lis1[0]
    if x1 >= x2 and y1 >= y2:
        ans = max(val1-val2, ans)
    # pattern 2
    val1, x1, y1 = lis2[-1]
    val2, x2, y2 = lis2[0]
    if x1 >= x2 and y1 <= y2:
        ans = max(val1 - val2, ans)
    # pattern3
    val1, x1, y1 = lis3[-1]
    val2, x2, y2 = lis3[0]
    if x1 <= x2 and y1 >= y2:
        ans = max(val1 - val2, ans)
    # patten 4
    val1, x1, y1 = lis1[-1]
    val2, x2, y2 = lis1[0]
    if x1 <= x2 and y1 <= y2:
        ans = max(val1 - val2, ans)
    print(ans)
if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:

def solve():
    N = int(input())
    xy_l = [None] * N
    invxy_l = [None] * N
    for _ in range(N):
        _x, _y = map(int, input().split())
        xy_l[_] = _x + _y - 2
        invxy_l[_] = _y - 1 - (_x - 1)

    ans_a = max(xy_l) - min(xy_l)
    ans_b = max(invxy_l) - min(invxy_l)

    if ans_a > ans_b:
        print(ans_a)
    else:
        print(ans_b)


solve()

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = []
for i in range(N):
    x, y = map(int, input().split())
    a.append(x+y)
    b.append(x-y)
    
print(max(max(a)-min(a),max(b)-min(b)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import numpy as np

n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]

xy = [i+j for i, j in x_y]

ans1 = max(xy)-min(xy)


xy_rev = [i-j for i, j in x_y]
min_index = np.argmin(xy_rev)
max_index = np.argmax(xy_rev)

x1, y1 = x_y[max_index]
x2, y2 = x_y[min_index]

ans2 = abs(x2-x1)+abs(y2-y1)

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
INF=10**10
n=int(input())
f=lambda:map(int,input().split())
s_min=t_min=INF
s_max=t_max=-INF
for _ in range(n):
  x,y=f()
  s_min=min(s_min,x+y)
  s_max=max(s_max,x+y)
  t_min=min(t_min,x-y)
  t_max=max(t_max,x-y)
print(max(s_max-s_min,t_max-t_min))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    pos = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    m, M = float("inf"), 0
    for x, y in pos:
        dist = x+y
        if m > dist:
            m = dist
        if M < dist:
            M = dist
    if ans < M-m:
        ans = M-m
    m, M = float("inf"), 0
    for x, y in pos:
        dist = (10**9 - x)+y
        if m > dist:
            m = dist
        if M < dist:
            M = dist
    if ans < M-m:
        ans = M-m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = [10**10]*4
for _ in range(N):
  x,y = [int(i) for i in input().split()]
  L[0] = min(L[0],x+y)
  L[1] = min(L[1],x-y+10**9)
  L[2] = min(L[2],-x+y+10**9)
  L[3] = min(L[3],-x-y+2*(10**9))
print(max(2*(10**9)-L[0]-L[3],2*(10**9)-L[1]-L[2]))

Submission status: Accepted

Solution code:
N = int(input())
xy = set(tuple(map(int, input().split())) for _ in range(N))

if len(xy) == 1:
    print(0)
else:
    plus = [x+y for x, y in xy]
    diff_plus = max(plus) - min(plus)

    minus = [x-y for x, y in xy]
    diff_minus = max(minus) - min(minus)

    print(max(diff_minus, diff_plus))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    d1 = {}
    d2 = {}

    for i in range(n):
        x, y = map(int, input().split())
        if x+y not in d1:
            d1[x+y] = 1
        if x-y not in d2:
            d2[x-y] = 1
    d1key = d1.keys()
    d1key = sorted(d1key)
    d2key = d2.keys()
    d2key = sorted(d2key)
    print(max(abs(d1key[0]-d1key[-1]), abs(d2key[0]-d2key[-1])))
resolve()

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    x = []
    y = []
    for _ in range(N):
        a, b = map(int, input().split())
        x.append(a)
        y.append(b)

    ans = 0
    for mv in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
        min_v = mv[0] * x[0] + mv[1] * y[0]
        for i in range(N):
            v = mv[0] * x[i] + mv[1] * y[i]
            ans = max(ans, v - min_v)
            min_v = min(min_v, v)
            # print(ans)
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())

l = 10**10

lu = l
ru = l
ld = 0
rd = 0

for _ in range(N):
    x, y = map(int, input().split())
    lu = min(x+y, lu)
    ru = min(y-x, ru)
    ld = max(y-x, ld)
    rd = max(x+y, rd)

#print(lu, ru, ld, rd)
print(max(rd-lu, ld-ru))

Submission status: Accepted

Solution code:
N = int(input())

ans = 0
x, y = map(int, input().split())
Max_A = x+y
Min_A = x+y
Max_B = -x+y
Min_B = -x+y

for i in range(1,N):
  x, y = map(int, input().split())
  C = x + y
  D = -x + y
  temp = max( abs(Max_A-C), abs(Min_A-C), abs(Max_B-D), abs(Min_B-D) )
  ans = max(ans, temp)
  #print(C, D, ans)
  Max_A = max(Max_A, C)
  Max_B = max(Max_B, D)
  Min_A = min(Min_A, C)
  Min_B = min(Min_B, D)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
wa = [0]*n
sa = [0]*n
for i in range(n):
    x,y = map(int,input().split())
    wa[i] = x+y
    sa[i] = x-y
wanosa = max(wa) - min(wa)
sanosa = max(sa) - min(sa)
ans = max(wanosa,sanosa)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
za = []
for _ in range(N):
    x, y = map(int,input().split())
    za.append((x + y, y - x))
X = max(za, key = lambda x:x[0])[0] - min(za, key = lambda x:x[0])[0]
Y = max(za, key = lambda x:x[1])[1] - min(za, key = lambda x:x[1])[1]
print(max(X, Y))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    XY=LLIN(N)

    X=[]
    Y=[]
    for x,y in XY:
        X.append(x-y)
        Y.append(x+y)
    
    X.sort()
    Y.sort()

    ans = max(X[-1]-X[0], Y[-1]-Y[0])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*N
Y = [0]*N
for TN in range(0,N):
    A,B = (int(T) for T in input().split())
    X[TN] = A-B
    Y[TN] = A+B
print(max(max(X)-min(X),max(Y)-min(Y)))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for _ in range(n):
  x,y=map(int,input().split())
  a+=[x-y]
  b+=[x+y]
a.sort()
b.sort()
print(max(a[-1]-a[0],b[-1]-b[0]))

Submission status: Accepted

Solution code:
n=int(input())
ad=[0]*n
su=[0]*n
for i in range(n):
  x,y=map(int,input().split())
  ad[i]=x+y
  su[i]=x-y
ad.sort()
su.sort()
print(max(ad[-1]-ad[0],su[-1]-su[0]))

Submission status: Accepted

Solution code:
n = int(input())
xyl = [tuple(map(int, input().split())) for _ in range(n)]

xyp = []
xym = []

for x,y in xyl:
    xyp.append(x+y)
    xym.append(x-y)

# xyp.sort()
# xym.sort()

ans1 = max(xym)-min(xym)
# print(ans1)
ans2 = max(xyp)-min(xyp)
ans = max(ans1,ans2)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

P=[list(map(int,input().split())) for _ in range(N)]

L1=[]
L2=[]
L3=[]
L4=[]
for x,y in P:
    L1.append(x+y)
    L2.append(-x+y)
    L3.append(x-y)
    L4.append(-x-y)

L1=sorted(L1)
L2=sorted(L2)
L3=sorted(L3)
L4=sorted(L4)

ans=max(L1[-1]-L1[0],L2[-1]-L2[0],L3[-1]-L3[0],L4[-1]-L4[0])
print(ans)

Submission status: Accepted

Solution code:
n=input()
x=[]
y=[]
for _ in range(n):
    x1,y1=[int(i) for i in raw_input().split()]
    x.append(x1);y.append(y1)
res=0
for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
        smallest = p * x[0] + q * y[0]
        for i in range(n):
                cur = p * x[i] + q * y[i]
                res = max(res, cur - smallest)
                smallest = min(smallest, cur)
print res

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()

memo1 = []
memo2 = []
for x, y in xy:
  memo1.append(x+y)
  memo2.append(x-y)

min1 = 10 ** 10
min2 = 10 ** 10

ans = 0

for i in range(n):
  ans = max(ans, memo1[i]-min1)
  ans = max(ans, memo2[i]-min2)
  min1 = min(min1, memo1[i])
  min2 = min(min2, memo2[i])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x * 2, y * 2))
X = sorted(X, key = lambda x: -x[1])
x0, y0 = X[0]
ans = 0
for x, y in X[1:]:
    ans = max(ans, y0 - y + abs(x - x0))
    a = (abs(x - x0) - (y0 - y)) // 2
    if a < 0: continue
    x0 += a if x0 < x else -a
    y0 += a
print(ans // 2)

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
def f(x):
    return x[0]-x[1]
def g(x):
    return x[0]+x[1]
ans = max(f(max(xy, key=f))-f(min(xy, key=f)),
          g(max(xy, key=g))-g(min(xy, key=g)),)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid):  # fix inputs here
    console("----- solving ------")

    # return a string (i.e. not a list or matrix)
    return max(max([(x+y) for x,y in grid]) - min([(x+y) for x,y in grid]), 
               max([(x-y) for x,y in grid]) - min([(x-y) for x,y in grid]))


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    nrows = int(inp[0])
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for row in range(1,nrows+1):
        grid.append(list(map(int,inp[row].split())))

    res = solve(grid)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

Solution code:
n=int(input())
INF=float('inf')

cmin0,cmax0=INF,-INF
cmin1,cmax1=INF,-INF
for _ in range(n):
  x,y=map(int,input().split())
  cx,cy=x-y,x+y
  cmin0=min(cmin0,cx)
  cmax0=max(cmax0,cx)
  cmin1=min(cmin1,cy)
  cmax1=max(cmax1,cy)
  
ans=max(cmax0-cmin0,cmax1-cmin1)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ls = [list(map(int, input().split())) for _ in range(N)]
ls_sum = [ls[i][0] + ls[i][1] for i in range(N)]
ls_dif = [ls[i][0] - ls[i][1] for i in range(N)]
ls_sum.sort()
ls_dif.sort()

print(max([ls_sum[N-1] - ls_sum[0], ls_dif[N-1] - ls_dif[0]]))

Submission status: Accepted

Solution code:
N=int(input())
L1=[]
L2=[]
L3=[]
for i in range(N):
    x,y=map(int,input().split())
    L1.append(x+y)
    L2.append(x-y)
    L3.append(y-x)
L1.sort()
L2.sort()
L3.sort()

M1=L1[-1]-L1[0]
M2=L2[-1]-L2[0]
M3=L3[-1]-L3[0]
print(max(M1,M2,M3))

Submission status: Accepted

Solution code:
n = int(input())
disadd = []
disminus = []
for i in range(n):
    x, y = map(int, input().split())
    disadd.append(x+y)
    disminus.append(x-y)

print(max(max(disadd)-min(disadd), max(disminus) - min(disminus)))

Submission status: Accepted

Solution code:
x=[];y=[]
for _ in range(int(input())):
  a,b=map(int,input().split())
  x.append(a-b);y.append(a+b)
print(max(max(x)-min(x),max(y)-min(y)))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    newx=[0 for i in range(n)]
    newy=[0 for i in range(n)]
    for i in range(n):
        x,y=MI()
        newx[i]=x-y
        newy[i]=x+y
    print(max(max(newx)-min(newx),max(newy)-min(newy)))

        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
add = []
diff = []
for _ in range(N):
    x, y = list(map(int, input().split()))
    add.append(x+y)
    diff.append(x-y)
add.sort()
diff.sort()
print(max(add[-1]-add[0], diff[-1]-diff[0]))

Submission status: Accepted

Solution code:
n = int(input())
xpy_max = -1001001001
xpy_min =  1001001001
xmy_max = -1001001001
xmy_min =  1001001001

for i in range(n):
    x, y = map(int, input().split())
    xpy_max = max(xpy_max, x+y)
    xpy_min = min(xpy_min, x+y)
    xmy_max = max(xmy_max, x-y)
    xmy_min = min(xmy_min, x-y)
ans = max(xpy_max - xpy_min, xmy_max - xmy_min)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = list(map(int, input().split()))
    X.append(x)
    Y.append(y)
    
points = []
for i, (x, y) in enumerate(zip(X, Y)):
    points.append((
        x + y,
        x + y,
        x - y,
        x - y
    ))
print(max(max(dim) - min(dim) for dim in zip(*points)))

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
a_max = -float("inf")
a_min = float("inf")
b_max = -float("inf")
b_min = float("inf")
for _ in range(N):
    x, y = map(int, input().split())
    a_max = max(a_max, x-y)
    a_min = min(a_min, x-y)
    b_max = max(b_max, x+y)
    b_min = min(b_min, x+y)
print(max(a_max-a_min, b_max-b_min))

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n = int(input())
    #n, k = map(int, input().split())
    #c, d = map(int, input().split())
    #a = list(map(int, input().split()))
    #b = list(map(int, input().split()))
    #s = input()
    a=[]
    b=[]
    for i in range(n):
        x, y = map(int, input().split())
        a+=[x+y]
        b+=[x-y]
    a=sorted(a)
    b=sorted(b)
    print(max(a[-1]-a[0], b[-1]-b[0]))

Submission status: Accepted

Solution code:
n = int(input())

max_diff = -float('inf')
min_diff = float('inf')
max_sum  = -float('inf')
min_sum  = float('inf')
for _ in range(n):
    x, y =map(int, input().split())
    max_diff = max(max_diff, x-y)
    min_diff = min(min_diff, x-y)
    max_sum = max(max_sum, x+y)
    min_sum  = min(min_sum, x+y)
print(max(max_diff - min_diff, max_sum - min_sum))

Submission status: Accepted

Solution code:
N=int(input())
x=[list(map(int,input().split())) for _ in range(N)]

A=[]
B=[]
C=[]
D=[]
for i in range(N):
    A.append(x[i][0]+x[i][1])
    B.append(-x[i][0]-x[i][1])
    C.append(x[i][0]-x[i][1])
    D.append(-x[i][0]-x[i][1])

print(max(max(A)-min(A),max(B)-min(B),max(C)-min(C),max(D)-min(D)))

Submission status: Accepted

Solution code:
N = int(input())
plus_max = -10**10
plus_min = 10**10
minus_max = -10**10
minus_min = 10**10
for i in range(N):
    x,y = map(int,input().split())
    plus_max = max(plus_max,x+y)
    plus_min = min(plus_min,x+y)
    minus_max = max(minus_max,x-y)
    minus_min = min(minus_min,x-y)
print(max(plus_max-plus_min,minus_max-minus_min))

Submission status: Accepted

Solution code:
N = int(input())

M0, m0 = -float('inf'), float('inf')
M1, m1 = -float('inf'), float('inf')
for i in range(N):
    x, y = map(int, input().split())
    M0 = max(M0, x + y)
    m0 = min(m0, x + y)
    M1 = max(M1, x - y)
    m1 = min(m1, x - y)

print(max(M0 - m0, M1 - m1))

Submission status: Accepted

Solution code:
N=int(input())
point=list()
for i in range(N):
    point.append([int(i) for i in input().split()])
#print(point)

list_a=sorted(point,key=lambda x:x[0]+x[1])
list_b=sorted(point,key=lambda x:x[1]-x[0])

ps=[list_a[0],list_a[N-1],list_b[0],list_b[N-1]]
#print(ps)
ans=0

for p1 in ps:
    for p2 in ps:
        ans=max(ans,abs(p1[0]-p2[0])+abs(p1[1]-p2[1]))

print (ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    p = []
    q = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append(x + y)
        q.append(x - y)
    ans = 0
    p_min = min(p)
    q_min = min(q)
    for i in range(N):
        ans = max(abs(p[i] - p_min), abs(q[i] - q_min), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

x = []
y = []

for i in range(n):
    a, b = [int(i) for i in input().split()]
    x.append(a+b)
    y.append(a-b)

x.sort()
y.sort()

print(max(abs(x[0]-x[n-1]),abs(y[0]-y[n-1])))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from random import randint
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def solve(N, X, Y):
    # xi + yiのmax, minとxi - yiのmax, minを使う
    xyp = [X[i] + Y[i] for i in range(N)]
    xym = [X[i] - Y[i] for i in range(N)]
    ans1 = max(xyp) - min(xyp)
    ans2 = max(xym) - min(xym)
    ans = max(ans1, ans2)
    return ans

def main():
    from builtins import int, map
    N = int(input())
    X, Y = [], []
    for _ in range(N):
        xi, yi = map(int, input().split())
        X.append(xi)
        Y.append(yi)
    print(solve(N, X, Y))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

ma = -float("inf")
mi = float("inf")
ma2 = -float("inf")
mi2 = float("inf")
for i in range(N):
    x,y = list(map(int,input().split()))
    ma = max(ma,x+y)
    mi = min(mi,x+y)
    ma2 = max(ma2,10**9-x+y)
    mi2 = min(mi2,10**9-x+y)
print(max(ma-mi,ma2-mi2))

Submission status: Accepted

Solution code:
N=int(input())
A=list()
B=list()
for i in range(N):
  x,y=map(int,input().split())
  A.append(x+y)
  B.append(x-y)
s=max(A)-min(A)
t=max(B)-min(B)
print(max(s,t))

Submission status: Accepted

Solution code:
def main(): 
    n = int(input())
    d1 = []
    d2 = []
    for _ in range(n):
        x,y = map(int,input().split())
        d1.append(x+y)
        d2.append(x-y)
    
    print(max(max(d1)-min(d1),max(d2)-min(d2)))
main()

Submission status: Accepted

Solution code:
N = int(input())
x,y = map(int,input().split(" "))
papb = [x,y]
pamb = [x,y]
mapb = [x,y]
mamb = [x,y]
for i in range(N - 1):
    x,y = map(int,input().split(" "))
    if x + y > papb[0] + papb[1]:papb = [x,y]
    if x - y > pamb[0] - pamb[1]:pamb = [x,y]
    if 0 - x + y > 0 - mapb[0] + mapb[1]:mapb = [x,y]
    if 0 - x - y > 0 - mamb[0] - mamb[1]:mamb = [x,y]
print(max(abs(papb[0] - mamb[0]) + abs(papb[1] - mamb[1]),abs(pamb[0] - mapb[0]) + abs(pamb[1] - mapb[1])))

Submission status: Accepted

Solution code:
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
p = [x + y for x, y in xy]
a1 = max(p) - min(p)
q = [x - y for x, y in xy]
a2 = max(q) - min(q)
print(max(a1, a2))

Submission status: Accepted

Solution code:
N=int(input())
answer=0

xylist=[]
for _ in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))

ppxylist=[]
for i in range(N):
  x,y=xylist[i]
  ppxylist.append((x+y,x,y))
ppxylist.sort()
#print(ppxylist)
answer=max(answer,ppxylist[-1][0]-ppxylist[0][0])

pmxylist=[]
for i in range(N):
  x,y=xylist[i]
  pmxylist.append((x-y,x,y))
pmxylist.sort()
#print(ppxylist)
answer=max(answer,pmxylist[-1][0]-pmxylist[0][0])

mpxylist=[]
for i in range(N):
  x,y=xylist[i]
  mpxylist.append((-x+y,x,y))
mpxylist.sort()
#print(ppxylist)
answer=max(answer,mpxylist[-1][0]-mpxylist[0][0])

mmxylist=[]
for i in range(N):
  x,y=xylist[i]
  mmxylist.append((-x-y,x,y))
mmxylist.sort()
#print(ppxylist)
answer=max(answer,mmxylist[-1][0]-mmxylist[0][0])
  
print(answer)

Submission status: Accepted

Solution code:
from operator import itemgetter

def main():
    N = int(input())
    point = set()
    for _ in range(N):
        x, y = map(int, input().split())
        point.add((x,y))
    #point = np.array(point)
    #oint = np.unique(point)
    if len(point) == 1:
        print(0)
        exit()
    
    t = []
    for x, y in point:
        l_00 = x + y
        l_0m = x + 10**9-y
        l_m0 = 10**9-x + y
        l_mm = 10**9-x + 10**9-y
        t.append(((x,y), l_00, l_0m, l_m0, l_mm))
    ans = 0
    for pos in range(1,5):
        t.sort(key=itemgetter(pos))
        l, r = t[0][0], t[-1][0]
        ans = max(ans,
            abs(l[0]-r[0])+abs(l[1]-r[1]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
tens=[]
for i in range(n):
    x,y=map(int,input().split())
    tens.append([x,y])

tasu=[]
hiku=[]

for i in range(n):
    tasu.append(tens[i][0]+tens[i][1])
    hiku.append(tens[i][0]-tens[i][1])

#print(tasu,hiku)

a=max(tasu)-min(tasu)
b=max(hiku)-min(hiku)

print(max(a,b))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n=int(input())

pointx=[]
pointy=[]
for i in range(n):
    x,y=map(int,input().split())
    pointx.append(x-y)
    pointy.append(x+y)

ans=0
pointx.sort()
pointy.sort()
ans=pointx[-1]-pointx[0]
ans=max(ans,pointy[-1]-pointy[0])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = []
for i in range(N):
    x,y = map(int,input().split())
    P.append([x,y])
L,R = [],[]
F = 10**9
for a,b in P:
    L.append(a+b)
    R.append(F-b+a)
print(max(max(L)-min(L),max(R)-min(R)))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
gcd = math.gcd

n = ni()
xpy = []
xmy = []
for i in range(n):
    x,y = ma()
    xpy.append(x+y)
    xmy.append(x-y)
xpy.sort()
xmy.sort()
a1=abs(xpy[0]-xpy[-1])
a2 = abs(xmy[0]-xmy[-1])
print(max(a1,a2))

Submission status: Accepted

Solution code:
N = int(input())

X = []
Y = []

P = []
Q = []

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(x + y)
    Q.append(x - y)

print(max(max(P) - min(P), max(Q) - min(Q)))