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

Solution (Python):
import sys
input = sys.stdin.readline




def det(p, q):
    return p[0]*q[1] - p[1]*q[0]


def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])


def get_convex_hull(points):
    
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))
if N == 2:
    x0,y0 = p[0]
    x1,y1 = p[1]
    print(abs(x0-x1)+abs(y0-y1))
    exit()

p = get_convex_hull(p)
n = len(p)
for i in range(n):
    xi,yi = p[i]
    for j in range(i+1,n):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(tmp,ans)
print(ans)

Solution (Python):
n = int(input())
point = []
for _ in range(n):
    point.append((tuple(map(int, input().split()))))
point = list(set(point))
point = sorted(point)
if len(point) == 1: print(0)
else:  
    d1 = max([(x+y) for x,y in point])- min([(x+y) for x,y in point])
    d2 = max([(x-y) for x,y in point]) - min([(x-y) for x,y in point])
    print(max(d1,d2))

Solution (Python):
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    """
    https://www.quora.com/How-can-I-find-the-maximum-Manhattan-distance-between-2-points-from-a-given-set-of-points
    """
    N = int(input())
    x, y = map(int, input().split())
    maximalp = x + y
    minimalp = x + y
    maximaln = x - y
    minimaln = x - y
    for _ in range(N - 1):
        x, y = map(int, input().split())
        maximalp = max(maximalp, x + y)
        minimalp = min(minimalp, x + y)
        maximaln = max(maximaln, x - y)
        minimaln = min(minimaln, x - y)
    print(max(maximalp - minimalp, maximaln - minimaln))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
d0 = []
d1 = []
for i in range(n):
  xi,yi = map(int,input().split())
  d0.append(xi-yi)
  d1.append(xi+yi)
print(max(max(d0)-min(d0),max(d1)-min(d1)))

Solution (Python):
N = int(input())
x, y = map(int, input().split())
A = [x + y, x + y, y - x, y - x]
for i in range(N - 1):
  x, y = map(int, input().split())
  p = x + y
  q = y - x
  A[0] = max(A[0], p)
  A[1] = min(A[1], p)
  A[2] = max(A[2], q)
  A[3] = min(A[3], q)
print(max(A[0] - A[1], A[2] - A[3]))

Solution (Python):
INF=2**31
n=int(input())
f=lambda:map(int,input().split())
s=t=INF
S=T=-INF
for _ in range(n):
  x,y=f()
  s=min(s,x+y)
  S=max(S,x+y)
  t=min(t,x-y)
  T=max(T,x-y)
print(max(S-s,T-t))

Solution (Python):
n = int(input())
a = []
b = []
for i in range(n):
    x, y = [int(i) for i in input().split()]
    a.append(x)
    b.append(y)
ans = 0
for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
    cur_min = float('inf')
    cur_max = float('-inf')
    for i in range(n):
        tmp = s*a[i] + t*b[i]
        cur_min = min(cur_min, tmp)
        cur_max = max(cur_max, tmp)
    ans = max(ans, cur_max - cur_min)
print(ans)

Solution (Python):
N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
a,b,c,d=-10**10,10**10,-10**10,10**10
l=[0]*4
for x,y in XY:
    if x+y>a: a=x+y;l[0]=(x,y)
    if x+y<b: b=x+y;l[1]=(x,y)
    if x-y>c: c=x-y;l[2]=(x,y)
    if x-y<d: d=x-y;l[3]=(x,y)
from itertools import combinations
print(max([abs(p[0]-q[0])+abs(p[1]-q[1]) for p,q in combinations(l,2)]))

Solution (Python):
N = int(input())

def m_dis(x1, y1, x2, y2):
	return abs(x2 - x1) + abs(y2 - y1)

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

x, y = points[0]

maxvalue_p = x + y
minvalue_p = x + y
maxvalue_m = x - y
minvalue_m = x - y
maxvalue_p_p = points[0]
minvalue_p_p = points[0]
maxvalue_m_p = points[0]
minvalue_m_p = points[0]

for x, y in points:
	p = x + y
	m = x - y
	if maxvalue_p == None or maxvalue_p < p:
		maxvalue_p = p
		maxvalue_p_p = (x, y)
	if minvalue_p == None or minvalue_p > p:
		minvalue_p = p
		minvalue_p_p = (x, y)
	if maxvalue_m == None or maxvalue_m < m:
		maxvalue_m = m
		maxvalue_m_p = (x, y)
	if minvalue_m == None or minvalue_m > m:
		minvalue_m = m
		minvalue_m_p = (x, y)

topvalue = 0

for x, y in points:
	topvalue = max(topvalue, 
		m_dis(x, y, maxvalue_p_p[0], maxvalue_p_p[1]),
		m_dis(x, y, minvalue_p_p[0], minvalue_p_p[1]),
		m_dis(x, y, maxvalue_m_p[0], maxvalue_m_p[1]),
		m_dis(x, y, minvalue_m_p[0], minvalue_m_p[1]))

print(topvalue)

Solution (Python):
n=int(input(""))
lista=[]
listb=[]

for i in range(n):
    xy=input("").split(" ")
    lista+=[int(xy[0])+int(xy[1])]
    listb+=[int(xy[0])-int(xy[1])]
t=max(lista)-min(lista)
tt=max(listb)-min(listb)
print(max(t,tt))

Solution (Python):



N = int(input())


ans = 0

r = []
for k in range(N):
  r.append(tuple(map(int, input().split())))
r.sort(key = lambda x:x[0])

nowx = -1
lastx_min = r[0][0]
lastx_max = r[0][0]

miny = r[0][1]
maxy = r[0][1]
k = 0
while k < N:
  if nowx != r[k][0]:
    nowx = r[k][0]
    while r[k][0] == nowx:
      ans = max(ans, abs(miny - r[k][1]) + nowx - lastx_min, abs(maxy-r[k][1])+ nowx -lastx_max)
      if miny - (nowx - lastx_min) > r[k][1]:
        miny = r[k][1]
        lastx_min = nowx
      if maxy + (nowx - lastx_max) < r[k][1]:
        maxy = r[k][1]
        lastx_max = nowx
      k += 1
      if k == N:
        break

print(ans)

Solution (Python):

import sys
def main(N, P):
    a = [x - y for x, y in P]
    b = [x + y for x, y in P]
    c = max(max(a) - min(a), max(b) - min(b))
    print(c)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, P)

Solution (Python):
N = int(input())
dist = []
dist2 = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    dist.append(x + y)
    dist2.append(x - y)
dist.sort()
dist2.sort()
ans = dist[N - 1] - dist[0]
ans2 = dist2[N - 1] - dist2[0]
print(max(ans, ans2))

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

Solution (Python):
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
points = set()
for _ in xrange(n):
    x,y = (int(x) for x in input().split())
    points.add((x,y))

if len(points) <= 1:
    print(0)
else:
    srt1 = sorted(points, key=lambda x: x[0] + x[1])
    x1,y1 = srt1[0]
    x2,y2 = srt1[-1]
    ans1 = abs(x1+y1 - (x2+y2))
    srt2 = sorted(points, key=lambda x: x[0] - x[1])
    x1,y1 = srt2[0]
    x2,y2 = srt2[-1]
    ans2 = abs((x1-y1) - (x2-y2))
    print(max(ans1, ans2))

Solution (Python):
N = int(input())
xs = []
ys = []
for _ in range(N):
    x,y = map(int,input().split())
    xs.append(x)
    ys.append(y)
fxys = [[], []]
for i in range(N):
    x = xs[i]
    y = ys[i]
    fxys[0].append(x-y)
    fxys[1].append(x+y)
ls = []
for d in [0, 1]:
    mx = max(fxys[d])
    mi = min(fxys[d])
    ls.append(mx-mi)
print(max(ls))

Solution (Python):
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()


    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    qqqq = 0
    wwww = 1000000000000000000000000000
    a = []
    for i in range(n):
        x,y = invr()
        a.append((x,y))
        q = max(q,x + y)
        w = min(w,x + y)
        qq = max(qq,x - y)
        ww = min(ww,x - y)
        qqqq = max(qqqq,y - x)
        wwww = min(wwww,y - x)
    if len(set(a)) == 1:
        print(0)
    else:
        print(max(q - w,qq - ww,qqqq - wwww))
    


 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)


        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Solution (Python):
mod = 10**9 + 7
def C():
    N = int(input())
    ans = 10**N - 2*9**N + 8**N
    print(ans%mod)
def A():
    N = int(input())
    if( N == 0):
        print(1)
    else:
        print(0)
def B():
    a,b,c,d = map(int,input().split())
    print(max(a*c,a*d,b*c,b*d))

def func(x,y):
    return [x-y,x+y]
def E():
    N = int(input())
    points = [list(map(int,input().split())) for _ in range(N)]
    
    d0list = [func(*p)[0] for p in points]
    d1list = [func(*p)[1] for p in points]
    d0Max = max(d0list) - min(d0list)
    d1Max = max(d1list) - min(d1list)
    print(max(d0Max,d1Max))
E()

Solution (Python):
xy=[]
invxy=[]
n=int(input())
for i in range(n):
    x,y = map(int,input().split())
    xy.append([x,y])
    invxy.append([x,-y])
ma=-10**20
mi=10**20
for i in xy:
    if ma<(i[0]+i[1]):
        ma=i[0]+i[1]
    if mi>(i[0]+i[1]):
        mi=i[0]+i[1]
invma=-10**20
invmi=10**20
for i in invxy:
    if invma<(i[0]+i[1]):
        invma=i[0]+i[1]
    if invmi>(i[0]+i[1]):
        invmi=i[0]+i[1]
k=abs(ma-mi)
t=abs(invma-invmi)
print(max(k,t))

Solution (Python):
n=int(input())
l1=[]
l2=[]
for _ in range(n):
    x,y=map(int,input().split())
    l1.append(x+y)
    l2.append(x-y)
print(max(max(l1)-min(l1),max(l2)-min(l2)))

Solution (Python):
n=int(input())
h=[]
add=[]
diff=[]
diff1=[]
for i in range(n):
  l=list(map(int,input().split()))
  h.append(l)
  p=h[i][0]+h[i][1]
  add.append(p)
  k=h[i][0]-h[i][1]
  diff.append(k)
  r=h[i][1]-h[i][0]
  diff1.append(r)
a=max(add)-min(add)
b=max(diff)-min(diff)
c=max(diff1)-min(diff1)
print(max(a,b,c))

Solution (Python):
N=int(input())


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

Sum = sorted(Sum)
Sub=sorted(Sub)
ans=max(abs(Sum[-1]-Sum[0]),abs(Sub[-1]-Sub[0]))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
xy = tuple(map(int, input().split()))
pM = sum(xy)
pm = sum(xy)
mM = xy[0] - xy[1]
mm = xy[0] - xy[1]
for _ in range(n - 1):
    xy = tuple(map(int, input().split()))
    s = sum(xy)
    d = xy[0] - xy[1]
    if s > pM:
        pM = s
    elif s < pm:
        pm = s
    if d > mM:
        mM = d
    elif d < mm:
        mm = d
print(max(abs(pM - pm), abs(mM - mm)))

Solution (Python):
import sys


def main():
    N = int(sys.stdin.readline().rstrip())

    X = [None] * N
    Y = [None] * N 
    Z = [None] * N

    for i in range(N):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        X[i] = x
        Y[i] = y
    
    X_min = min(X)
    Y_min = min(Y)

    for i in range(N):
        X[i] = X[i] - X_min
        Y[i] = Y[i] - Y_min
        Z[i] = X[i] + Y[i]

    ans1 = max(Z) - min(Z)

    X_max = max(X)

    for i in range(N):
        X[i] = X_max - X[i]
        Y[i] = Y[i] - Y_min
        Z[i] = X[i] + Y[i]

    ans2 = max(Z) - min(Z)

    print(max(ans1, ans2))


main()

Solution (Python):
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n = int(data())
points = []
for i in range(n):
    points.append(L())
arr = []
for x, y in points:
    arr.append(x + y)
arr.sort()
answer = arr[-1] - arr[0]
arr = []
for x, y in points:
    arr.append(x - y)
arr.sort()
answer = max(answer, arr[-1] - arr[0])
out(answer)

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

xy1 = max(x + y for x, y in xy)
xy2 = max(-x - y for x, y in xy)
xy3 = max(-x + y for x, y in xy)
xy4 = max(x - y for x, y in xy)

print(max(xy1 + xy2, xy3 + xy4))

Solution (Python):
N = int(input())

dists = []
while N:
    x, y = map(int, input().split())
    dists.append((x, y, x+y, y-x))
    N -= 1

dists1 = sorted(dists, key=lambda x: x[2])
dists2 = sorted(dists, key=lambda x: x[3])

ans1 = abs(dists1[0][0] - dists1[-1][0]) + abs(dists1[0][1] - dists1[-1][1])
ans2 = abs(dists2[0][0] - dists2[-1][0]) + abs(dists2[0][1] - dists2[-1][1])

print(max(ans1, ans2))

Solution (Python):
import math

n = int(input())

x = list(range(n))
y = list(range(n))
m = list(range(n))
l = list(range(n))
for i in range(n):
  x[i],y[i] = map(int,input().split())
  m[i] = x[i] - y[i]
  l[i] = x[i] + y[i]
m.sort()
l.sort()
res = max(m[n-1]-m[0], l[n-1]-l[0])
print(res)

Solution (Python):
n = int(input())
p = [0 for _ in range(n)]
m = [0 for _ in range(n)]
for i in range(n):
  xi,yi = map(int,input().split())
  p[i] = xi+yi
  m[i] = xi-yi
p.sort()
m.sort()
print(max(p[-1] - p[0],m[-1] - m[0]))

Solution (Python):
def main():
    n = int(input())
    s = [0] * n
    d = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        s[i] = x + y
        d[i] = x - y
    print(max(max(s) - min(s), max(d) - min(d)))


if __name__ == '__main__':
    main()

Solution (Python):

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


p_max = (-1) * (10**10)
p_min = (10**10)

m_max = (-1) * (10**10)
m_min = 10**10

for i in range(N):
    l = lxy[i]
    p = l[0] + l[1]
    m = l[0] - l[1]

    if(p_max < p):
        p_max = p
    if(p_min > p):
        p_min = p
    
    if(m_max < m):
        m_max = m 
    if(m_min > m):
        m_min = m

print(max(p_max-p_min, m_max-m_min))

Solution (Python):

n = int(raw_input())
points = set([])
for _ in range(n):
	p = map(int, raw_input().split())
	points.add(tuple(p))
points = list(points)
def distance(p,q): return abs(p[0] - q[0]) + abs(p[1] - q[1])


def f(points):
	r = 0
	for u in [-1,1]:
		for v in [-1,1]:
			pps = [u*x + v*y for x,y in points]
			r = max(r, max(pps) - min(pps))
	return r
print f(points)

Solution (Python):
n = int(input())
xxx = []
yyy = []
for _ in range(n):
    cx, cy = map(int, input().split())
    xxx.append(cx + cy)
    yyy.append(cx - cy)

max_x = max(xxx)
min_x = min(xxx)
max_y = max(yyy)
min_y = min(yyy)

print(max(max_x - min_x, max_y - min_y))

Solution (Python):
n = int(input())

xmi = 1e18
xma = -1e18
ymi = 1e18
yma = -1e18
for i in range(n):
    x, y = map(int, input().split())
    xmi = min(xmi, x+y)
    xma = max(xma, x+y)
    ymi = min(ymi, x-y)
    yma = max(yma, x-y)
ans = 0
ans = max(ans, xma - xmi)
ans = max(ans, yma - ymi)
print(ans)

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
import math
ll=[]
lll=[]
for i in range(n):
    ll.append([l[i][0]+l[i][1],i])
    lll.append([l[i][0]-l[i][1],i])
ll.sort()
lll.sort()

a=int(math.fabs(l[ll[0][1]][0]-l[ll[-1][1]][0])+math.fabs(l[ll[0][1]][1]-l[ll[-1][1]][1]))
b=int(math.fabs(l[lll[0][1]][0]-l[lll[-1][1]][0])+math.fabs(l[lll[0][1]][1]-l[lll[-1][1]][1]))

print(max(a,b))

Solution (Python):
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  
    x_y_arr = []
    for i in range(N):
        _ = list(map(int, _in[i+1].split(' ')))  
        x_y_arr.append(_)
    
    f_x_y_arr0 = []
    f_x_y_arr1 = []
    for x, y in x_y_arr:
        f_x_y_arr0.append(x - y)
        f_x_y_arr1.append(x + y)
    f_x_y_arr0.sort(reverse=True)
    f_x_y_arr1.sort(reverse=True)
    ans = max((f_x_y_arr0[0] - f_x_y_arr0[-1]), (f_x_y_arr1[0] - f_x_y_arr1[-1]))
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

print(max(max(a)-min(a), max(b)-min(b)))

Solution (Python):

import sys


def solve(N: int, x: "List[int]", y: "List[int]"):
    z = [xx+yy for xx, yy in zip(x, y)]
    zz = [xx-yy for xx, yy in zip(x, y)]
    return max(abs(min(z) - max(z)), abs(min(zz) - max(zz)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, x, y))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

n = int(input())
INF = 1 << 35
M = -INF
m = INF
d0 = []
d1 = []
for i in range(n):
    x, y = map(int, input().split())
    a = x - y
    b = x + y
    d0.append(a)
    d1.append(b)
print(max(max(d0) - min(d0), max(d1) - min(d1)))

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
xy = []
xs = []
ys = []
for _ in range(N):
    x, y = map(int, input().split())
    xy.append([x - y, x + y])
    xs.append(x - y)
    ys.append(x + y)

diff1 = max(xs) - min(xs)
diff2 = max(ys) - min(ys)
ans = max(diff1, diff2)
print(ans)

Solution (Python):
n = int(input())
xy = []
for _ in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
    
al,be = 1000000000,1000000000
f = [(1,1),(1,-1),(-1,1),(-1,-1)]
ans = -1145141919810364

for k,l in f:
    alfa = al * k
    beta = be * l
    man = []
    for i,j in xy:
        man.append(abs(alfa-i) + abs(beta-j))
    ans = max(ans,max(man) - min(man))
    
print(ans)

Solution (Python):
N=int(input())
axis1=[]
axis2=[]
for i in range(N):
    x,y=map(int,input().split())
    axis1.append(x+y)
    axis2.append(x-y)
a1=max(axis1)-min(axis1)
a2=max(axis2)-min(axis2)
print(max(a1,a2))

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
point = []
p = []
m = []
for i in range(n):
    a,b = mp()
    point.append((a,b))
    p.append(a+b)
    m.append(a-b)
print(max(max(p)-min(p), -min(m)+max(m), max(m)-min(m), -min(p)+max(p)))

Solution (Python):
n=int(input())

xy=[]
for i in range(n):
    xi,yi=map(int,input().split())
    xy.append([xi,yi])

f0=[]
f1=[]

for i in range(n):
    f0.append(xy[i][0]-xy[i][1])
    f1.append(xy[i][0]+xy[i][1])

print(max(max(f0)-min(f0),max(f1)-min(f1)))

Solution (Python):
n = int(input())
fx = [[0 for i in range(4)] for j in range(n)]

for i in range(n):
  x, y = map(int, input().split())
  fx[i][0] = x + y
  fx[i][1] = x - y
  fx[i][2] = - x + y
  fx[i][3] = - x - y

ans = 0
for j in range(4):
  saidai = -(10 ** 10)
  saisho = 10 ** 10
  for i in range(n):
    if saidai < fx[i][j]:
      saidai = fx[i][j]
    if saisho > fx[i][j]:
      saisho = fx[i][j]
  ans = max(ans, saidai - saisho)

print(ans)

Solution (Python):
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
ans=[]
cand=[xy[i][0]+xy[i][1] for i in range(n)]

ans.append(max(cand)-min(cand))
cand=[-xy[i][0]+xy[i][1]for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
print(max(ans))

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

n = int(readline())

p = [list(map(int,readline().split())) for i in range(n)]

for i in range(n):
    x = p[i][0]
    y = p[i][1]
    p[i][0] = x-y
    p[i][1] = x+y

dmax0 = -INF
dmin0 = INF
dmax1 = -INF
dmin1 = INF

for (x,y) in p:
    dmax0 = max(dmax0, x)
    dmin0 = min(dmin0, x)
    dmax1 = max(dmax1, y)
    dmin1 = min(dmin1, y)

print(max(dmax1-dmin1, dmax0-dmin0))

Solution (Python):

import numpy as np
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def blute(N, XY):
    ret = np.zeros(N, np.int64)
    for i in range(N):
        ret[i] = np.max(np.abs(XY - XY[i]).sum(axis=1))
    return np.max(ret)


def solve(N, XY):
    S = XY.sum(axis=1)
    p1 = np.argmax(S)
    p2 = np.argmin(S)
    D = XY[:, 0] - XY[:, 1]
    p3 = np.argmax(D)
    p4 = np.argmin(D)
    return max(S[p1] - S[p2], D[p3] - D[p4])
    


def main():
    
    N = int(input())
    XY = np.int64(read().split())
    XY = XY.reshape((N, 2))
    print(solve(N, XY))



T1 = """
3
1 1
2 4
3 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
2
1 1
1 1
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

TEST_T3 = """
>>> N = 100
>>> np.random.seed(1)
>>> solve(N, np.random.randint(1, 100, (N, 2)))
189
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
n=int(input())
bignum=10**30
num1,num2,num3,num4=-bignum,bignum,-bignum,bignum
for i in range(n):
  x,y=map(int, input().split())
  num1=max(x+y,num1)
  num2=min(x+y,num2)
  num3=max(x-y,num3)
  num4=min(x-y,num4)
print(max(num1-num2,num3-num4))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
que = [getList() for i in range(N)]











minus = []
plus = []
for x, y in que:
    minus.append(x - y)
    plus.append(x + y)
minus.sort()
plus.sort()
m = minus[-1] - minus[0]
p = plus[-1] - plus[0]
print(max(abs(m), abs(p)))

Solution (Python):
N = int(input())
XYs = [list(map(int, input().split())) for _ in range(N)]
XYs.sort()

prevX = None
minY = maxY = XYs[0][1]
ans = 0
for x, y in XYs:
    if prevX != x and prevX is not None:
        minY -= x - prevX
        maxY += x - prevX
    ans = max(ans, abs(minY-y), abs(maxY-y))
    minY = minY if minY < y else y
    maxY = maxY if maxY > y else y
    prevX = x
print(ans)

Solution (Python):
import os
from io import BytesIO, IOBase
import sys
def main():
    n = int(input())
    a = []
    for i in range(n):
        a.append(list(map(int, input().split())))
    b=max(a,key=lambda x:x[0]+x[1])
    c=min(a,key=lambda x:x[0]+x[1])
    ma=abs(b[0]+b[1]-(c[0]+c[1]))
    b=max(a,key=lambda x:x[0]-x[1])
    c=max(a,key=lambda x:x[1]-x[0])
    ma=max(ma,abs(b[0]+c[1]-(c[0]+b[1])))
    print(ma)

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

if __name__ == "__main__":
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  



n = ni()
m0 = -inf
s0 = inf
m1 = -inf
s1 = inf
for i in range(n):
    xi, yi = na()
    diff = xi - yi
    summ = xi + yi
    m0 = max(diff, m0)
    s0 = min(diff, s0)
    m1 = max(summ, m1)
    s1 = min(summ, s1)

print(max(m0-s0, m1-s1))

Solution (Python):
import sys
input = sys.stdin.readline

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

iNE=None
maxNE=-1e12
iNW=None
maxNW=-1e12
iSE=None
maxSE=-1e12
iSW=None
maxSW=-1e12

for i in range(N):
    p = pts[i]
    NE = p[0] + p[1]
    NW = -p[0] + p[1]
    SE = p[0] - p[1]
    SW = -p[0] - p[1]
    if NE > maxNE:
        maxNE = NE
        iNE = i
    if SE > maxSE:
        maxSE = SE
        iSE = i
    if NW > maxNW:
        maxNW = NW
        iNW = i
    if SW > maxSW:
        maxSW = SW
        iSW = i

d1 = abs(pts[iNE][0]-pts[iSW][0])+abs(pts[iNE][1]-pts[iSW][1])
d2 = abs(pts[iNW][0]-pts[iSE][0])+abs(pts[iNW][1]-pts[iSE][1])

print(max(d1,d2))