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:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


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

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod)
    return numer * denom % mod


def solve():
    pass


def solve01():
    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))

    flag = 1
    for i in range(len(L) - 1):
        flag *= (L[i] == L[i + 1])
    if flag == 1:
        try:
            raise ValueError("error!")
        except ValueError as e:
            eprint(e)

    if Xmax == Xmin or Ymax == Ymin:
        try:
            raise ValueError("error!")
        except ValueError as e:
            eprint(e)

    # 対角線ACについて
    d_MinDistFromA = sys.maxsize    # 点Aからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromA = min(d_MinDistFromA, abs(a - Xmin) + abs(b - Ymax))

    d_MinDistFromC = sys.maxsize    # 点Cからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromC = min(d_MinDistFromC, abs(a - Xmax) + abs(b - Ymin))
    ans1 = abs(A[0] - C[0]) + abs(A[1] - C[1]) - (d_MinDistFromA + d_MinDistFromC)  #

    # 対角線BDについて
    d_MinDistFromB = sys.maxsize    # 点Bからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromB = min(d_MinDistFromB, abs(a - Xmin) + abs(b - Ymin))

    d_MinDistFromD = sys.maxsize    # 点Dからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromD = min(d_MinDistFromD, abs(a - Xmax) + abs(b - Ymax))
    ans2 = abs(B[0] - D[0]) + abs(B[1] - D[1]) - (d_MinDistFromB + d_MinDistFromD)

    # 出力
    # eprint('ans1,ans2 ', end=':\n')
    # eprint(ans1, ans2)
    print(max(ans1, ans2))


def solve00():
    n = int(input().strip())
    L = []
    Xmin = sys.maxsize
    Ymin = sys.maxsize
    Xmax = -100
    Ymax = -100
    for i in range(n):
        a, b = map(int, input().strip().split())
        L.append((a, b))
        Xmin = min(Xmin, a)
        Ymin = min(Ymin, b)
        Xmax = max(Xmax, b)
        Ymax = max(Ymax, b)

    A = (Xmin, Ymax)
    B = (Xmin, Ymin)
    C = (Xmax, Ymin)
    D = (Xmax, Ymax)

    # 対角線ACについて
    d_MinDistFromA = sys.maxsize    # 点Aからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromA = min(d_MinDistFromA, abs(a - Xmin) + abs(b - Ymax))

    d_MinDistFromC = sys.maxsize    # 点Cからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromC = min(d_MinDistFromC, abs(a - Xmax) + abs(b - Ymin))
    ans1 = abs(A[0] - C[0]) + abs(A[1] - C[1]) - (d_MinDistFromA + d_MinDistFromC)  #

    # 対角線BDについて
    d_MinDistFromB = sys.maxsize    # 点Bからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromB = min(d_MinDistFromB, abs(a - Xmin) + abs(b - Ymin))

    d_MinDistFromD = sys.maxsize    # 点Dからの距離が最小であるような，その最小の距離の値を求める
    for a, b in L:
        d_MinDistFromD = min(d_MinDistFromD, abs(a - Xmax) + abs(b - Ymax))
    ans2 = abs(B[0] - D[0]) + abs(B[1] - D[1]) - (d_MinDistFromB + d_MinDistFromD)

    # 出力
    # eprint('ans1,ans2 ', end=':\n')
    # eprint(ans1, ans2)
    print(max(ans1, ans2))


def main():
    solve01()


if __name__ == '__main__':
    main()

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()
print(max(a[-1] - a[0], b[-1] - b[0]))

Submission status: Accepted

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

Submission status: Accepted

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

min_diff = 10**9
max_diff = -10**9
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

print(max(max_sum-min_sum, max_diff-min_diff))

Submission status: Accepted

Solution code:
N = int(input())
a = - (10 ** 9 + 3)  # max(x + y)
b = 10 ** 9 + 3  # min(x + y)
c = - (10 ** 9 + 3)  # max(x - y)
d = 10 ** 9 + 3  # min(x - y)
for i in range(N):
    x, y = map(int, input().split())
    a = max(a, x + y)
    b = min(b, x + y)
    c = max(c, x - y)
    d = min(d, x - y)
ans = max([a - b, c - d])
print(ans)

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 = 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=int(input())
xy=[list(map(int,input().split()))for _ in range(N)]
xy1=[x+y for x,y in xy]
xy2=[-x+y for x,y in xy]
ans1=max(xy1)-min(xy1)
ans2=max(xy2)-min(xy2)
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = [LIST() for _ in range(N)]
zw = [[x+y, x-y] for x, y in xy]
z, w = zip(*zw)
print(max(max(z)-min(z), max(w)-min(w)))

Submission status: Accepted

Solution code:
n = int(input())
p_mn = m_mn= 10**9 * 2
p_mx = m_mx = -p_mn
for i in range(n):
    x, y = map(int, input().split())
    p = x + y
    m = x - y
    p_mx = max(p_mx, p)
    p_mn = min(p_mn, p)
    m_mx = max(m_mx, m)
    m_mn = min(m_mn, m)
print(max(p_mx-p_mn, m_mx-m_mn))

Submission status: Accepted

Solution code:
N = int(input())
XY = [[int(_) for _ in input().split()] for _ in range(N)]
ans = -1
for dx, dy in ((1, 1), (-1, 1), (-1, -1), (1, -1)):
    xy2 = sorted(x * dx + y * dy for x, y in XY)
    ans = max(ans, max(xy2) - min(xy2))
print(ans)

Submission status: Accepted

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

z = []
w = []

for i in range(N):
  z.append(p[i][0] + p[i][1])
  w.append(p[i][0] - p[i][1])

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

Submission status: Accepted

Solution code:
n = int(input())
Z = [0 for i in range(n)]
W = [0 for i in range(n)]
for i in range(n):
    xi, yi = map(int, input().split())
    Z[i] = xi + yi
    W[i] = xi - yi

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

Submission status: Accepted

Solution code:
n = int(input())

zmax = 0
zmin = 10**10
wmax = -10**10
wmin = 10**10

for i in range(n):
    x, y = map(int, input().split())
    zref = x + y
    wref = x - y
    zmax = max(zmax, zref)
    zmin = min(zmin, zref)
    wmax = max(wmax, wref)
    wmin = min(wmin, wref)

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

Submission status: Accepted

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

xy.sort()
lstm = []
lstp = []
for x, y in xy:
    lstm.append(x-y)
    lstp.append(x+y)
    
lstm.sort()
lstp.sort()
ans = max(lstm[-1] - lstm[0], lstp[-1] - lstp[0])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ph = 0
pl = 10**10
mh = -10**10
ml = 10**10
for _ in range(n):
  x,y = map(int,input().split())
  ph = max(ph,x+y)
  pl = min(pl,x+y)
  mh = max(mh,x-y)
  ml = min(ml,x-y)
print(max(ph-pl,mh-ml))

Submission status: Accepted

Solution code:
N=int(input())
minz=10**11
minw=10**11
maxz=-10**11
maxw=-10**11
for i in range(N):
 
    a,b=map(int,input().split())
    if  a+b>maxz:
        maxz=a+b

    if a+b<minz:
        minz=a+b

    if  a-b>maxw:
        maxw=a-b

    if a-b<minw:
        minw=a-b

    
 
print(max((maxz-minz),(maxw-minw)))

Submission status: Accepted

Solution code:
n = int(input())
maxx, minx, maxy, miny = -10**10, 10**10, -10**10, 10**10
for _ in range(n):
	x, y = map(int, input().split())
	x, y = x+y, x-y
	maxx = max(maxx, x)
	minx = min(minx, x)
	maxy = max(maxy, y)
	miny = min(miny, y)
print(max(maxx - minx, maxy - miny))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

ans = max(max(x_plus_y)-min(x_plus_y), max(x_minus_y)-min(x_minus_y))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
p1, p2, p3, p4 = [[10**9, 10**9], [0, 0], [0, 10**9], [10**9, 0]]
ans = 0
for i in range(N):
    x, y = map(int, input().split())
    if p1[0] + p1[1] >= x + y:
        p1 = [x, y]
    if p2[0] + p2[1] <= x + y:
        p2 = [x, y]
    if p3[0] - p3[1] <= x - y:
        p3 = [x, y]
    if p4[0] - p4[1] >= x - y:
        p4 = [x, y]
P = [p1, p2, p3, p4]
for x1, y1 in P:
    for x2, y2 in P:
        ans = max(ans, abs(x1-x2)+abs(y1-y2))
print(ans)

Submission status: Accepted

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


pu = []
mi = []
N = int(input())
for _ in range(N):
    x, y = LI()
    pu.append(x+y)
    mi.append(x-y)
P = max(pu)
p = min(pu)
M = max(mi)
m = min(mi)
print(max(P-p, M-m))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
t = int(input())
po = []
 
for _ in range(t):
  x,y = list(map(int,input().split()))
  po.append((x,y))
  
po.sort()
 
dp1 = [+(10**99) for _ in range(t)]
 
for i in range(t):
  x,y = po[i][0], po[i][1]
  value = x+y
  dp1[i] = min(dp1[i-1], value)
  
dp2 = [+(10**99) for _ in range(t)]
 
for i in range(t):
  x,y = po[i][0], po[i][1]
  value = x-y
  dp2[i] = min(dp2[i-1], value)
  
best = -9999999999999999999999999999
#print(dp)
 
for i in range(1,t):
  dist = po[i][0] + po[i][1] - dp1[i-1]
  best = max(best, dist)
  
  dist = po[i][0] - po[i][1] - dp2[i-1]
  best = max(best, dist)
  
print(best)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a_li , b_li = [] , []
  for _ in range(n):
    x , y = map(int,input().split())
    a_li.append(x + y)
    b_li.append(x - y)
  print(max(max(a_li) - min(a_li), max(b_li) - min(b_li)))
 
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N=int(input())

X=[0 for _ in range(N)]
Y=[0 for _ in range(N)]

INF=1e10
Zmax=-INF
Zmin=INF
Wmax=-INF
Wmin=INF


for n in range(N):
	X[n], Y[n] = map(int, input().split())
	z = X[n] + Y[n]
	w = X[n] - Y[n]

	Zmax = max( Zmax, z )
	Zmin = min( Zmin, z )
	Wmax = max( Wmax, w )
	Wmin = min( Wmin, w )

ans = max( abs(Zmax - Zmin), abs(Wmax - Wmin))

print(ans)

Submission status: Accepted

Solution code:
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_max = max(plus)
    plus_min = min(plus)
    minus_max = max(minus)
    minus_min = min(minus)

    print(max(plus_max - plus_min, minus_max - minus_min))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

s = []
l = []
top = 2*(10**9)+1
low = 0
for j in range(N):
    t = sum(M[j])
    if low == t:
        s.append(M[j])
    elif low < t:
        low = t
        s = []
        s.append(M[j])

    if top == t:
        l.append(M[j])
    elif top > t:
        top = t
        l = []
        l.append(M[j])


def cal_man(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


s.sort()
l.sort()


high = []
small = []
lowest = 2*(10**9)+1
topest = -2*(10**9)+1
for j in range(N):
    t = M[j][1] - M[j][0]
    if lowest > t:
        lowest = t
        small = []
        small.append(M[j])
    elif lowest == t:
        small.append(M[j])

    if topest < t:
        topest = t
        high = []
        high.append(M[j])
    elif topest == t:
        high.append(M[j])
high.sort()
small.sort()


print(max([cal_man(s[0], l[-1]), cal_man(s[-1], l[0]),
           cal_man(high[0], small[-1]), cal_man(high[-1], small[0])]))

Submission status: Accepted

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

    z_list = []
    w_list = []
    for i in range(N):
        x = p_list[i][0]
        y = p_list[i][1]
        z_list.append(x + y)
        w_list.append(x - y)
    ans = max(max(z_list) - min(z_list), max(w_list) - min(w_list))
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
xmax = -inf
xmin = inf
ymax = -inf
ymin = inf
for _ in range(N):
    a, b = map(int, input().split())
    x = a + b
    y = a - b
    xmax = max(xmax, x)
    xmin = min(xmin, x)
    ymax = max(ymax, y)
    ymin = min(ymin, y)

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())
u = [0]*n
v = [0]*n
for i in range(n):
    x, y = map(int, input().split())
    u[i] = x+y
    v[i] = x-y

ret = 0
ret = max(ret, max(u)-min(u))
ret = max(ret, max(v)-min(v))
print(ret)

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys


def resultSur97(x):
    return x % (1000000000 + 7)


if __name__ == '__main__':
    # ------ 入力 ------#
    # 1行入力
    n = int(input())    # 数字
    # a = input()     # 文字列
    # aList = list(map(int, input().split()))     # スペース区切り連続数字
    # aList = input().split()     # スペース区切り連続文字列
    # aList = [int(c) for c in input()]   # 数字→単数字リスト変換

    # 定数行入力
    x = n
    # aList = [int(input()) for _ in range(x)] # 数字
    # aList = [input() for _ in range(x)] # 文字
    aList = [list(map(int, input().split())) for _ in range(x)]     # スペース区切り連続数字(行列)
    # aList = [input().split() for _ in range(x)]     # スペース区切り連続文字
    # aList = [[int(c) for c in input()] for _ in range(x)]   # 数字→単数字リスト変換(行列)

    # スペース区切り連続 数字、文字列複合
    # aList = []
    # for _ in range(x):
    #     aa, bb = input().split()
    #     a.append((int(aa), bb))

    # ------ 処理 ------#
    zmin = aList[0][0] + aList[0][1]
    zmax = aList[0][0] + aList[0][1]
    wmin = aList[0][0] - aList[0][1]
    wmax = aList[0][0] - aList[0][1]

    for i in range(len(aList)):
        x = aList[i][0]
        y = aList[i][1]

        z = x + y
        w = x - y

        if z < zmin:
            zmin = z
        if z > zmax:
            zmax = z
        if w < wmin:
            wmin = w
        if w > wmax:
            wmax = w

    disMax = max(zmax-zmin, wmax-wmin)
    # ------ 出力 ------#
    print("{}".format(disMax))
    # if flg == 0:
    #     print("YES")
    # else:
    #     print("NO")

Submission status: Accepted

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
  XY[i] = [XY[i][0] - XY[i][1], XY[i][0] + XY[i][1]]
X = [XY[i][0] for i in range(N)]
Y = [XY[i][1] for i in range(N)]
X.sort()
Y.sort()
print(max(X[-1] - X[0], Y[-1] - Y[0]))

Submission status: Accepted

Solution code:
n = int(input())
zm = -2e10
zn = 30000000000
wm = -2e10
wn = 30000000000
while(n):
  x,y = map(int,input().split())
  zm = max(zm,x+y)
  zn = min(zn,x+y)
  wm = max(wm,x-y)
  wn = min(wn,x-y)
  n-=1
  
print(max(zm-zn,wm-wn))

Submission status: Accepted

Solution code:
n = int(input())

zmax = -10**10
zmin = 10**10
wmax = -10**10
wmin = 10**10

for i in range(n):
    x, y = map(int, input().split())
    zref = x + y
    wref = x - y
    zmax = max(zmax, zref)
    zmin = min(zmin, zref)
    wmax = max(wmax, wref)
    wmin = min(wmin, wref)

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

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)

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 = (list(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:
# cook your dish here
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(s, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if s[mid] == val:return mid
        elif s[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,s):
    for i in range(1,n):s[i]+=s[i-1]
    return s;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
#code here
n = int(input())
points=[]
D,d,S,s=-inf,inf,-inf,inf
for i in range(n):
    a,b=iia()
    D=max(D,a-b);d=min(d,a-b);S=max(S,a+b);s=min(s,a+b)
print(max(D-d,S-s))

Submission status: Accepted

Solution code:
import numpy as np
a = input()
N = int(a)

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

z = x + y
w = x - y

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

Submission status: Accepted

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

a,b = max(w)-min(w),max(z)-min(z)
print(max(a,b))

Submission status: Accepted

Solution code:
N = int(input())
M0 = M1 = -float('inf')
m0 = m1 = float('inf')

for _ in range(N):
    x, y = map(int, input().split())
    M0 = max(M0, x - y)
    m0 = min(m0, x - y)
    M1 = max(M1, x + y)
    m1 = min(m1, x + y)

print(max(M0 - m0, M1 - m1))

Submission status: Accepted

Solution code:
n = int(input())
max_x = max_y = - 5 * 10**9
min_x = min_y = 5 * 10**9
for i in range(n):
    X, Y = map(int, input().split())
    x = X + Y
    y = X - Y
    max_x = max(max_x, x)
    max_y = max(max_y, y)
    min_x = min(min_x, x)
    min_y = min(min_y, y)
print(max(max_x - min_x, max_y - min_y))

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    Z = []
    W = []

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

    a = max(Z) - min(Z)
    b = max(W) - min(W)
    print(max(a, b))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

a = -10**10
b = 10**10
c = -10**10
d = 10**10

for i in range(N):
    x = G[i][0]
    y = G[i][1]
    t = x+y
    u = x-y
    a = max(a,t)
    b = min(b,t)
    c = max(c,u)
    d = min(d,u)

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

Submission status: Accepted

Solution code:
n=int(input())
x=[0]*n
y=[0]*n
z=[]
w=[]
for i in range(n):
    x[i],y[i]= list(map(int, input().strip().split()))
    z.append(x[i]+y[i])
    w.append(x[i]-y[i])
a=max(z)-min(z)
b=max(w)-min(w)
print(max(a,b))

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=sorted(a)
b=sorted(b)
ans=max(a[-1]-a[0],b[-1]-b[0])
print(ans)

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:
n = int(input())
point_dict1 = {}
point_dict2 = {}
for i in range(n):
    x, y = map(int, input().split())
    point_dict1[x + y] = (x, y)
    point_dict2[y - x] = (x, y)
min_point1 = min(point_dict1)
max_point1 = max(point_dict1)
min_point2 = min(point_dict2)
max_point2 = max(point_dict2)
print(max(max_point1 - min_point1, max_point2 - min_point2))

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]
for i in range(N):
    z = A[i][0] + A[i][1]
    w = A[i][0] - A[i][1]
    if i==0:
        M_z = m_z = z
        M_w = m_w = w
    if z > M_z: M_z = z
    if z < m_z: m_z = z
    if w > M_w: M_w = w
    if w < m_w: m_w = w
print(max(M_z-m_z,M_w-m_w))

Submission status: Accepted

Solution code:
N = int(input())

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

UV = [rot(*map(int, input().split())) for _ in range(N)]

mxU = max(u for u, _ in UV)
miU = min(u for u, _ in UV)
mxV = max(v for _, v in UV)
miV = min(v for _, v in UV)

print(max(mxU - miU, mxV - miV))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 11:19:14 2020

@author: ezwry
"""

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

"""
A,Bの場合
"""

maxab = x[0] + y[0]
minab = x[0] + y[0]

for i in range(n):
    xi = x[i]
    yi = y[i]
    mini = xi+yi
    maxi = xi+yi
    if mini < minab:
        minab = mini
    if maxi > maxab:
        maxab = maxi

maxatob = maxab - minab

"""
C,Dの場合
"""

maxcd = y[0]-x[0]
mincd = y[0]-x[0]

for j in range(n):
    maxj = y[j] - x[j]
    minj = y[j] - x[j]
    if maxj > maxcd:
        maxcd = maxj
    if minj < mincd:
        mincd = minj

maxctod = maxcd - mincd

majimax = max(maxatob, maxctod)
print(majimax)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
tail = 0
head = float('inf')
for i in range(N):
    tail = max(tail, sum(A[i]))
    head = min(head, sum(A[i]))
ans_1 = tail - head

tmp_h, tmp_t = 0, 0
tail = A[i]
head = A[i]
for i in range(N):
    tail = A[i] if tmp_t < A[i][0]-A[i][1] else tail
    head = A[i] if tmp_h < A[i][1]-A[i][0] else head
    tmp_t = A[i][0]-A[i][1] if tmp_t < A[i][0]-A[i][1] else tmp_t
    tmp_h = A[i][1]-A[i][0] if tmp_h < A[i][1]-A[i][0] else tmp_h

ans_2 = abs(tail[0]-head[0]) + abs(tail[1]-head[1])
ans = max(ans_1, ans_2)
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)
  
plus.sort()
minus.sort()

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

Submission status: Accepted

Solution code:
'''
Created on 2020/09/14

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  x,y=map(int,pin().split())
  z1=x+y
  z2=x+y
  w1=x-y
  w2=x-y
  for i in range(N-1):
    x,y=map(int,pin().split())
    z1=max(z1,x+y)
    z2=min(z2,x+y)
    w1=max(w1,x-y)
    w2=min(w2,x-y)
  print(max(z1-z2,w1-w2))
  return
main()
#解説AC

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = []
    Y = []

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

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


if __name__ == '__main__':
    main()

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=sorted(A)
B=sorted(B)
print(max(abs(A[0]-A[-1]),abs(B[0]-B[-1])))

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 = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    z = a + b
    w = a - b
    A.append(z)
    B.append(w)
    
P = abs(max(A) - min(A))
Q = abs(max(B) - min(B))
print(max(P, Q))

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
zmax=-float('inf')
zmin = float('inf')
wmax = -float('inf')
wmin = float('inf')

for _ in range(N):
    x,y=map(int,input().split())
    z=x+y
    w=x-y
    zmax = max(z,zmax)
    zmin = min(z,zmin)
    wmax = max(w,wmax)
    wmin = min(w,wmin)
print(max(zmax-zmin,wmax-wmin))

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]
a = []
b = []
for i in range(n):
    a.append(xy[i][0]+xy[i][1])
    b.append(xy[i][0]-xy[i][1])
a_sort = sorted(a)
b_sort = sorted(b)

print(max(a_sort[-1]-a_sort[0],b_sort[-1]-b_sort[0]))

Submission status: Accepted

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

Submission status: Accepted

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

w = [xy[i][0] - xy[i][1] for i in range(n)]
z = [xy[i][0] + xy[i][1] for i in range(n)]
print(max((max(w) - min(w)), (max(z)-min(z))))

Submission status: Accepted

Solution code:
def max_min(val,pos):
  if val<abs_max[pos][0]:
    abs_max[pos][0]=val
  elif val>abs_max[pos][1]:
    abs_max[pos][1]=val
    

n=int(input())

abs_max=[[float('inf'),float('-inf')] for __ in range(4)]

for _ in range(n):
  x,y=map(int,input().split())
  max_min(x+y,0)
  max_min(x-y,1)
  max_min(-x+y,2)
  max_min(-x-y,3)
ans=0
for Min,Max in abs_max:
  ans=max(ans,Max-Min)
print(ans)

Submission status: Accepted

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

def dist(tpl1, tpl2):
    return abs(tpl1[0] - tpl2[0]) + abs(tpl1[1] - tpl2[1])

f0 = []
f1 = []
for i in range(N):
    x, y = xy[i]
    f0.append(x-y)
    f1.append(x+y)
ans = max(ans,
        max(f0) - min(f0),
        max(f1) - min(f1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])

xlim = []
ylim = []

def cha(a):
    return [a[0]-a[1],a[0]+a[1]]

for i in range(N):
        ylim.append(cha(l[i])[1])
        xlim.append(cha(l[i])[0])

xlim.sort()
ylim.sort()

print(max(xlim[-1]-xlim[0],ylim[-1]-ylim[0]))

Submission status: Accepted

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

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:
n = int(input())
X = []
Y = []
for i in range(n):
    x,y = map(int,input().split())
    X.append(x+y)
    Y.append(x-y)

print(max(max(X)-min(X),max(Y)-min(Y)))

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