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 os
import heapq
import sys,threading
import math as mt
import operator
from copy import copy
from collections import defaultdict,deque
from io import BytesIO, IOBase

sys.setrecursionlimit(2*10 ** 5)



def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def pw(a,b,md):
    result=1
    while(b>0):
        if(b%2==1):
            result*=a
            result%=md
        a*=a
        a%=md
        b//=2
    return result%md


def inpt():
    return [int(k) for k in input().split()]


n=int(input())
ar=[]
br=[]
for _ in range(n):
    a,b=inpt()
    ar.append((a+b))
    br.append((a-b))

print(max(max(ar)-min(ar), max(br)-min(br)))


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

Solution (Python):
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
xy = [list(x) for x in zip(*xy)]
a = [i+j for i,j in zip(xy[0],xy[1])]
b = [i-j for i,j in zip(xy[0],xy[1])]
aa = max(a) - min(a)
ba = max(b) - min(b)
print(max(aa,ba))

Solution (Python):




import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n = read_int()
    xy = [tuple(read_ints()) for _ in range(n)]
    diff = [x - y for x, y in xy]
    sum_ = [x + y for x, y in xy]
    print(max(max(sum_) - min(sum_), max(diff) - min(diff)))

if __name__ == '__main__':
    Main()

Solution (Python):
n=int(input())
z=[]
w=[]
for i in range(n):
  x,y=map(int,input().split())
  z.append(x+y)
  w.append(x-y)
ans=max(max(z)-min(z), max(w)-min(w))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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




minX, maxX = min(xs), max(xs)
minY, maxY = min(ys), max(ys)



ans = 0
for x, y in zip(xs, ys):
    cs = [abs(x-minX), abs(x-maxX), abs(y-minY), abs(y-maxY)]
    m = max(cs)
    if m > ans:
        ans = m

print(ans)

Solution (Python):


def main():
    n = int(input())
    xy = [list(map(int, input().split())) for i in range(n)]
    max_z, max_w, min_z, min_w = -10**20, -10**20, 10**20, 10**20
    ans = 0
    for p in xy:
        max_z, max_w = max(max_z, p[0] + p[1]), max(max_w, p[0] - p[1])
        min_z, min_w = min(min_z, p[0] + p[1]), min(min_w, p[0] - p[1])
    ans = max(max_z - min_z, max_w - min_w)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
l=[list(map(int,input().split())) for _ in range(int(input()))]
f=sorted([x+y for x,y in l])
g=sorted([x-y for x,y in l])
print(max(f[-1]-f[0],g[-1]-g[0]))

Solution (Python):
N = int(input())
z = [None] * N
w = [None] * N
for i in range(N):
    x, y = map(int, input().split())
    z[i] = x + y
    w[i] = x - y

print(max(max(z)-min(z), max(w)-min(w)))

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    U = []
    V = []
    for _ in range(N):
        x, y = map( int, input().split())
        u, v = x+y, x-y
        U.append(u)
        V.append(v)
    U.sort()
    V.sort()
    print( max(U[-1]-U[0], V[-1]-V[0]))
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
xy = [list(map(int, input().split())) for _i in range(n)]
x = [i+j for i, j in xy]
y = [i-j for i, j in xy]
x.sort()
y.sort()
print(max(abs(x[0]-x[-1]), abs(y[0]-y[-1])))

Solution (Python):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
f0 = sorted([x+y for x, y in xy])
f1 = sorted([x-y for x, y in xy])
print(max(f0[-1]-f0[0], f1[-1]-f1[0]))

Solution (Python):
a,*b=[],
for z in[*open(0)][1:]:x,y=map(int,z.split());a+=x+y,;b+=x-y,
print(max(abs(max(a)-min(a)),abs(max(b)-min(b))))

Solution (Python):
N=int(input())
Z=[0]*N
W=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    Z[i]=x+y
    W[i]=x-y

alpha=max(Z)-min(Z)
beta=max(W)-min(W)
print(max(alpha,beta))

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

XplusY = [x + y for x, y in XY]
XminusY = [x - y for x, y in XY]

print(max([max(XplusY) - min(XplusY), max(XminusY) - min(XminusY)]))

Solution (Python):
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    x, y = i2(N)

    Mw = max(x[i]+y[i] for i in range(N))
    mw = min(x[i]+y[i] for i in range(N))
    Mz = max(x[i]-y[i] for i in range(N))
    mz = min(x[i]-y[i] for i in range(N))

    print(max(Mz-mz, Mw-mw))
    


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input().strip())
l = []
 
for i in range(n):
    x, y = map(int, input().split())
    a = y + x
    b = y - x
    l.append([x, y, a, b])
 
la = sorted(l, key=lambda z: z[2])
lb = sorted(l, key=lambda z: z[3])
 
print(max(abs(la[0][0] - la[-1][0]) + abs(la[0][1]-la[-1][1]),
          abs(lb[0][0] - lb[-1][0]) + abs(lb[0][1]-lb[-1][1])
          )
      )

Solution (Python):




def chebyshev_0(a, b):
    return a - b
def chebyshev_1(a, b):
    return a + b

N = int(input())
X = [0] * N
Y = [0] * N

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

max_0 = - (10 ** 9) - 1
min_0 = 2 * (10 ** 9)
for x, y in zip(X, Y):
    if chebyshev_0(x, y) > max_0:
        max_0 = chebyshev_0(x, y)
    if chebyshev_0(x, y) < min_0:
        min_0 = chebyshev_0(x, y)
l0 = abs(max_0 - min_0)

max_1 = - (10 ** 9) - 1
min_1 = 2 * (10 ** 9)
for x, y in zip(X, Y):
    if chebyshev_1(x, y) > max_1:
        max_1 = chebyshev_1(x, y)
    if chebyshev_1(x, y) < min_1:
        min_1 = chebyshev_1(x, y)
l1 = abs(max_1 - min_1)

print(max([l0, l1]))

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

a = [0 for i in range(N)]
b = [0 for i in range(N)]

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

a = sorted(a)
b = sorted(b)
print(max(a[N-1]-a[0], b[N-1]-b[0]))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N = int(readline())

    mat = []
    a = []
    b = []

    for _ in range(N):
        x, y = map(int, readline().split())
        a.append(x + y)
        b.append(x - y)

    d1 = max(a) - min(a)
    d2 = max(b) - min(b)

    print(max(d1,d2))


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
Z=[0]*N
W=[0]*N

for i in range(N):
  x, y = map(int, input().split())
  Z[i]=x+y
  W[i]=x-y

print(max(max(Z)-min(Z),max(W)-min(W)))

Solution (Python):
import sys
input = sys.stdin.readline
def MI():
    return map(int, input().split())

n = int(input())
z=[]
w=[]
for i in range(n):
    x,y=MI()
    z.append(x+y)
    w.append(x-y)

print(max(max(z)-min(z), max(w)-min(w)))

Solution (Python):
n = int(input())
xx = []
yy = []
for _ in range(n):
    x, y = map(int, input().split())
    xx.append(x + y)
    yy.append(x - y)

print(max(max(xx) - min(xx), max(yy) - min(yy)))

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


def get_output():
    dist = [0 for _ in range(N)]
    X, Y = [], []

    for i, (x, y) in enumerate(xy):
        x, y = x-y, x+y
        X.append(x)
        Y.append(y)

    a = max(X) - min(X)
    b = max(Y)-min(Y)
    return max(a, b)


print(get_output())

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=set(tuple([lnii() for i in range(n)]))

if len(l)==1:
  print(0)
  exit()

x_max=0
x_min=10**10
y_max=0
y_min=10**10

for x,y in l:

  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)


  t=x+y
  y_max=max(y_max,t)
  y_min=min(y_min,t)

x_ans=x_max-x_min
y_ans=y_max-y_min
print(max(x_ans,y_ans))

Solution (Python):
n = int(input())
c = [[int(i) for i in input().split()] for i in range(n)]
z = []
w = []
for i in range(n):
    z.append(c[i][0] + c[i][1])
    w.append(c[i][1] - c[i][0])
ans = max(max(z)-min(z), max(w)-min(w))
print(ans)

Solution (Python):

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

z = [x + y for x, y in X]
w = [x - y for x, y in X]

print(max(max(z) - min(z), max(w) - min(w)))

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

ws = [x+y for x,y in xys]
zs = [x-y for x,y in xys]

print(max([max(ws)-min(ws), max(zs)-min(zs)]))

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    a0 = a1 = a2 = a3 = INF

    ans = 0
    for _ in range(int(input())):
        x, y = map(int, input().split())
        ans = max(ans, x + y - a0, x - y - a1, -x + y - a2, -x - y - a3)
        a0 = min(a0, x + y)
        a1 = min(a1, x - y)
        a2 = min(a2, -x + y)
        a3 = min(a3, -x - y)

    print(ans)
resolve()

Solution (Python):

N = int(input())
pos_x_list = []
pos_y_list = []

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

print(max(max(pos_x_list) - min(pos_x_list), max(pos_y_list) - min(pos_y_list)))

Solution (Python):
n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)]

mi = 10**10
ma = 0

for i in range(n):
    tmp = xy[i][0] + xy[i][1]
    if tmp > ma:
        ma = tmp
    
    if tmp < mi:
        mi = tmp
        
ans = ma-mi

mi = 10**10
ma = -10**10

for i in range(n):
    tmp = xy[i][0] - xy[i][1]
    if tmp > ma:
        ma = tmp
    
    if tmp < mi:
        mi = tmp
        
print(max(ans,ma-mi))

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

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

Solution (Python):
n = int(input())
XY = [tuple(map(int, input().split())) for i in range(n)]
A = [x + y for x, y in XY]
B = [x - y for x, y in XY]
print(max(max(A) - min(A), max(B) - min(B)))

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

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

answer=max(pxylist[-1]-pxylist[0],mxylist[-1]-mxylist[0])
print(answer)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
A,B = [],[]  
for i in range(N):
    x,y = MI()
    A.append(x+y)
    B.append(x-y)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

ans1 = []
ans2 = []
for i in range(N):
    ans1.append(X[i] + Y[i])
    ans2.append(Y[i] - X[i])
ans1.sort()
ans2.sort()

a = ans1[-1] - ans1[0]
b = ans2[-1] - ans2[0]

print(max(a,b))

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

x=[]
y=[]
for _ in range(n):
    xx,yy=map(int,input().split())
    x.append(xx)
    y.append(yy)

def maxAbsValExpr(arr1, arr2):
    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)
    return ans


print(maxAbsValExpr(x, y))

Solution (Python):
N = int(input())
X = [[] for _ in range(N)]
z = [0 for _ in range(N)]
w = [0 for _ in range(N)]
for i in range(N):
    X[i] = list(map(int, input().split()))
    z[i] = X[i][0] +X[i][1]
    w[i] = X[i][0] -X[i][1]

ans = max(max(z)-min(z), max(w)-min(w))
print(ans)

Solution (Python):
N = int(input())
Zlist=[]
Wlist = []
for i in range(N):
    x,y = map(int,input().split())
    z = x+y
    w = x-y
    Zlist.append(z)
    Wlist.append(w)
Zlist.sort()
Wlist.sort()
print(max(Zlist[-1]-Zlist[0],Wlist[-1]-Wlist[0]))

Solution (Python):
X = []
Y = []
N = int(input())
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
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
from itertools import accumulate
sys.setrecursionlimit(10**6)




def floor(a, b): return -(-a // b)


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


N = z()
X, Y = [], []
dist = [0]*(N)  
for i in range(N):
    x, y = zz()
    x, y = x-y, x+y

    X.append(x)
    Y.append(y)

a = max(X) - min(X)
b = max(Y)-min(Y)
print(max(a, b))

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

l = [None] * N

for i in range(N):
    l[i] = list(map(int, input().split()))

minX = min([e[0] for e in l])
minY = min([e[1] for e in l])
maxX = max([e[0] for e in l])
maxY = max([e[1] for e in l])

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

s0 = min([d([minX,minY], e) for e in l])
s1 = min([d([maxX,maxY], e) for e in l])
 
t0 = min([d([maxX,minY], e) for e in l])
t1 = min([d([minX,maxY], e) for e in l])
 

print(d([minX,minY], [maxX,maxY]) - min(s0+s1, t0+t1))

Solution (Python):


import sys
input=sys.stdin.readline

n=int(input())
xs=[]
ys=[]
for _ in range(n):
    x,y=map(int,input().split())
    tx,ty=x+y,x-y
    xs.append(tx)
    ys.append(ty)
xs=sorted(xs)
ys=sorted(ys)
ans=max(abs(xs[-1]-xs[0]),abs(ys[-1]-ys[0]))
print(ans)

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

def f(x,y):
  return x-y

def g(x,y):
  return x+y
  
print(max(max([f(x[i],y[i]) for i in range(n)])-min([f(x[i],y[i]) for i in range(n)]), max([g(x[i],y[i]) for i in range(n)])-min([g(x[i],y[i]) for i in range(n)])))

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
zahyo = [l() for _ in range(N)]
zahyo2 = [sum(zahyo[i]) for i in range(N)]
zahyo3 = [zahyo[i][0]-zahyo[i][1] for i in range(N)]
ans = 0
print(max(max(zahyo2)-min(zahyo2),max(zahyo3)-min(zahyo3)))

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

f0 = [x - y for x, y in xy]
f1 = [x + y for x, y in xy]

f0.sort()
f1.sort()

ans = max((f0[-1] - f0[0]), (f1[-1] - f1[0]))
print(ans)

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

Solution (Python):
N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(reverse=True)

ans = 0
M = xy[0][0] + xy[0][1]
m = xy[0][0] - xy[0][1]
for x, y in xy[1:]:
    ans = max(ans, M-x-y, m-x+y)
    M = max(M, x+y)
    m = max(m, x-y)

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

import itertools


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


def dx(p1, p2):
    return abs(p1[0] + p2[0]) // 2


def dy(p1, p2):
    return abs(p1[0] - p2[0]) // 2


def slow_solve(N, XYs):
    ans = 0
    for points in itertools.combinations(XYs, 2):
        ans = max(ans, d(points[0], points[1]))
    return ans


def solve(N, XYs):
    def transrate(XYs):
        return [(A[0] - A[1], A[0] + A[1]) for A in XYs]

    XYs = transrate(XYs)

    
    
    
    
    
    
    

    def candidates():
        return [
            
            
            
            
            
            
            
            
            max(XYs, key=lambda x: x[0]),
            min(XYs, key=lambda x: x[0]),
            max(XYs, key=lambda x: x[1]),
            min(XYs, key=lambda x: x[1]),
        ]

    XYs.sort(key=lambda p: p[0], reverse=True)
    xmax = XYs[0][0] - XYs[-1][0]
    XYs.sort(key=lambda p: p[1], reverse=True)
    ymax = XYs[0][1] - XYs[-1][1]
    return max(xmax, ymax)


























if __name__ == "__main__":
    N = int(input())
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]

    print(solve(N, XYs))

Solution (Python):
import sys
r=sys.stdin.readline
N=int(r())
def md(x,y,a,b):
    return abs(x-a)+abs(y-b)
left_top=(0,0)
left_down=(0,0)
right_top=(0,0)
right_down=(0,0)
for i in range(N):
    x,y = map(int,r().split())
    if i==0:
        left_top=(x,y)
        left_down=(x,y)
        right_top=(x,y)
        right_down=(x,y)
    else:
        if md(0,0,left_down[0],left_down[1])>md(0,0,x,y):
            left_down=(x,y)
        if md(0,0,right_top[0],right_top[1])<md(0,0,x,y):
            right_top=(x,y)
        if right_down[0]-right_down[1]<x-y:
            right_down=(x,y)
        if left_top[1]-left_top[0]<y-x:
            left_top=(x,y)
a=md(left_down[0],left_down[1],right_top[0],right_top[1])
b=md(left_top[0],left_top[1],right_down[0],right_down[1])
print(max([a,b]))

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

p1 = list(map(int,input().split()))
p2 = copy.copy(p1)
p3 = copy.copy(p1)
p4 = copy.copy(p1)

for i in range(n-1):

    p = list(map(int,input().split()))
    if p1[0]+p1[1] > p[0]+p[1]:
        p1 = copy.copy(p)

    if p4[0]+p4[1] < p[0]+p[1]:
        p4 = copy.copy(p)

    if p2[0]-p2[1] < p[0]-p[1]:
        p2 = copy.copy(p)

    if -p3[0]+p3[1] < -p[0]+p[1]:
        p3 = copy.copy(p)

print(max(p4[0]-p1[0]+p4[1]-p1[1], p2[0]-p3[0]+p3[1]-p2[1]))

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    amax = [0, 0]
    amin = [10**20, 10**20]
    for _ in range(n):
        x, y = na()
        amin[0] = min(amin[0], x+y)
        amax[0] = max(amax[0], x+y)
        amin[1] = min(amin[1], -x+y)
        amax[1] = max(amax[1], -x+y)
    print(max(amax[0]-amin[0], amax[1]-amin[1]))
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
data = []
for i in range(n):
	x,y = readInts()
	data.append([x+y,x,y,x-y])
ans = 0
data.sort(key=lambda x:x[0])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[1])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[2])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[3])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
print(ans)

Solution (Python):
def f(x, y):
    return x-y, x+y


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

max_x = -2000000000
min_x = 2000000000
max_y = -2000000000
min_y = 2000000000
for xi, yi in p:
    f1, f2 = f(xi, yi)
    max_x = max(max_x, f1)
    min_x = min(min_x, f1)
    max_y = max(max_y, f2)
    min_y = min(min_y, f2)

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

Solution (Python):
Row=int(input())
X=[]
Y=[]
for i in range(Row):
    n,a=input().split()
    X.append(int(n))
    Y.append(int(a))
A=[]
B=[]
for i in range(len(X)):
    A.append(X[i]-Y[i])
    B.append(X[i]+Y[i])
maxmax1=A[0]
maxmax2=B[0]
minmin1=A[0]
minmin2=B[0]
for i in range(len(A)):
    maxmax1=max(maxmax1,A[i])
    minmin1=min(minmin1,A[i])
for i in range(len(B)):
    maxmax2=max(maxmax2,B[i])
    minmin2=min(minmin2,B[i])
print(max((maxmax1-minmin1),(maxmax2-minmin2)))

Solution (Python):
from itertools import combinations


def main():
    N = int(input())

    max_x = (float("-inf"), 0)
    min_x = (float("inf"), 0)

    max_y = (0, float("-inf"))
    min_y = (0, float("inf"))

    max_xy = (float("-inf"), 0)
    min_xy = (float("inf"), 0)

    max_yx = (0, float("-inf"))
    min_yx = (0, float("inf"))

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

        if x > max_x[0]:
            max_x = (x, y)
        if x < min_x[0]:
            min_x = (x, y)
        if y > max_y[1]:
            max_y = (x, y)
        if y < min_y[1]:
            min_y = (x, y)
        if x + y > max_xy[0] + max_xy[1]:
            max_xy = (x, y)
        if x + y < min_xy[0] + min_xy[1]:
            min_xy = (x, y)
        if y - x > max_yx[1] - max_yx[0]:
            max_yx = (x, y)
        if y - x < min_yx[1] - min_yx[0]:
            min_yx = (x, y)

    ans = 0
    for a, b in combinations(
        (max_x, min_x, max_y, min_y, max_xy, min_xy, max_yx, min_yx), 2):
        ans = max(ans, abs(a[0] - b[0]) + abs(a[1] - b[1]))

    print(ans)


main()

Solution (Python):
N = int(input())
plus = []
minus = []
for i in range(N):
    x,y = map(int,input().split())
    plus.append(x+y)
    minus.append(x-y)
plus.sort()
minus.sort()

ans_1 = plus[-1]-plus[0]
ans_2 = abs(minus[-1]-minus[0])
print(max(ans_1,ans_2))

Solution (Python):
N = int(input())
v = [list(map(int, input().split())) for i in range(N)]
minx = min([v[i][0] for i in range(N)])
miny = min([v[i][1] for i in range(N)])
v.sort(key = lambda x:x[0] - minx + x[1] - miny)
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
result = d
v.sort(key = lambda x:x[0] - minx - (x[1] - miny))
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(max(d, result))

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

Solution (Python):
from operator import itemgetter

def sm(lis):
    return (lis[0]*2 + lis[1]**2)**0.5


def main():
    n = int(input())
    XY = [list(map(int,input().split())) for _ in range(n)]
    ans = 0
    a = [0,0]
    b = [0,0]
    c = [0,0]
    d = [0,0]
    y1 = 0
    y2 = 0
    x1 = 0
    x2 = 0
    for x,y in XY:
        if x >= x1:
            x1 = x
        if x <= x2:
            x2 = x
        if y >= y1:
            y1 = y
        if y <= y2:
            y2 = y
    a = [x1,y1]
    b = [x2,y1]
    c = [x2,y2]
    d = [x1,y2]
    Ans = []

            


    XY.sort(key = lambda xy:abs(xy[0] - a[0]) + abs(xy[1] - a[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])
    XY.sort(key = lambda xy:abs(xy[0] - b[0]) + abs(xy[1] - b[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    XY.sort(key = lambda xy:abs(xy[0] - c[0]) + abs(xy[1] - c[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    XY.sort(key = lambda xy:abs(xy[0] - d[0]) + abs(xy[1] - d[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    for x,y in Ans:
        for xx,yy in Ans:
            ans  = max(abs(x - xx) + abs(y - yy),ans)
    print(ans)
    return

if __name__ == "__main__":
    main()

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

ans = 0
tmp_M0 = -float("inf")
tmp_m0 = float("inf")
tmp_M1 = -float("inf")
tmp_m1 = float("inf")
for i in range(N):
    x,y =map(int, input().split())
    if x-y > tmp_M0:
        tmp_M0 = x-y
    if x-y < tmp_m0:
        tmp_m0 = x-y
    if x+y > tmp_M1:
        tmp_M1 = x+y
    if x+y < tmp_m1:
        tmp_m1 = x+y
    
    if max(tmp_M0-tmp_m0, tmp_M1-tmp_m1) > ans:
        ans = max(tmp_M0-tmp_m0, tmp_M1-tmp_m1)
        
print(ans)

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

z = [0]*n
w = [0]*n

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

a = max(z)
b = min(z)
c = max(w)
d = min(w)

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

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]


N = int(input())

X, Y = [], []
for i in range(N):
    x, y = li()
    X.append(x)
    Y.append(y)


def maxAbsValExpr(arr1, arr2):
    maxVal = 0
    for x, y in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
        distances = [x * arr1[i] + y * arr2[i] for i in range(len(arr1))]
        maxVal = max(maxVal, max(distances) - min(distances))
    return maxVal

ans = maxAbsValExpr(X, Y)
print(ans)

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

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y

    if x+y > summax:
        summax = x+y
    if x+y < summin:
        summin = x+y
    if x-y > diffmax:
        diffmax = x-y
    if x-y < diffmin:
        diffmin = x-y

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)

Solution (Python):

import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    Z = []
    W = []
    for _ in range(n):
        x, y = map(int, input().split())
        z = x + y
        w = x - y
        Z.append(z)
        W.append(w)
    Z.sort()
    W.sort()
    print(max(abs(Z[0] - Z[-1]), abs(W[0] - W[-1])))



if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, *xy = map(int, open(0).read().split())
    f = [(i - j, i + j) for i, j in zip(xy[::2], xy[1::2])]

    a = max(x[0] for x in f)
    b = min(x[0] for x in f)

    c = max(x[1] for x in f)
    d = min(x[1] for x in f)

    ans = max(a - b, c - d)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = []
b = []

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

aa = max(a)-min(a)
bb = max(b)-min(b)

if aa >= bb:
    print(aa)
else:
    print(bb)

Solution (Python):
n = int(input())
p = []
m = []

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

mnp = min(p)
mxp = max(p)
mnm = min(m)
mxm = max(m)

res = [mxp-mnp, mxm-mnm, mnm, mxm, mnp-mxp]
print(max(res))

Solution (Python):
from collections import deque
N=int(input())

L1=[0 for _ in range(N)]
L2=[0 for _ in range(N)]
for i in range(N):
    x,y=map(int,input().split())
    L1[i],L2[i]=x-y,x+y


mi1=min(L1)
ma1=max(L1)
mi2=min(L2)
ma2=max(L2)

ans=max(ma1-mi1,ma2-mi2)
print(ans)

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

max1 = -1 * (10 ** 10)
min1 = 10 ** 10
max0 = -1 * (10 ** 10)
min0 = 10 ** 10

for i in range(n):
    x,y = list(map(int,input().split()))
    k0 = x - y
    k1 = x + y
    if k0 > max0:
        max0 = k0
    if k0 < min0:
        min0 = k0
    if k1 > max1:
        max1 = k1
    if k1 < min1:
        min1 = k1


ans = int(max(max1-min1,max0-min0))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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




minX, maxX = min(xs), max(xs)
minY, maxY = min(ys), max(ys)



ans = 0
for x, y in zip(xs, ys):
    cs = [abs(x-minX), abs(x-maxX), abs(y-minY), abs(y-maxY)]
    m = max(cs)
    if m > ans:
        ans = m

print(ans)

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

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

max_1 = -float('inf')
min_1 = float('inf')

max_2 = -float('inf')
min_2 = float('inf')

for a, b in lst:
    max_1 = max(max_1, a - b)
    min_1 = min(min_1, a - b)

    max_2 = max(max_2, a + b)
    min_2 = min(min_2, a + b)


ans = max(max_1 - min_1, max_2 - min_2)

print(ans)

Solution (Python):
def ii(): return int(input())


def mi(): return map(int, input().split())


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


n = ii()

ps = []

xmin = (1e9, 0)
xmax = (-1e9, 0)
ymin = (0, 1e9)
ymax = (0, -1e9)

for _ in range(n):
    x, y = mi()
    ps.append((x, y))

l1 = list(sorted(ps, key=lambda p: p[0] + p[1]))
l2 = list(sorted(ps, key=lambda p: p[0] - p[1]))


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


a1 = d(l1[0], l1[n-1])
a2 = d(l2[0], l2[n-1])

print(max(a1, a2))