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):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    def manhattan_distance(p1,p2):
        x1,y1 = p1
        x2,y2 = p2
        return abs(x1-x2) + abs(y1-y2)
    
    def chebyshev_distance(p1,p2):
        x1,y1 = p1
        x2,y2 = p2
        return max(abs(x1-x2),abs(y1-y2))



    N = II()
    
    points = []
    from random import random
    f_0 = []
    f_1 = []
    for i in range(N):
        x,y = LMIIS()
        
        
        
        points.append((x,y))
        f_0.append(x-y)
        f_1.append(x+y)
    ans = 0
    ans = max(ans,max(f_0)-min(f_0))
    ans = max(ans,max(f_1)-min(f_1))
    
    print(ans)

    
    
    
    
    
    
    

    
    




main()

Solution (Python):
N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int, input().split())))


def f(x, y):
    return [x - y, x + y]


XY = []
for x, y in xy:
    XY.append(f(x, y))

large, small = [-float('inf'), -float('inf')], [float('inf'), float('inf')]
for i in range(2):
    for j in XY:
        large[i] = max(j[i], large[i])
        small[i] = min(j[i], small[i])

ans = max(large[0] - small[0], large[1] - small[1])
print(ans)

Solution (Python):
n = int(input())
d1 = []
d2 = []
for i in range(n):
  x,y = map(int,input().split())
  d1.append(x-y)
  d2.append(x+y)
one = max(d1)-min(d1)
two = max(d2)-min(d2)
print(max(one,two))

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

max_f_0 = -10**10
min_f_0 = 10**10
max_f_1 = -10**10
min_f_1 = 10**10

for _ in range(N):
    x, y = map(int, input().split(" "))
    f_0 = x - y
    f_1 = x + y
    
    if max_f_0 < f_0:
        max_f_0 = f_0
    if min_f_0 > f_0:
        min_f_0 = f_0
    if max_f_1 < f_1:
        max_f_1 = f_1
    if min_f_1 > f_1:
        min_f_1 = f_1
        
print(max((max_f_0-min_f_0), (max_f_1-min_f_1)))

Solution (Python):
N = int(input())
ls = []
lt= []
for _ in range(N):
    x,y = map(int, input().split())
    s = x+y
    t = x-y

    ls.append(s)
    lt.append(t)

print(max(max(ls) - min(ls),max(lt) - min(lt)))

Solution (Python):
n = int(input())
x,y = map(int,input().split())
lx = x+y
ly = (x-y)
maxlx = lx
minlx = lx
maxly = ly
minly = ly
for _ in range(n-1):
  x,y = map(int,input().split())
  lx = x+y
  ly = (x-y)
  maxlx = max(maxlx,lx)
  minlx = min(minlx,lx)
  maxly = max(maxly,ly)
  minly = min(minly,ly)
print(max(maxlx-minlx,maxly-minly))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]

    X, Y = [], []
    for x, y in XY:
        X.append(x + y)
        Y.append(x - y)
    res = max(max(X) - min(X), max(Y) - min(Y))
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
N=int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]

xyp=[]
xym=[]
for i in range(N):
    xyp.append(x[i]+y[i])
    xym.append(x[i]-y[i])
    
print(max(max(xyp)-min(xyp),-min(xym)+max(xym),max(xym)-min(xym),-min(xym)+max(xym)))

Solution (Python):
def calc(x, y):
    ans = 0
    ans += abs(x[0] - y[0])
    ans += abs(x[1] - y[1])
    return ans
N = int(input())
pts = [[0, 0] for i in range(N)]
d = (10 ** 9) // 2
dist_0 = 0
for i in range(N):
    x, y = list(map(int, input().split()))
    pts[i][0], pts[i][1] = x - d, y -d
    dist_0 = max(dist_0, calc(pts[i], [0, 0]))
s = set()
for pt in pts:
    if calc(pt,[0,0]) == dist_0:
        s.add(tuple(pt))
ans = 0
for pt in pts:
    for can in s:
        ans = max(ans, calc(pt, list(can)))
print(ans)

Solution (Python):
n = int(input())
X = [0] * n
Y = [0] * n
cx = []
cy = []

for i in range(n):
    X[i], Y[i] = map(int, input().split())
    cx.append(X[i] - Y[i])
    cy.append(X[i] + Y[i])




ans = max(max(cx) - min(cx), max(cy) - min(cy))
print(ans)

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

a = []
b = []

for i in range(n):
  a.append(p[i][0] - p[i][1])
  b.append(p[i][0] + p[i][1])
  
ans = max(max(a)-min(a),max(b)-min(b))
print(ans)

Solution (Python):








def solve(N, xyi):
    plus_max = - 10 ** 18
    plus_min = + 10 ** 18
    minus_max = - 10 ** 18
    minus_min = + 10 ** 18

    for x, y in xyi:
        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)
    ans = max(abs(plus_max - plus_min), abs(minus_max - minus_min))
    print(ans)


if __name__ == '__main__':
    
    N = int(input())
    
    
    
    xyi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, xyi)

Solution (Python):
import heapq
N = int(input())
xy_s = [list(map(int,input().split())) for _ in range(N)]
XPYMAX = []
XPYMIN = []
XMYMAX = []
XMYMIN = []
heapq.heapify(XPYMAX)
heapq.heapify(XPYMIN)
heapq.heapify(XMYMAX)
heapq.heapify(XMYMIN)
answer = 0
for i, xy in enumerate(xy_s):
    x = xy[0]
    y = xy[1]
    heapq.heappush(XPYMAX,-(x+y))
    heapq.heappush(XMYMAX,-(x-y))
    heapq.heappush(XPYMIN,(x+y))
    heapq.heappush(XMYMIN,(x-y))

    if i == 0:
        continue

    xpy = x+y
    xmy = x-y
    xpymax = -XPYMAX[0]
    xpymin = XPYMIN[0]
    xmymax = -XMYMAX[0]
    xmymin = XMYMIN[0]
    dist = max(abs(xpymax-xpy), abs(xpymin-xpy), abs(xmymax-xmy), abs(xmymin-xmy))
    answer = max(dist, answer)
print(answer)

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

xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]

x_c = [x + y for (x, y) in zip(x, y)]
y_c = [x - y for (x, y) in zip(x, y)]

ans = max(x_c) - min(x_c)

ans_1 = max(y_c) - min(y_c)

if ans < ans_1:
    ans = ans_1

print(ans)

Solution (Python):
def main():
    inf=float("inf")
    n=int(input())
    mx=[-inf,-inf,-inf,-inf]
    mn=[inf,inf,inf,inf]
    for i in range(n):
        x,y=map(int,input().split())
        if x+y>mx[0] : mx[0]=x+y
        if x+y<mn[0] : mn[0]=x+y
        if x-y>mx[1] : mx[1]=x-y
        if x-y<mn[1] : mn[1]=x-y
        if -x-y>mx[2] : mx[2]=-x-y
        if -x-y<mn[2] : mn[2]=-x-y
        if -x+y>mx[3] : mx[3]=-x+y
        if -x+y<mn[3] : mn[3]=-x+y
    print(max([mx[i]-mn[i] for i in range(4)]))

main()

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

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

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for x, y in P:
    X.append(x)
    Y.append(y)
mx = (min(X) + max(X)) // 2
my = (min(Y) + max(Y)) // 2

Qx = []
Qy = []
for x, y in P:
    x, y = x-mx, y-my
    Qx.append(x+y)
    Qy.append(x-y)

ax = max(Qx) - min(Qx)
ay = max(Qy) - min(Qy)
ans = max(ax, ay)
print(ans)

Solution (Python):
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = 0
ur = sorted(xy, key=lambda x: x[0]+x[1])[-1]
ul = sorted(xy, key=lambda x: x[1]-x[0])[-1]
dr = sorted(xy, key=lambda x: x[0]-x[1])[-1]
dl = sorted(xy, key=lambda x: -x[0]-x[1])[-1]

l = [ur, ul, dr, dl]
for i in l:
  for j in l:
    ans = max(ans, abs(i[0]-j[0])+abs(i[1]-j[1]))
print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    XY = [[int(x) for x in input().split()] for _ in range(N)]

    arr1 = []
    arr2 = []
    for x, y in XY:
        arr1.append(x)
        arr2.append(y)


    minX, maxX = min(arr1), max(arr1)
    minY, maxY = min(arr2), max(arr2)

    ans = 0
    
    for point in [(minX, minY), (maxX, minY), (minX, maxY), (maxX, maxY)]:
        minD = float('inf')
        maxD = float('-inf')
        for i in range(0, len(arr1)):
            distance = abs(arr1[i] - point[0]) + abs(arr2[i] - point[1])
            minD = min(minD, distance)
            maxD = max(maxD, distance)
        ans = max(ans, maxD - minD)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    N=int(input())
    A=[list(map(int,input().split())) for _ in range(N)]
    B=[]
    C=[]
    for x in A:
        B.append(x[0]+x[1])
        C.append(x[0]-x[1])
    b=max(B)-min(B)
    c=max(C)-min(C)
    d=[b,c]
    print(max(d))
    
   


if __name__ == '__main__':
    main()

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

Xmax = -2*10**9
Ymax = -2*10**9
Xmin = 2*10**9
Ymin = 2*10**9


for i in range(N):
    x, y = map(int, input().split())
    if (x + y >= Xmax):
        Xmax = x + y
    if (x + y <= Xmin):
        Xmin = x + y
    if (x - y >= Ymax):
        Ymax = x - y
    if (x - y <= Ymin):
        Ymin = x - y

print(max(Xmax - Xmin, Ymax - Ymin))

Solution (Python):
def ge():
    return map(int,input().split())
def main():
    
    
    
    
    N=int(input())
    f0=[]
    f1=[]
    for _ in range(N):
        X,Y=ge()
        f0.append(X-Y)
        f1.append(X+Y)
    ans=max(max(f0)-min(f0),max(f1)-min(f1))
    print(ans)
main()

Solution (Python):
def main():
    N = int(input())
    X = []
    a = -float('inf') 
    b = float('inf') 
    c = -float('inf') 
    d = float('inf') 
    e = -float('inf') 
    f = float('inf') 
    g = -float('inf') 
    h = float('inf') 

    for _ in range(N):
        x, y = map(int, input().split())
        a = max(a, x + y)
        b = min(b, x + y)
        c = max(c, x - y)
        d = min(d, x - y)
        e = max(e, -x + y)
        f = min(f, -x + y)
        g = max(g, -x - y)
        h = min(h, -x - y)
    ans = a - b
    ans = max(ans, c-d)
    ans = max(ans, e-f)
    ans = max(ans, g-h)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
dmax_0=-10**10
dmin_0=10**10
dmax_1=-10**10
dmin_1=10**10
for i,j in xy:
  dmax_0=max(i-j,dmax_0)
  dmin_0=min(i-j,dmin_0)
  dmax_1=max(i+j,dmax_1)
  dmin_1=min(i+j,dmin_1)
print(max(dmax_0-dmin_0,dmax_1-dmin_1))

Solution (Python):
n = int(input())
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    x_list.append(x - y)
    y_list.append(x + y)
x_list.sort()
y_list.sort()
ans = max(x_list[-1] - x_list[0], y_list[-1] - y_list[0])
print(ans)

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

for x,y in XY:
  X_.append(x-y)
  Y_.append(x+y)

print(max(max(X_)-min(X_), max(Y_)-min(Y_)))

Solution (Python):
def resolve():
    N = int(input())
    _xmin, _xmax = float("inf"), -float("inf")
    _ymin, _ymax = float("inf"), -float("inf")
    for i in range(N):
        x, y = list(map(int, input().split()))
        _x, _y = x - y, x + y
        _xmin = min(_x, _xmin)
        _xmax = max(_x, _xmax)
        _ymin = min(_y, _ymin)
        _ymax = max(_y, _ymax)
    print(max(_xmax-_xmin, _ymax-_ymin))


if '__main__' == __name__:
    resolve()

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

XY_max = -10**10
XY_min = 10**10
YX_max = -10**10
YX_min = 10**10

for _ in range(N):
  x,y = map(int, input().split())
  XY_max = max(XY_max,x+y)
  XY_min = min(XY_min,x+y)
  YX_max = max(YX_max,x-y)
  YX_min = min(YX_min,x-y)

print(max(XY_max-XY_min,YX_max-YX_min))

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


x_minus_y = []
x_plus_y = []
for i in range(n):
    x_minus_y.append(xy[i][0] - xy[i][1])
    x_plus_y.append(xy[i][0] + xy[i][1])
x_max = max(x_minus_y)
x_min = min(x_minus_y)
y_max = max(x_plus_y)
y_min = min(x_plus_y)

if x_max - x_min >= y_max - y_min:
    print(x_max - x_min)
else:
    print(y_max - y_min)

Solution (Python):









import os
import sys




def f(x, y, version):
    if version == 0:
        return x+y
    else:
        return x-y

def main():
    N = int(input())
    ch_0 = []
    ch_1 = []
    trans_max = -1
    for _ in range(N):
        x, y = map(int, input().split())
        ch_0.append(f(x, y, 0))
        ch_1.append(f(x, y, 1))
    ans_0 = max(ch_0)-min(ch_0)
    ans_1 = max(ch_1)-min(ch_1)
    if ans_0 < ans_1:
        print(ans_1)
    else:
        print(ans_0)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

n = int(input())

x = []
y = []
for i in range(n):
  l = list(map(int, input().split()))
  x.append(l[0])
  y.append(l[1])

x = np.array(x)
y = np.array(y)

xy0 = x + y
xy1 = x - y

print(max(max(xy0)-min(xy0),max(xy1)-min(xy1)))

Solution (Python):
n=int(input())
X=[]
Y=[]

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

    
ans = max(max(X)-min(X),max(Y)-min(Y))

print(ans)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = []
B = []
for _ in range(N):
    x, y = map(int, readline().split())
    A.append(x+y)
    B.append(x-y)

a = max(A)
b = min(A)
c = max(B)
d = min(B)

print(max(abs(a-b),abs(c-d)))

Solution (Python):

"""
Created on Sun Sep 13 20:41:42 2020

@author: liang
"""

N = int(input())
d = list()
for i in range(N):
    x, y = map(int,input().split())
    d.append((x,y))

d.sort(key=lambda x:x[0]+x[1])


ans1 = abs(d[0][0] - d[N-1][0]) + abs(d[0][1] - d[N-1][1])

d.sort(key=lambda x:x[0]-x[1])

ans2 = abs(d[0][0] - d[N-1][0]) + abs(d[0][1] - d[N-1][1])

ans = max(ans1, ans2)

print(ans)

Solution (Python):
n = int(input())
pnts = [tuple(map(int, input().split())) for i in range(n)]

mxsum = max(map(lambda p: p[0]+p[1], pnts))
mnsum = min(map(lambda p: p[0]+p[1], pnts))
mxdif = max(map(lambda p: p[0]-p[1], pnts))
mndif = min(map(lambda p: p[0]-p[1], pnts))

print(max([mxsum - mnsum, mxdif-mndif]))

Solution (Python):

import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict

mod = 10 ** 9 + 7
mod1 = 998244353


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



class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n



class SegmentTree1:
    def __init__(self, data, default=0, func=lambda a, b: max(a , b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)



class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b:a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)



class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD



def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m



def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z



def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por



def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        
        
        if (arr[mid] < key):
            count = mid + 1
            left = mid + 1

        
        else:
            right = mid - 1

    return count



def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c
def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1

    
    
    leftGreater = n

    
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        
        
        else:
            l = m + 1

    
    
    return (n - leftGreater)



n=int(input())
ans=0
d=defaultdict(int)
d1=defaultdict(int)
m=-10**13
m1=-10**13
mi=10**13
mi1=10**13
for i in range(n):
    a,b=map(int,input().split())
    m=max(m,a+b)
    mi=min(mi,a+b)
    m1=max(m1,a-b)
    mi1=min(mi1,a-b)

print(max(m-mi,m1-mi1))

Solution (Python):
N = int(input())
W = []
S = []
for _ in range(N):
    x,y = [int(hoge) for hoge in input().split()]
    wa = x+y
    sa = x-y
    W.append(wa)
    S.append(sa)
T = max(W)- min(W)
Y = max(S)- min(S)
print(max(T,Y))

Solution (Python):
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    x = list()
    y = list()
    for _ in range(n):
        xi, yi = _ia()
        x.append(xi - yi)
        y.append(xi + yi)
    return max(max(x) - min(x), max(y) - min(y))


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

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


mi = min(XY, key=lambda x: x[0] + x[1])
ma = max(XY, key=lambda x: x[0] + x[1])
ans1 = ma[0]-mi[0] + ma[1]-mi[1]


mi = min(XY, key=lambda x: x[0] + (10**9)-x[1])
ma = min(XY, key=lambda x: (10**9)-x[0] + x[1])
ans2 = abs(ma[0]-mi[0]) + abs(ma[1]-mi[1])
print(max(ans1, ans2))