Problem:


Score : 500 points

Problem Statement

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

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

Constraints

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

1 \leq x_i,y_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the answer.

Sample Input 1

3
1 1
2 4
3 2

Sample Output 1

4

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

Sample Input 2

2
1 1
1 1

Sample Output 2

0



Sample input:
3
1 1
2 4
3 2


Sample output:
4

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

def dist(A, B):
    return abs(A[0] - B[0]) + abs(A[1] - B[1])

XY = [tuple(map(int, input().split())) for _ in range(N)]
INF = -10**10

ans = 0
for O in [(INF, INF), (-INF, INF)]:
    S = XY[0]
    for xy in XY:
        if dist(O, S) < dist(O, xy):
            S = xy
    O = S
    for xy in XY:
        if dist(O, S) < dist(O, xy):
            S = xy
    ans = max(ans, dist(O, S))
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    Z = []; W = []
    for i in range(N):
        x, y = map(int, input().split())
        z = x + y
        w = x - y
        Z.append(z)
        W.append(w)
    ans = max(max(Z) - min(Z), max(W) - min(W))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

z=[]
w=[]

for i in pnt:
  z.append(i[0]+i[1])
  w.append(i[0]-i[1])
print(max(max(z)-min(z),max(w)-min(w)))

Submission status: Accepted

Solution code:
N = int(input())

def dist(A, B):
    return abs(A[0] - B[0]) + abs(A[1] - B[1])

XY = [tuple(map(int, input().split())) for _ in range(N)]
INF = -10**10

ans = 0
for O in [(INF, INF), (-INF, INF), (INF, -INF), (-INF, -INF)]:
    S = XY[0]
    for xy in XY:
        if dist(O, S) < dist(O, xy):
            S = xy
    O = S
    for xy in XY:
        if dist(O, S) < dist(O, xy):
            S = xy
    ans = max(ans, dist(O, S))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    xy = [list(map(int, rl().split())) for _ in range(N)]
    
    a = [xi + yi for xi, yi in xy]
    a.sort()
    b = [xi - yi for xi, yi in xy]
    b.sort()
    ans = max(a[-1] - a[0], b[-1] - b[0])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

a.sort()
b.sort()

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

Submission status: Accepted

Solution code:
n = int(input())
s = []

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

t = sorted(s)
u = sorted(s, key=lambda x: x[1])
res = 0

tmp1 = t[-1][0] - t[0][0]
tmp2 = u[-1][1] - u[0][1]

print(max(tmp1, tmp2))

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
cheby = []
for i in range(n):
    l = [xy[i][0]-xy[i][1],xy[i][0]+xy[i][1]]
    cheby.append(l)

xmax = -10**10
xmin = 10**10
ymax = -10**10
ymin = 10**10
for i in range(n):
    if cheby[i][0] > xmax :
        xmax = cheby[i][0]
        xa = i
    if cheby[i][0] < xmin :
        xmin = cheby[i][0]
        xi = i
    if cheby[i][1] > ymax :
        ymax = cheby[i][1]
        ya = i
    if cheby[i][1] < ymin :
        ymin = cheby[i][1]
        yi = i

if abs(xmax-xmin) > abs(ymax-ymin):
    print(abs(xy[xa][0]-xy[xi][0])+abs(xy[xa][1]-xy[xi][1]))
else :
    print(abs(xy[ya][0]-xy[yi][0])+abs(xy[ya][1]-xy[yi][1]))

Submission status: Accepted

Solution code:
n=int(input())
z_max,z_min=-10**10,10**10
w_max,w_min=-10**10,10**10
for i in range(n):
    a,b=map(int,input().split())
    z=a+b
    w=a-b
    z_max=max(z_max,z)
    z_min=min(z_min,z)
    w_max=max(w_max,w)
    w_min=min(w_min,w)
print(max(z_max-z_min,w_max-w_min))

Submission status: Accepted

Solution code:
from sys import *
N = int(stdin.readline())
a,b = [],[]
for i in range(N):
    tmp = list(map(int, stdin.readline().split()))
    a.append(tmp[0] + tmp[1])
    b.append(tmp[0] - tmp[1])

a.sort()
b.sort()
print(max(a[-1]-a[0], b[-1]-b[0]))

Submission status: Accepted

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

def main():
    n = int(input())
    plus = []
    minus = []
    for _ in range(n):
        x, y = map(int, input().split())
        plus.append(x + y)
        minus.append(x - y)
    plus.sort()
    minus.sort()
    ans = max(plus[-1] - plus[0], minus[-1] - minus[0])
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
# Fast IO (be careful about bytestring, not on interactive)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())

sumList = []
subList = []

for _ in range(N):
    x,y = map(int,input().split())
    sumList.append(x + y)
    subList.append(x - y)

print(max(max(sumList) - min(sumList),max(subList) - min(subList)))

Submission status: Accepted

Solution code:
N = int(input())
xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
U = [x + y for x, y in zip(xs, ys)]
V = [x - y for x, y in zip(xs, ys)]
ans = max([max(U) - min(U), max(V) - min(V)])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# マンハッタン距離
plus = []
minus = []
for _ in range(N):
    x, y = map(int, input().split())
    plus.append(x + y)
    minus.append(x - y)

print(max(max(plus) - min(plus), max(minus) - min(minus)))

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())


def main():
    N = i_input()
    x, y = i_map()
    z = x + y
    w = x - y
    z_max = z
    z_min = z
    w_max = w
    w_min = w
    for i in range(1, N):
        x, y = i_map()
        z = x + y
        w = x - y
        z_max = max(z_max, z)
        z_min = min(z_min, z)
        w_max = max(w_max, w)
        w_min = min(w_min, w)
    ans = max([z_max - z_min, w_max - w_min])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
a,b,c,d=0,1e10,-1e10,1e10
for i in range(N):
  A,B=input().split()
  A=int(A)
  B=int(B)
  a=max(a,A+B)
  b=min(b,A+B)
  c=max(c,A-B)
  d=min(d,A-B)
print(max(abs(a-b),abs(c-d)))

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())


def main():
    N = i_input()
    Z = []
    W = []
    for i in range(1, N + 1):
        x, y = i_map()
        Z.append(x + y)
        W.append(x - y)
    Z.sort()
    W.sort()
    ans = max([Z[-1] - Z[0], W[-1] - W[0]])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
# マンハッタン距離
# 45度回転
z = []
w = []
for i in range(n):
    x, y = map(int, input().split())
    z.append(x + y)
    w.append(x - y)
z.sort()
w.sort()
print(max(z[-1]-z[0], w[-1]-w[0]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
XY = []
for i in range(N):
  XY.append([int(i) for i in input().split()])

XY = np.array(XY)
X = XY[:,0]
Y = XY[:,1]
pxpy = X + Y
pxmy = X - Y
mxpy =-X + Y
mxmy =-X - Y

candi = [np.argmax(pxpy),np.argmax(pxmy),np.argmax(mxpy),np.argmax(mxmy)]

cand = [XY[candi[i]] for i in range(4)]
manh = [abs(cand[0][0] - cand[3][0]) + abs(cand[0][1] - cand[3][1]), abs(cand[1][0] - cand[2][0]) + abs(cand[1][1] - cand[2][1])]
print(max(manh))

Submission status: Accepted

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

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


def get_max_manhattan_distanse(xs, ys):
    X = [xs[i] + ys[i] for i in range(len(xs))]
    Y = [xs[i] - ys[i] for i in range(len(xs))]
    # return max(max(X) - min(X), max(Y) - min(Y))
    X.sort()
    Y.sort()
    return max(X[-1] - X[0], Y[-1] - Y[0])

ans = get_max_manhattan_distanse(xs, ys)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

#https://img.atcoder.jp/abc178/editorial-E-phcdiydzyqa.pdf

z_list = list()
w_list = list()

for i in range(N):
    x,y = map(int, input().split())
    z_list.append(x + y)
    w_list.append(x - y)
    
print(max(max(z_list)-min(z_list),max(w_list)-min(w_list)))

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n = int(ipt())
    x,y = map(int,ipt().split())
    mas = [x+y,x-y,-x-y,y-x]
    ma = 0
    for _ in range(n-1):
        x,y = map(int,ipt().split())
        cpr = [-y-x,y-x,x+y,x-y]
        for i in range(4):
            if mas[i]+cpr[i] > ma:
                ma = mas[i]+cpr[i]
        for i in range(4):
            if mas[i] < cpr[i-2]:
                mas[i] = cpr[i-2]

    print(ma)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
A = [x + y for x, y in zip(xs, ys)]
B = [x - y for x, y in zip(xs, ys)]
ans = max([max(A) - min(A), max(B) - min(B)])
print(ans)

Submission status: Accepted

Solution code:
def e_dist_max():
    N = int(input())
    Pos_z, Pos_w = [], []  # editorial に準ずる
    for _ in range(N):
        x, y = [int(i) for i in input().split()]
        Pos_z.append(x + y)
        Pos_w.append(x - y)
    Pos_z.sort()
    Pos_w.sort()
    return max(Pos_z[-1] - Pos_z[0], Pos_w[-1] - Pos_w[0])

print(e_dist_max())

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
ma1, mi1 = -10000000000, 10000000000
ma2, mi2 = -10000000000, 10000000000
for i in range(n):
    x, y = map(int, input().split())
    ma1 = max(ma1, x - y)
    mi1 = min(mi1, x - y)
    ma2 = max(ma2, x + y)
    mi2 = min(mi2, x + y)
    ans = max(ans, ma1 - mi1, ma2 - mi2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
u = [list(map(int, input().split())) for i in range(n)]
z = [u[i][0] + u[i][1] for i in range(n)]
w = [u[i][0] - u[i][1] for i in range(n)]
d = [max(z)-min(z), max(w)-min(w)]

print(max(d))

Submission status: Accepted

Solution code:
N=int(input())

L=[]
# xでソート
#でソート
#min, max


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

L=sorted(L)
ans=abs(L[0][0]-L[-1][0])
L=sorted(L, key=lambda x: x[1])
ans=max(ans, abs(L[0][1]-L[-1][1]))

print(ans)

Submission status: Accepted

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

fn=[lambda x:x[0]+x[1],lambda x:x[0]-x[1]]
ans=0
for f in fn:
    xy.sort(key = f)
    ans=max(ans,abs(f(xy[0])-f(xy[-1])))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    z_max = 0
    z_min = 2 * 10 **9

    w_max = - 10 ** 9
    w_min = 10 ** 9

    for i in range(N):
        z = xy[i][0] + xy[i][1]
        w = xy[i][0] - xy[i][1]
        z_max = max(z_max,z)
        z_min = min(z_min,z)
        w_max = max(w_max,w)
        w_min = min(w_min,w)

    res = max(z_max-z_min,w_max-w_min)

    print(res)



main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math,bisect
sys.setrecursionlimit(10 ** 5)
from collections import defaultdict
from itertools import groupby,accumulate
from heapq import heapify,heappop,heappush
from collections import deque,Counter,OrderedDict
def I(): return int(sys.stdin.readline())
def neo(): return map(int, sys.stdin.readline().split())
def Neo(): return list(map(int, sys.stdin.readline().split()))
n = I()
A,B = [],[]
for i in range(n):
    a,b = neo()
    A += [a+b]
    B += [a-b]
A.sort()
B.sort()
Ans = max(A[-1]-A[0],B[-1]-B[0])
print(Ans)

Submission status: Accepted

Solution code:
import random

N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
  x[i], y[i] = map(int, input().split())

minn = 10**10
maxn = -10**10
minp = 10**10
maxp = -10**10

for i in range(N):
  minn = min(minn, x[i]-y[i])
  maxn = max(maxn, x[i]-y[i])
  minp = min(minp, x[i]+y[i])
  maxp = max(maxp, x[i]+y[i])

print(max(maxn-minn, maxp-minp))

Submission status: Accepted

Solution code:
N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
z = []; w = []
for x, y in xy:
    z.append(x + y)
    w.append(x - y)

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

Submission status: Accepted

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

a.sort()
b.sort()
ans = max(a[-1]-a[0],b[-1]-b[0])
print(ans)

Submission status: Accepted

Solution code:
def get_ints():
  return list(map(int,input().split()))

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

a.sort()
b.sort()
ans = max(a[-1]-a[0], b[-1]-b[0])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
Z = sorted([x+y for x,y in A])
W = sorted([x-y for x,y in A])

print(max(Z[-1]-Z[0], W[-1]-W[0]))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    P = []
    M = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append(x + y)
        M.append(x - y)
    P.sort()
    M.sort()
    ans = max(P[-1] - P[0], M[-1] - M[0])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
zmi=10**10
zma=-10**10
wmi=10**10
wma=-10**10
for x,y in xy:
    zmi=min(zmi,x+y)
    zma=max(zma,x+y)
    wmi=min(wmi,x-y)
    wma=max(wma,x-y)
print(max(zma-zmi,wma-wmi))

Submission status: Accepted

Solution code:
n=int(input())

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

xpy=[]
xmy=[]

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

xpy.sort()
xmy.sort()

print(max(abs(xpy[-1]-xpy[0]),abs(xmy[-1]-xmy[0])))

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
p=[a+b for a,b in l]
q=[a-b for a,b in l]
p.sort()
q.sort()
print(max(p[-1]-p[0],q[-1]-q[0]))

Submission status: Accepted

Solution code:
n = int (input())

xy = []

def dist(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
    
for i in range(n):
    x, y = map(int,input().split())
    xy.append([x+y, x-y])

xy.sort(key = lambda x: x[0])

min_z = xy[0][0]
max_z = xy[-1][0]

xy.sort(key = lambda x: x[1])

min_w = xy[0][1]
max_w = xy[-1][1]

print(max(abs(min_z - max_z), abs(min_w - max_w)))

Submission status: Accepted

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

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

z.sort()
w.sort()

print(max(z[n-1]-z[0],w[n-1]-w[0]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading



threading.stack_size(10**8)
sys.setrecursionlimit(300000)

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

#-------------------game starts now-----------------------------------------------------
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(mi,mi1,m,m1)
print(max(m-mi,m1-mi1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
i = 0
a_max = 2
a_min = 2*(10**9)
s_max = 1-10**9
s_min = 10**9-1

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    
    if sub > s_max:
        s_max = sub
    if sub < s_min:
        s_min = sub

d_add = a_max - a_min
d_sub = s_max - s_min

#if d_add >= d_sub:
#    print(d_add)
#if d_add < d_sub:
#    print(d_sub)
print(max(d_add,d_sub))

Submission status: Accepted

Solution code:
n = int(input())
plus = []
minus = []

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

result = max(max(plus) - min(plus), max(minus) - min(minus))
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
MOD = 10**9 + 7
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic

N=rri()
A = rrmm(N)
X = []
Y = []
for x, y in A:
    X.append(x-y)
    Y.append(x+y)
#print X
#print Y

xlo, xhi = min(X), max(X)
ylo, yhi = min(Y), max(Y)

print(max(yhi-ylo, xhi-xlo))

Submission status: Accepted

Solution code:
n = int(input())
z = [0 for _ in range(n)]
w = [0 for _ in range(n)]

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

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

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
z = [x + y for x, y in xy]
w = [x - y for x, y in xy]
print(max(max(z) - min(z), max(w) - min(w)))

Submission status: Accepted

Solution code:
n=int(input())
s,p=10**100,10**100
t,q=-1000000000000,-1000000000000

for i in range(n):
  x,y=map(int,input().split())
  s=min(s,x+y)
  t=max(t,x+y)
  p=min(p,x-y)
  q=max(q,x-y)
  
print(max(t-s,q-p))

Submission status: Accepted

Solution code:
N=int(input())
DMY=10**9

mmax=None
mmin=None
dmax=None
dmin=None
for i in range(N):
    x,y = map(int, input().split())
    if not mmax:
        mmax=(x,y,x+y)
        mmin=(x,y,x+y)
        dmax=(x,y,x+DMY-y)
        dmin=(x,y,x+DMY-y)
        continue
    if x+y > mmax[2]:
        mmax=(x,y,x+y)
    elif x+y < mmin[2]:
        mmin=(x,y,x+y)
    if x+DMY-y > dmax[2]:
        dmax=(x,y,x+DMY-y)
    elif x+DMY-y < dmin[2]:
        dmin=(x,y,x+DMY-y)

print(max(mmax[2]-mmin[2],dmax[2]-dmin[2]))

Submission status: Accepted

Solution code:
n = int(input())

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

p_arr = [0]*n
m_arr = [0]*n

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

p_dist = max(p_arr) - min(p_arr)
m_dist = max(m_arr) - min(m_arr)
dist_max = max(p_dist, m_dist)
  
  
print(dist_max)

Submission status: Accepted

Solution code:
n = int(input())

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

print(max(abs(max(xy_sum) - min(xy_sum)), abs(max(xy_dif) - min(xy_dif))))

Submission status: Accepted

Solution code:
z = []
w = []

for _ in range(int(input())):
    x, y = map(int, input().split())
    z.append(x + y)
    w.append(x - y)


z_max = max(z)
z_min = min(z)
w_max = max(w)
w_min = min(w)

print(max([abs(z_max - z_min), abs(w_max - w_min)]))

Submission status: Accepted

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

k = []
m = []
for i in l:
  a,b = i
  k.append(a+b)
  m.append(a-b)
k.sort()
m.sort()
print(max([k[-1]-k[0],m[-1] -m[0]]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
    if minlocal==hidarisita:
        hidarisita2=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
    if maxlocal==migiue:
        migiue2=maxlocal
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migisita=minlocal
    if minlocal==migisita:
        migisita2=minlocal
for i in range(0,n):#左上
    maxlocal=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
    if maxlocal==hidariue:
        hidariue2=maxlocal
aa=migiue-hidarisita
ab=migiue-hidarisita2
ba=migiue2-hidarisita
bb=migiue2-hidarisita2
cc=hidariue-migisita
cd=hidariue-migisita2
dc=hidariue2-migisita
dd=hidariue2-migisita2
print(max(aa,ab,ba,bb,cc,cd,dc,dd))

Submission status: Accepted

Solution code:
n = int(input())
u = []
v = []
ans = 0
for i in range(n):
    x, y = map(int, input().split())
    u.append(x+y)
    v.append(x-y)
ans = max(max(u) - min(u), max(v) - min(v))
print(ans)

Submission status: Accepted

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

tmp1 = []
tmp2 = []
for i in range(n):
    tmp1.append([xy[i][0]+xy[i][1], xy[i][0], xy[i][1]])
    tmp2.append([xy[i][0]-xy[i][1], xy[i][0], xy[i][1]])
tmp1.sort()
tmp2.sort()

ans = 0

if (tmp1[-1][2]-tmp1[0][2])*(tmp1[-1][1]-tmp1[0][1]) >= 0:
    tmp = tmp1[-1][0]-tmp1[0][0]
    ans = max(tmp, ans)
if (tmp2[-1][2]-tmp2[0][2])*(tmp2[-1][1]-tmp2[0][1]) <= 0:
    tmp = tmp2[-1][0]-tmp2[0][0]
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

tmp1 = []
tmp2 = []
for i in range(n):
    tmp1.append([xy[i][0]+xy[i][1], xy[i][0], xy[i][1]])
    tmp2.append([xy[i][0]-xy[i][1], xy[i][0], xy[i][1]])
tmp1.sort()
tmp2.sort()

if n <= 10:
    ii = n
    jj = n+1
else:
    ii = 10
    jj = 10

ans = 0
for i in range(ii):
    for j in range(1, jj):
        if (tmp1[-j][2]-tmp1[i][2])*(tmp1[-j][1]-tmp1[i][1]) >= 0:
            tmp = tmp1[-j][0]-tmp1[i][0]
            ans = max(tmp, ans)
        if (tmp2[-j][2]-tmp2[i][2])*(tmp2[-j][1]-tmp2[i][1]) <= 0:
            tmp = tmp2[-j][0]-tmp2[i][0]
            ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    
    z = []
    w = []

    for _ in range(n):
        x,y = tuple(map(int,input().split()))
        z.append(x+y)
        w.append(x-y)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

tmp1 = []
tmp2 = []
for i in range(n):
    tmp1.append([xy[i][0]+xy[i][1], xy[i][0], xy[i][1]])
    tmp2.append([xy[i][0]-xy[i][1], xy[i][0], xy[i][1]])
tmp1.sort()
tmp2.sort()

if n <= 1000:
    ii = n
    jj = n+1
else:
    ii = 1000
    jj = 1000

ans = 0
for i in range(ii):
    for j in range(1, jj):
        if (tmp1[-j][2]-tmp1[i][2])*(tmp1[-j][1]-tmp1[i][1]) >= 0:
            tmp = tmp1[-j][0]-tmp1[i][0]
            ans = max(tmp, ans)
        if (tmp2[-j][2]-tmp2[i][2])*(tmp2[-j][1]-tmp2[i][1]) <= 0:
            tmp = tmp2[-j][0]-tmp2[i][0]
            ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(xy):
    ans = 0
    pos = [xy[0] for _ in range(4)]

    for p in xy:
        if pos[0][0] + pos[0][1] < p[0] + p[1]:
            pos[0] = p
        if pos[1][0] + pos[1][1] > p[0] + p[1]:
            pos[1] = p
        if pos[2][0] - pos[2][1] < p[0] - p[1]:
            pos[2] = p
        if pos[3][0] - pos[3][1] > p[0] - p[1]:
            pos[3] = p

    return max(pos[0][0]+pos[0][1]-pos[1][0]-pos[1][1], pos[2][0]-pos[2][1]-pos[3][0]+pos[3][1])


if __name__ == "__main__":
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]
    print(solve(xy))

Submission status: Accepted

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

N = int(input())
points = [0] * N
rx = []
ry = []
for i in range(N):
    x, y = map(int, input().split())
    rx.append(x - y)
    ry.append(x + y)
print(max(max(rx) - min(rx), max(ry) - min(ry)))

Submission status: Accepted

Solution code:

N = int(input())

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

#f = [[0]*2 for i in range(N)]
X=[]
Y=[]
for i in range(N):
    #f[i][0] = x[i]-x[i]
    #f[i][1] = x[i]+y[i]
    X.append(x[i]-y[i])
    Y.append(x[i]+y[i])

dam1 = max(X) - min(X)
dam2 = max(Y) - min(Y)
print(max(dam1,dam2))

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x,y = [],[]
for i in range(n):
    a,b = ip()
    x.append(a+b)
    y.append(a-b)
print(max(max(x)-min(x),max(y)-min(y)))

Submission status: Accepted

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

z = []
w = []

for xy in xys:
    z.append(xy[0]+xy[1])
    w.append(xy[0]-xy[1])

#print(z)
#print(w)

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

Submission status: Accepted

Solution code:
n = int(input())
x = [None]*n
y = [None]*n

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


#y=x+k1 <=> x-y=-k1
k1 = [0]*n
#y=-x+k2 <=> x+y=k2
k2 = [0]*n
for i in range(n):
    k1[i] = -(x[i]-y[i])
    k2[i] = x[i]+y[i]

print(max(max(k1)-min(k1),max(k2)-min(k2)))

Submission status: Accepted

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