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:
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []



def main():
	N = i_input()

	x_y_list = []

	for i in range(0,N):
		tmpx,tmpy = i_map()
		x_y_list.append((tmpx,tmpy))

	z_list = []
	w_list = []
	for i in range(0,N):
		tmpz = x_y_list[i][0] + x_y_list[i][1]
		tmpw = x_y_list[i][0] - x_y_list[i][1]
		z_list.append(tmpz)
		w_list.append(tmpw)

	print(max(max(map(lambda x : (x),z_list))-min(map(lambda x: (x), z_list)),max(map(lambda x : (x),w_list))-min(map(lambda x: (x),w_list))))
	
	return


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
"""AtCoder Beginner Contest 178.

E
"""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


def calc(p1: list, p2: list) -> int:
    """Calc Manhattan Distance."""
    return abs(p2[1] - p1[1]) + abs(p2[0] - p1[0])


def main():
    """Run."""
    n = int(input())

    patterns = {
        'lt': (1, 1),
        'rt': (-1, 1),
        'lb': (-1, -1),
        'rb': (1, -1),
    }

    points: dict = {k: None for k in patterns.keys()}

    for _ in range(n):
        p = list(map(int, input().split(' ')))

        for k, (x, y) in patterns.items():
            max_p = points[k]

            if max_p:
                max_p_pos = (max_p[0] * x) + (max_p[1] * y)
                p_pos = (p[0] * x) + (p[1] * y)
                if max_p_pos < p_pos:
                    points[k] = p
            else:
                points[k] = p

    ans = 0
    for i, p1 in enumerate(points.values()):
        for p2 in list(points.values())[i + 1:]:
            ans = max(ans, calc(p1, p2))

    print(ans)


main()

Submission status: Accepted

Solution code:
N = int(input())

xpy = []
xmy = []


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

    xpy.append(x + y)
    xmy.append(x - y)

print(max(max(xpy) - min(xpy), max(xmy) - min(xmy)))

Submission status: Accepted

Solution code:
n=int(input())
zmi=wmi=int(1e+10)
zma=wma=int(-1e+10)
for i in range(n):
    xi,yi=map(int,input().split())
    zma=max(xi+yi,zma)
    wma=max(xi-yi,wma)
    zmi=min(xi+yi,zmi)
    wmi=min(xi-yi,wmi)
print(max(zma-zmi,wma-wmi))

Submission status: Accepted

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

add = sorted([x+y for x, y in xy])
sub = sorted([x-y for x, y in xy])

print(max(add[-1]-add[0], sub[-1]-sub[0]))

Submission status: Accepted

Solution code:
n = int(input())

plus,minus = [],[]
for i in range(n):
    a,b = map(int,input().split())
    plus.append(a+b)
    minus.append(a-b)

plus.sort()
minus.sort()

print(max(plus[-1]-plus[0],minus[-1]-minus[0]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
#from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *
from bisect import *	
#from heapq import *
#from math import ceil
#from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
mod=10**9+7
t=1
while t>0:
	t-=1
	n=fi()
	a=[]
	b=[]
	for i in range(n):
		x,y=mi()
		a.append(x+y)
		b.append(x-y)
	p=max(a)-min(a)
	q=max(b)-min(b)
	print(max(p,q))

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())
a, b = [], []

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

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

Submission status: Accepted

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

l.sort()
ll.sort()

print(max(l[-1]-l[0],ll[-1]-ll[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)
A = max(a)-min(a)
B = max(b)-min(b)
print(max(A,B))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
ans1 = max(x[0] + x[1] for x in d) - min(x[0] + x[1] for x in d)
ans2 = max(x[0] - x[1] for x in d) - min(x[0] - x[1] for x in d)
print(max(ans1, ans2))

Submission status: Accepted

Solution code:
N = int(input())

x, y = map(int, input().split())
mz = Mz = x + y
mw = Mw = x - y

for i in range(N-1):
    x, y = map(int, input().split())
    z = x + y
    w = x - y
    mz = min(mz, z)
    Mz = max(Mz, z)
    mw = min(mw, w)
    Mw = max(Mw, w)

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

Submission status: Accepted

Solution code:
n = int(input())

z = list()
w = list()

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

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

print(ans)

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())
a, b = [], []
for _ 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:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()	
	pp_min=mod*mod
	pp_max=0
	pm_max=-mod*mod
	mp_max=-mod*mod
	for _ in range(n):
		a, b = tin()
		pp_min = min(pp_min, a+b)
		pp_max = max(pp_max, a+b)
		pm_max = max(pm_max, a-b)
		mp_max = max(mp_max, -a + b)
	return max((pp_max - pp_min), (mp_max + pm_max))
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

umax = max(u)
umin = min(u)
vmax = max(v)
vmin = min(v)

print(max(umax-umin,vmax-vmin))

Submission status: Accepted

Solution code:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a = []
b = []
for i in range(n):
    x,y = rl()
    a.append(x+y)
    b.append(x-y)
a.sort()
b.sort()
print(max(a[-1]-a[0], b[-1]-b[0]))

Submission status: Accepted

Solution code:
n = int(input())
amx = -float("inf")
amn = float("inf")
bmx = -float("inf")
bmn = float("inf")
ans = -float("inf")
for i in range(n):
    a,b = map(int,input().split())
    amx = max(amx,a+b)
    amn = min(amn,a+b)
    bmx = max(bmx,a-b)
    bmn = min(bmn,a-b)
print(max(amx-amn,bmx-bmn))

Submission status: Accepted

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

za,wa=-10**10,-10**10
zi,wi=10**10,10**10
for i in range(N):
    z=arr[i][0]+arr[i][1]
    w=arr[i][0]-arr[i][1]
    
    za=max(z,za)
    zi=min(z,zi)
    
    wa=max(w,wa)
    wi=min(w,wi)

print(max(za-zi,wa-wi))

Submission status: Accepted

Solution code:
n, *XY = map(int, open(0).read().split())
XY = list(zip(XY[::2], XY[1::2]))
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)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]
A = [x+y for x, y in zip(X, Y)]
B = [x-y for x, y in zip(X, Y)]
print(max(max(A) - min(A), max(B) - min(B)))

Submission status: Accepted

Solution code:
n, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]
A = [x+y for x, y in zip(X, Y)]
B = [x-y for x, y in zip(X, Y)]
A.sort()
B.sort()
print(max(A[-1] - A[0], B[-1] - B[0]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    x, y = [], []
    for i in range(N):
        x_i, y_i = list(map(int, input().split()))
        x.append(x_i)
        y.append(y_i)

    return N, x, y


def main(N: int, x: list, y: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 点の数(2 <= N <= 2 * 10**5)
        x (list): x座標(1 <= x_i <= 10**9)
        y (list): y座標(1 <= y_i <= 10**9)
    """
    # 求解処理
    max_z = -sys.maxsize
    min_z = sys.maxsize
    max_w = -sys.maxsize
    min_w = sys.maxsize
    for x_i, y_i in zip(x, y):
        z_i = x_i + y_i
        max_z = max(max_z, z_i)
        min_z = min(min_z, z_i)
        w_i = x_i - y_i
        max_w = max(max_w, w_i)
        min_w = min(min_w, w_i)
    ans = max(max_z - min_z, max_w - min_w)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, x, y = get_input()

    # メイン処理
    main(N, x, y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys

# 標準入力を取得
N = int(input())
x, y = [], []
for i in range(N):
    x_i, y_i = list(map(int, input().split()))
    x.append(x_i)
    y.append(y_i)

# 求解処理
max_z = -sys.maxsize
min_z = sys.maxsize
max_w = -sys.maxsize
min_w = sys.maxsize
for x_i, y_i in zip(x, y):
    z_i = x_i + y_i
    max_z = max(max_z, z_i)
    min_z = min(min_z, z_i)
    w_i = x_i - y_i
    max_w = max(max_w, w_i)
    min_w = min(min_w, w_i)
ans = max(max_z - min_z, max_w - min_w)

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
N, *XY = map(int, open(0).read().split())

XY = [(x, y) for x, y in zip(*[iter(XY)] * 2)]
XY = list(set(XY))

Ax, Ay = max(XY, key=lambda t: t[0] + t[1])
Bx, By = max(XY, key=lambda t: -t[0] + t[1])
Cx, Cy = max(XY, key=lambda t: t[0] - t[1])
Dx, Dy = max(XY, key=lambda t: -t[0] - t[1])

print(max(
    max(abs(x - Ax) + abs(y - Ay),
        abs(x - Bx) + abs(y - By),
        abs(x - Cx) + abs(y - Cy),
        abs(x - Dx) + abs(y - Dy),
    ) for x, y in XY
))

Submission status: Accepted

Solution code:
N, *XY = map(int, open(0).read().split())

XY = [(x, y) for x, y in zip(*[iter(XY)] * 2)]
XY = list(set(XY))

Ax, Ay = max(XY, key=lambda t: t[0] + t[1])
Bx, By = max(XY, key=lambda t: -t[0] + t[1])
Cx, Cy = max(XY, key=lambda t: t[0] - t[1])
Dx, Dy = max(XY, key=lambda t: -t[0] - t[1])

ans = 0
for x, y in XY:
    ans = max(
        ans,
        abs(x - Ax) + abs(y - Ay),
        abs(x - Bx) + abs(y - By),
        abs(x - Cx) + abs(y - Cy),
        abs(x - Dx) + abs(y - Dy),
    )

print(ans)

Submission status: Accepted

Solution code:
#E_Manhattan
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())
arr = []
for i in range(n):
    x,y = list(map(int,input().split()))
    arr.append((x,y))
arr = sorted(arr)
ans = 0
pre = 1e10
for i in range(n):
    ans = max(ans, arr[i][0] + arr[i][1] - pre)
    pre = min(pre, arr[i][0] + arr[i][1])
pre = 1e10
for i in range(n):
    ans = max(ans, arr[i][0] - arr[i][1] - pre)
    pre = min(pre, arr[i][0] - arr[i][1])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
max_z = -np.Inf
min_z = np.inf
max_w = -np.Inf
min_w = np.inf
for _ in range(N):
    x, y = map(int, input().split())
    z = x + y
    w = x - y
    max_z = max(max_z, z)
    min_z = min(min_z, z)
    max_w = max(max_w, w)
    min_w = min(min_w, w)
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 = max(A)
b = min(A)
c = max(B)
d = min(B)

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

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from operator import sub

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    M = 10**9+1
    data = [[M, -M], [M, -M]]
    for x, y in zip(it, it):
        for i, x in enumerate([x+y, x-y]):
            for j, f in enumerate([min, max]):
                data[i][j] = f(data[i][j], x)

    print(max(map(lambda x: abs(sub(*x)), data)))



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    N = int(next(in_))
    xy = (tuple(map(int, line.split())) for line in itertools.islice(in_, N))
    zw = tuple((x + y, x - y) for x, y in xy)

    zmax = zmin = zw[0][0]
    wmax = wmin = zw[0][1]
    for z, w in zw[1:]:
        zmax = max(zmax, z)
        zmin = min(zmin, z)
        wmax = max(wmax, w)
        wmin = min(wmin, w)

    ans = max(zmax - zmin, wmax - wmin)
    
    return ans
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

p = np.zeros((N, 2))

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


X = np.array(X)
Y = np.array(Y)

p[:, 0] = X + Y
p[:, 1] = X - Y

xmin = np.argmin(p[:, 0])
xmax = np.argmax(p[:, 0])
ymin = np.argmin(p[:, 1])
ymax = np.argmax(p[:, 1])

ans = 0

for c in [xmin, xmax, ymin, ymax]:
    x, y = p[c]
    p_ = p.copy()
    p_[:, 0] -= x
    p_[:, 1] -= y
    p_m = np.max(p_, axis=1)
    ans = max(ans, np.max(p_m))
print(int(ans))

Submission status: Accepted

Solution code:
import sys

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    x = [0]*n
    y = [0]*n
    for i in range(n):
        x[i],y[i] = map(int,input().split())
    f0 = [0]*n
    f1 = [0]*n
    for i in range(n):
        f0[i],f1[i] = f(x[i],y[i])
    print(max(max(f0)-min(f0),max(f1)-min(f1)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
 
 
def f(x, y):
    return x - y, x + y
 
 
def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
    f0 = [0] * n
    f1 = [0] * n
    for i in range(n):
        f0[i], f1[i] = f(x[i], y[i])
    print(max(max(f0) - min(f0), max(f1) - min(f1)))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
m=[]
a=[-float("inf"), float("inf")]
b=[-float("inf"), float("inf")]
for _ in range(N):
    x, y = map(int, input().split())
    a[0] = max(a[0], x+y)
    a[1] = min(a[1], x+y)
    b[0] = max(b[0], x-y)
    b[1] = min(b[1], x-y)
print(max(abs(a[0]-a[1]), abs(b[0]-b[1])))

Submission status: Accepted

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

Submission status: Accepted

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

plus=[i[0]+i[1]for i in LIST]
minus=[i[0]-i[1]for i in LIST]

d_plus=max(plus)-min(plus)
d_minus=max(minus)-min(minus)

print(max(d_plus, d_minus))

Submission status: Accepted

Solution code:
n = int(input())
point = []
ans = -1
for i in range(n):
    point.append(list(map(int, input().split())))
x_sub_y = []
x_plus_y = []
for i in range(n):
    x_sub_y.append(point[i][0] - point[i][1])
    x_plus_y.append(point[i][0] + point[i][1])
x_sub_y.sort()
x_plus_y.sort()
ans = max(ans, x_sub_y[-1] - x_sub_y[0], x_plus_y[-1] - x_plus_y[0])
print(ans)

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

x, y = [0]*N, [0]*N

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

maxZ, minZ = x[0] + y[0], x[0] + y[0]
maxW, minW = x[0] - y[0], x[0] - y[0]
for i in range(N):
    z = x[i] + y[i]
    w = x[i] - y[i]

    maxZ = max(maxZ, z)
    minZ = min(minZ, z)
    maxW = max(maxW, w)
    minW = min(minW, w)

ans = max(maxZ-minZ, maxW-minW)
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    d = []
    e = []
    for k in range(N):
        x, y = map(int,input().split())
        d.append(x+y)
        e.append(x-y)
    d.sort()
    e.sort()
    print(max(e[-1]-e[0],d[-1]-d[0]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

l.sort()
z.sort()
w.sort()

ans = max(z[-1]-z[0],w[-1]-w[0])

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
x=[0]*N
for i in range(N):
    x[i]=list(map(int,input().split()))
#print(x)
z=[0]*N
w=[0]*N

for i in range(N):
    z[i]=x[i][0]+x[i][1]
    w[i]=x[i][0]-x[i][1]

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

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)
print(max(max(plus)-min(plus),max(minus)-min(minus)))

Submission status: Accepted

Solution code:
n = int(input())

x_plus_y = []
x_minus_y = []

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

x_plus_y.sort()
x_minus_y.sort()

print(max(x_plus_y[-1] - x_plus_y[0], x_minus_y[-1] - x_minus_y[0]))

Submission status: Accepted

Solution code:
import math
N = int(input())

s1 = []
s2 = []
#visited
for i in range(N):
    x, y = map(int, input().split())
    d0 = x + y
    d1 = x - y
    #if d0 in s1 and d1 in s2 and s1.index(d0) == s2.index(d1):
    #    continue
    s1.append(d0)
    s2.append(d1)


ans = 0

if len(s1) > 1 and len(s2) > 1:
    s1s = sorted(s1)
    s2s = sorted(s2)

    ans = max(s1s[0] - s1s[-1], s2s[0] - s2s[-1]
              , s1s[-1] - s1s[0], s2s[-1] - s2s[0])

print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
inf = float('inf')

M1, M2 = -inf, -inf
m1, m2 = inf, inf

for i in range(n):
  x, y = map(int, input().split())
  d1 = x+y
  d2 = x-y
  M1 = max(M1, d1)
  m1 = min(m1, d1)
  M2 = max(M2, d2)
  m2 = min(m2, d2)

D1 = M1-m1
D2 = M2-m2

print(max(D1, D2))

Submission status: Accepted

Solution code:
def seekDistance(n,nodes):
    max_z,min_z = searchMaxAndMinZ(n,nodes)
    max_w,min_w = searchMaxAndMinW(n,nodes)
    return max(max_z-min_z,max_w-min_w)

def searchMaxAndMinZ(n,nodes):
    max_z = -1
    min_z = 2 * 10 ** 9
    for i in range(n):
        curr_z = nodes[i][0] + nodes[i][1]
        if(curr_z > max_z):
            max_z = curr_z
        if(curr_z < min_z):
            min_z = curr_z
    return max_z,min_z

def searchMaxAndMinW(n,nodes):
    max_w = -10**9
    min_w = 2 * 10 ** 9
    for i in range(n):
        curr_w = nodes[i][0] - nodes[i][1]
        if (curr_w > max_w):
            max_w = curr_w
        if (curr_w < min_w):
            min_w = curr_w
    return max_w, min_w

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

Submission status: Accepted

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

Submission status: Accepted

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

xy.sort(key=lambda x: x[0] + x[1])
mn1, mx1 = xy[0], xy[-1]
xy.sort(key=lambda x: x[0] - x[1])
mn2, mx2 = xy[0], xy[-1]

li = [mn1, mx1, mn2, mx2]
ans = 0
for x1, y1 in li:
    for x2, y2 in li:
        dist = abs(x1 - x2) + abs(y1 - y2)
        ans = max(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.buffer.readline())
z, w = [0]*n, [0]*n
for a, i in zip(sys.stdin.buffer.readlines(), range(n)):
    x, y = map(int, a.split())
    z[i] = x+y
    w[i] = x-y
print(max(abs(max(z)-min(z)), abs(max(w)-min(w))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC178D Manhattan
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_ans = max(z)-min(z)
w_ans = max(w)-min(w)
print(max(z_ans,w_ans))

Submission status: Accepted

Solution code:
n=int(input())
rmax=-10**10
rmin=10**10
lmax=-10**10
lmin=10**10
for i in range(n):
    xi,yi=map(int,input().split())
    rmax=max(rmax,xi+yi)
    rmin=min(rmin,xi+yi)
    lmax=max(lmax,xi-yi)
    lmin=min(lmin,xi-yi)
    
print(max(rmax-rmin,lmax-lmin))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

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

    print(max(abs(max(arr1) - min(arr1)), abs(max(arr2) - min(arr2))))





if __name__ == '__main__':
    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_max = max(z)
z_min = min(z)
w_max = max(w)
w_min = min(w)

print(max(z_max-z_min,w_max-w_min))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

N = int(input())
V = set()
for s in sys.stdin.readlines():
    x, y = map(int, s.split())
    V.add((x + y, x - y))

y1 = max(V, key=itemgetter(1))[1]
y2 = min(V, key=itemgetter(1))[1]
x1 = max(V, key=itemgetter(0))[0]
x2 = min(V, key=itemgetter(0))[0]

print(max(abs(x1 - x2), abs(y1 - y2)))

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)

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 _ in range(N)]

def measure(originX,originY):
    origin = [originX,originY]
    XY.sort(key=lambda x: abs(x[0]-origin[0])+abs(x[1]-origin[1]))
    return abs(XY[-1][0]-origin[0])+abs(XY[-1][1]-origin[1])-(abs(XY[0][0]-origin[0])+abs(XY[0][1]-origin[1]))

ans = 0
ans = max(ans,measure(1,1))
ans = max(ans,measure(1,10**9))
print(ans)

Submission status: Accepted

Solution code:
"""
四隅に仮想の原点をつくり、各座標からその原点へのマンハッタン距離を計測する。
"""

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

def measure(originX,originY):
    origin = [originX,originY]
    XY.sort(key=lambda x: abs(x[0]-origin[0])+abs(x[1]-origin[1]))
    return abs(XY[-1][0]-origin[0])+abs(XY[-1][1]-origin[1])-(abs(XY[0][0]-origin[0])+abs(XY[0][1]-origin[1]))

ans = 0
ans = max(ans,measure(1,1))
ans = max(ans,measure(1,10**9))
ans = max(ans,measure(10**9,1))
ans = max(ans,measure(10**9,10**9))
print(ans)

Submission status: Accepted

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

n=int(input())

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

z_ans=max(z)-min(z)
w_ans=max(w)-min(w)
print(max(z_ans,w_ans))

Submission status: Accepted

Solution code:
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=abs(x-y)
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

#  t=abs(x+y)
  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))

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def solve02():
    n = int(input().strip())
    L = []
    Xmin, Ymin, Xmax, Ymax = (sys.maxsize, sys.maxsize, -100, -100)

    for i in range(n):
        a, b = map(int, input().strip().split())
        L.append((a, b))
        Xmin, Ymin, Xmax, Ymax = (min(Xmin, a), min(Ymin, b), max(Xmax, a), max(Ymax, b))
    A, B, C, D = ((Xmin, Ymax), (Xmin, Ymin), (Xmax, Ymin), (Xmax, Ymax))

    # 対角線ACについて
    d_MinDistFromA = sys.maxsize    # 点Aからの距離が最小であるような，その最小の距離の値を求める
    d_MinDistFromC = sys.maxsize    # 点Cからの距離が最小であるような，その最小の距離の値を求める
    # 対角線BDについて
    d_MinDistFromB = sys.maxsize    # 点Bからの距離が最小であるような，その最小の距離の値を求める
    d_MinDistFromD = sys.maxsize    # 点Dからの距離が最小であるような，その最小の距離の値を求める

    for a, b in L:
        d_MinDistFromA = min(d_MinDistFromA, abs(a - Xmin) + abs(b - Ymax))
        d_MinDistFromC = min(d_MinDistFromC, abs(a - Xmax) + abs(b - Ymin))
        d_MinDistFromB = min(d_MinDistFromB, abs(a - Xmin) + abs(b - Ymin))
        d_MinDistFromD = min(d_MinDistFromD, abs(a - Xmax) + abs(b - Ymax))

    # 出力
    ans1 = abs(A[0] - C[0]) + abs(A[1] - C[1]) - (d_MinDistFromA + d_MinDistFromC)
    ans2 = abs(B[0] - D[0]) + abs(B[1] - D[1]) - (d_MinDistFromB + d_MinDistFromD)
    print(max(ans1, ans2))


def main():
    solve02()


if __name__ == '__main__':
    main()