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())
xs = []
ys = []
for _ in range(N):
    x,y = map(int,input().split())
    xs.append(x)
    ys.append(y)
fxys = [[], []]
for i in range(N):
    x = xs[i]
    y = ys[i]
    fxys[0].append(x-y)
    fxys[1].append(x+y)
ls = []
for d in [0, 1]:
    mx = max(fxys[d])
    mi = min(fxys[d])
    ls.append(mx-mi)
print(max(ls))

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    qqqq = 0
    wwww = 1000000000000000000000000000
    a = []
    for i in range(n):
        x,y = invr()
        a.append((x,y))
        q = max(q,x + y)
        w = min(w,x + y)
        qq = max(qq,x - y)
        ww = min(ww,x - y)
        qqqq = max(qqqq,y - x)
        wwww = min(wwww,y - x)
    if len(set(a)) == 1:
        print(0)
    else:
        print(max(q - w,qq - ww,qqqq - wwww))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())


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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


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

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

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

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

    ans1 = max(Z) - min(Z)

    X_max = max(X)

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

    ans2 = max(Z) - min(Z)

    print(max(ans1, ans2))


main()

Submission status: Accepted

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


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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

dists1 = sorted(dists, key=lambda x: x[2])
dists2 = sorted(dists, key=lambda x: x[3])
# dists3 = sorted(dists, key=lambda x: x[4])
ans1 = abs(dists1[0][0] - dists1[-1][0]) + abs(dists1[0][1] - dists1[-1][1])
ans2 = abs(dists2[0][0] - dists2[-1][0]) + abs(dists2[0][1] - dists2[-1][1])

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
import math

n = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
## coding: UTF-8
N = int(input())
lxy = [list(map(int, input().split())) for _ in range(N)]


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

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

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

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

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

Submission status: Accepted

Solution code:

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

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

print(max(a,b))

Submission status: Accepted

Solution code:
from sys import stdin


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, x, y))

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

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())

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

f0=[]
f1=[]

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

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
ans=[]
cand=[xy[i][0]+xy[i][1] for i in range(n)]
#print(cand)
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]+xy[i][1]for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
print(max(ans))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n = int(readline())

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


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


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


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


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


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

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

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


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


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


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

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

main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

#############
# Main Code #
#############

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

# マンハッタン距離
# 分けて考える?
# NlogNまでいけそう

# 愚直?
# ソートして考える?

# リストして各点についてO(1)で答える
# xが小さい順にソート

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

Submission status: Accepted

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

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

Submission status: Accepted

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

class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

stdin = sys.stdin

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



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

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

Submission status: Accepted

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

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

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

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

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

print(max(d1,d2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def f(n, m):
  return(abs(n[0]-m[0]) + abs(n[1]-m[1]))

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]

ans = max(max(f0) - min(f0), max(f1) - min(f1))

print(ans)

Submission status: Accepted

Solution code:
#n,m=map(int,input().split())
#a=list(map(int,input()))
#s=input()
def main(n,xy):
  d=[x+y for x,y in xy]
  d.sort()
  ans=d[-1]-d[0]
  maxx=max([x for x,y in xy])
  dr=[(maxx-x)+y for x,y in xy]
  dr.sort()
  ans=max(ans,dr[-1]-dr[0])
  return ans
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
print(main(n,xy))

Submission status: Accepted

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

print(max(A[N-1]-A[0],abs(B[N-1]-B[0])))

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
arr2=[]
s=set()
for _ in range(n):
	x,y=map(int,input().split())
	if((x,y) not in s):
		arr.append(x+y)
		arr2.append(x-y)
		s.add((x,y))
arr.sort()
arr2.sort()
if(len(arr)==1):
	print(0)
else:
	ans=arr[-1]-arr[0]
	ans=max(ans,arr2[-1]-arr2[0])
	print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    Ps = [NLI() for _ in range(N)]
    Px = [x+y for x, y in Ps]
    Py = [x-y for x, y in Ps]
    print(max(max(Px) - min(Px), max(Py) - min(Py)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

from math import factorial as f

from math import ceil, floor, sqrt
import math

import bisect
import re
import heapq

from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

yes = "Yes"
no = "No"


def main():
    f = [[0,0] for i in range(200005)]
    n = ii()
    for i in range(n):
        x,y = mi()
        f[i][0] = x+y
        f[i][1] = x-y
    xmax,ymax,xmin,ymin = 0,-1000000000000000,100000000000000000,10000000000000000
    for i in range(n):
        xmax = max(xmax,f[i][0])
        xmin = min(xmin,f[i][0])
        ymax = max(ymax,f[i][1])
        ymin = min(ymin,f[i][1])

    xmax = max(xmax-xmin,ymax-ymin)

    print(xmax)





main()

Submission status: Accepted

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

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

xplusy = []
xminusy = []

for i in range (0, N):
	xplusy.append(A[i][0]+A[i][1])
	xminusy.append(A[i][0]-A[i][1])

print(max((max(xplusy)-min(xplusy)), (max(xminusy) - min(xminusy))))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
xy=[]
for _ in range(n):
    u,v=MI()
    xy.append((u+v,u-v))
xy.sort()
l=xy[0][0]
t=b=xy[0][1]
ans=0
for x,y in xy:
    ans=max(ans,x-l,t-y,y-b)
    t=max(t,y)
    b=min(b,y)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

minx=10**10
maxx=-10**10
miny=10**10
maxy=-10**10

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

    maxx=max(maxx,x+y)
    minx=min(minx,x+y)
    maxy=max(maxy,x-y)
    miny=min(miny,x-y)

print(max(maxx-minx,maxy-miny))

Submission status: Accepted

Solution code:
n=int(input())

class Point:
    def __init__(self,x,y):
        self.x=x
        self.y=y


points=[]

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

min_x=100000000000
max_x=-100000000000
min_y=100000000000
max_y=-100000000000

for point in points:
    if point.x<min_x:
        min_x=point.x
    if point.x>max_x:
        max_x=point.x
    if point.y<min_y:
        min_y=point.y
    if point.y>max_y:
        max_y=point.y

x_abs=max_x-min_x
y_abs=max_y-min_y
print(max(x_abs,y_abs))