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

points_pp = []
points_pn = []
points_np = []
points_nn = []
for _ in range(N):
  x, y = map(int, input().split())
  points_pp.append(x+y)
  points_nn.append(-x-y)
  
  points_pn.append(x-y)
  points_np.append(-x+y)
  
ans_pp = max(points_pp) - min(points_pp)  
ans_pn = max(points_pn) - min(points_pn)  
ans_np = max(points_np) - min(points_np)  
ans_nn = max(points_nn) - min(points_nn)
print(max(ans_pp, ans_pn, ans_np, ans_nn))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[]
min_x=10**9+1
min_y=10**9+1
B=[0 for i in range(N)]
C=[0 for i in range(N)]
for i in range(N):
    x,y=map(int,input().split())
    A.append([x,y])
    min_x=min(min_x,x)
    min_y=min(min_y,y)
for i in range(N):
    A[i][0]=A[i][0]-min_x
    A[i][1]=A[i][1]-min_y
    B[i]=A[i][0]+A[i][1]
    C[i]=A[i][0]-A[i][1]
print(max(max(B)-min(B),max(C)-min(C)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)

n=int(input())
table=[(x-y,x+y)for x,y in [map(int,input().split()) for i in range(n)]]
a,b=[table[0][0]]*2,[table[0][1]]*2
ans=0
for x,y in table:
    ans=max(ans,abs(x-a[0]),abs(x-a[1]),abs(y-b[0]),abs(y-b[1]))
    a[0]=min(x,a[0])
    a[1]=max(a[1],x)
    b[0]=min(b[0],y)
    b[1]=max(b[1],y)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

p = max(data1)-min(data1)
q = max(data2)-min(data2)

print(max(p,q))

Submission status: Accepted

Solution code:
N = int(input())
px = []
py = []
cro1 = []
cro2 = []
for i in range(N):
    x,y = map(int,input().split())
    px.append((x,y))
    py.append((x,y))
    cro1.append(x+y)
    cro2.append(y-x)
"""
px.sort()
py.sort(key=lambda x:x[1])
"""
cro1.sort()
cro2.sort()
print(max(cro1[-1]-cro1[0],cro2[-1]-cro2[0]))

Submission status: Accepted

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


if __name__ == '__main__':
    main()

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)
dP=abs(max(P)-min(P))
dM=abs(max(M)-min(M))
print(max(dP,dM))

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
for i, v in enumerate(p):
    x, y = v
    p[i] = x-y, x+y

xm, ym = -10**9, -10**9
xw, yw = 10**9, 10**9
for x, y in p:
    xm = max(xm, x)
    xw = min(xw, x)
    ym = max(ym, y)
    yw = min(yw, y)

# print(p)
ans = max(abs(xm - xw), abs(ym - yw))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
z=[]
c=[]
for j in range(n):
    x1,y1=[int(j) for j in input().split()]
    z.append(x1+y1)
    c.append(x1-y1)
za=max(z)
zi=min(z)
ca=max(c)
ci=min(c)
mx=max(za-zi,ca-ci)
print(mx)

Submission status: Accepted

Solution code:
def LI():return list(map(int,input().split()))
def II():return int(input())
def yes():return print("Yes")
def no():return print("No")
INF=float("inf")
from collections import deque, defaultdict, Counter
from heapq import heappop, heappush
from itertools import product, combinations
from functools import reduce, lru_cache
from math import pi, gcd
from decimal import Decimal

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

class Unionfind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

n=II()
a=[]
b=[]
for _ in range(n):
    x,y=LI()
    a+=(x+y),
    b+=(x-y),
    
# a.sort()
# b.sort()

ans1=max(a)-min(a)
ans2=max(b)-min(b)

ans=max(abs(ans1),abs(ans2))

print(ans)

Submission status: Accepted

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

F = [0]*N

for i in range(N):
    F[i] = xy[i][0] - xy[i][1]
ans = max(F) - min(F)

for i in range(N):
    F[i] = xy[i][0] + xy[i][1]
ans2 = max(F) - min(F)

print(max(ans, ans2))

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
for _ in range(n):
    X,Y = map(int,input().split())
    x.append(X)
    y.append(Y)

res = 0
for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
    smallest = p * x[0] + q * y[0] + 0
    for i in range(n):
        cur = p * x[i] + q * y[i]
        res = max(res, cur - smallest)
        smallest = min(smallest, cur)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X, Y = [], []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x - y)
        Y.append(x + y)
    return max(max(X) - min(X), max(Y) - min(Y))


print(main())

Submission status: Accepted

Solution code:
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
C=[a+b for a,b in zip(A,B)]
D=[a-b for a,b in zip(A,B)]
print(max((max(C)-min(C)),(max(D)-min(D))))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    cnt0 = collections.Counter()
    for x, y in xy:
        cnt0[x+y] += 1
    ans0 = max(cnt0.keys()) - min(cnt0.keys())

    cnt1 = collections.Counter()
    for x, y in xy:
        cnt1[x-y] += 1
    ans1 = max(cnt1.keys()) - min(cnt1.keys())

    print(max(ans0, ans1))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())

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

print(max(abs(wa[0] - wa[-1]), abs(sa[0] - sa[-1])))

Submission status: Accepted

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

best = 0

mn = min(XY, key=lambda pt: pt[0] + pt[1])
mx = max(XY, key=lambda pt: pt[0] + pt[1])
best = max(best, abs(mn[0] - mx[0]) + abs(mn[1] - mx[1]))

mn = min(XY, key=lambda pt: pt[0] - pt[1])
mx = max(XY, key=lambda pt: pt[0] - pt[1])
best = max(best, abs(mn[0] - mx[0]) + abs(mn[1] - mx[1]))


print(best)

Submission status: Accepted

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

n = int(input())
a, b = [], []
res = []

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

a.sort()
b.sort()

res.append(a[-1] - a[0])
res.append(b[-1] - b[0])

print(max(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

minus = []
plus = []

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

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

Submission status: Accepted

Solution code:
#Python Template

from sys import stdin, stdout

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

def v1(l):
	return l[0] + l[1]

def v2(l):
	return l[0] - l[1]

def main():
	n = int(stdin.readline())
	pts = []
	for _ in range(n):
		x, y = [int(i) for i in stdin.readline().split()]
		pts.append([x,y])
	s1 = sorted(pts, key=v1)
	s2 = sorted(pts, key=v2)
	#print(s1)
	#print(s2)

	d1 = d(s1[0], s1[-1])
	d2 = d(s2[0], s2[-1])
	dist = max(d1, d2)
	print(dist)


	

main()

Submission status: Accepted

Solution code:

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())

ru = -2*10**9
lu = -2*10**9
ld = -2*10**9
rd = -2*10**9

for _ in range(N):
    x,y = map(int,input().split())
    a = x+y
    b = x-y
    ru = max2(ru,a)
    lu = max2(lu,-b)
    ld = max2(ld,-a)
    rd = max2(rd,b)

print(max2(ru+ld,lu+rd))

Submission status: Accepted

Solution code:
N = int(input())
pulls = []
minus = []

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

pulls.sort()
minus.sort()
print(max(pulls[-1] - pulls[0], minus[-1] - minus[0]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


def main():
    N, *XY = map(int, read().split())

    P = [(x, y) for x, y in zip(*[iter(XY)] * 2)]
    Q = [f(x, y) for x, y in P]
    R = [[q[i] for q in Q] for i in (0, 1)]

    ans = 0
    for i in (0, 1):
        ma = max(R[i])
        mi = min(R[i])
        if ans < ma - mi:
            ans = ma - mi

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
mi1= 10**10
ma1= -10**10
mi2=10**10
ma2=-10**10
P = []
for i in range(n):
  a = list(map(int,input().split()))
  P.append(a)
P.sort(key = lambda x:x[0])
for i in range(n):
    p=P[i]
    mi1=min(mi1,p[0]+p[1])
    ma1=max(ma1,p[0]+p[1])
    mi2=min(mi2,p[0]-p[1])
    ma2=max(ma2,p[0]-p[1])
print(max(ma1-mi1,ma2-mi2))

Submission status: Accepted

Solution code:
N = int(input())

lst = [[0, 0, 0, 0] for _ in range(N)]
p = [0] * N
m = [0] * N

for i in range(N):
  x, y = map(int, input().split())
  lst[i][0] = x
  lst[i][1] = y
  p[i] = x+y
  m[i] = x-y
  
d = max( max(p) - min(p), max(m) - min(m) )
print(d)

Submission status: Accepted

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

N = int(input())
P, Q = [], []
for _ in range(N):
    x, y = map(int, input().split())
    P.append(f(x,y))
    Q.append(g(x,y))
print(max(max(P)-min(P), max(Q)-min(Q)))

Submission status: Accepted

Solution code:
N = int(input())
XY_set = set(tuple(map(int, input().split())) for _ in range(N))
N = len(XY_set)

XY45 = [(x + y, x - y) for x, y in XY_set]
ans = max(max(x for x, _ in XY45) - min(x for x, _ in XY45),
          max(y for _, y in XY45) - min(y for _, y in XY45))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a0=10**10
b0=10**10
c0=10**10
d0=10**10
a1=-10**10
b1=-10**10
c1=-10**10
d1=-10**10
for i in range(n):
  x,y=map(int,input().split())
  a=x+y
  if a0>a:
    a0=a
  if a1<a:
    a1=a
  b=x-y
  if b0>b:
    b0=b
  if b1<b:
    b1=b
  c=-x+y
  if c0>c:
    c0=c
  if c1<c:
    c1=c
  d=-x-y
  if d0>d:
    d0=d
  if d1<d:
    d1=d
print(max(a1-a0,b1-b0,c1-c0,d1-d0))

Submission status: Accepted

Solution code:
n=int(input())
ans=0
xway=[]
xsay=[]
for i in range(n):
  t1,t2=map(int,input().split())
  xway.append(t1+t2)
  xsay.append(t1-t2)
xway.sort()
xsay.sort()
ans=max(ans,xway[-1]-xway[0])
ans=max(ans,xsay[-1]-xsay[0])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = []
for i in range(N):
    XY.append(list(map(int,input().split())))
ZW = []
for i in range(N):
    ZW.append([XY[i][0]-XY[i][1],XY[i][0]+XY[i][1]])

out = []
ZW.sort(key=lambda x:x[0])
out.append(abs(ZW[0][0]-ZW[N-1][0]))
ZW.sort(key=lambda x:x[1])
out.append(abs(ZW[0][1]-ZW[N-1][1]))
print(max(out))

Submission status: Accepted

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

N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]

PLUS=[]
MINUS=[]

for x,y in P:
    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:
#!/usr/bin/env pypy3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

sum = []
dif = []

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

    sum += [x+y]
    dif += [x-y]

ans1 = max(sum) - min(sum)
ans2 = max(dif) - min(dif)

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ab=[]
A=-1e20
B=-1e20
C=1e20
D=1e20
for i in range(n):
	x,y=map(int,input().split())
	A=max(A,x+y)
	B=max(B,x-y)
	C=min(C,x+y)
	D=min(D,x-y)
print(max(A-C,B-D))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = []
gg = []
for i in range(n):
    x,y = na()
    g.append(x-y)
    gg.append(x+y)

ans = max(max(g)-min(g),max(gg)-min(gg))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = [tuple(map(int, input().split())) for _ in range(N)]
L.sort(key=lambda x: x[0]+x[1])
a = abs(L[0][0]-L[-1][0])+abs(L[0][1]-L[-1][1])
L.sort(key=lambda x: x[0]-x[1])
b = abs(L[0][0]-L[-1][0])+abs(L[0][1]-L[-1][1])
print(max(a, b))

Submission status: Accepted

Solution code:
def main():
    # start coding here...
    N = int(input())
    a = []
    b = []
    for i 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)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
f0 = []
f1 = []
for i in range(n):
    x,y = lr()
    f0.append(x-y)
    f1.append(x+y)
print(max(max(f0)-min(f0), max(f1)-min(f1)))

Submission status: Accepted

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

n=int(input())
x=[]
y=[]
for i in range(n):
  x1,y1=map(int,input().split())
  x.append(x1)
  y.append(y1)
max1=-10**10
for i in range(n):
  if x[i]+y[i]>max1:
    point1=i
    max1=x[i]+y[i]
max1=-10**10
for i in range(n):
  if x[i]-y[i]>max1:
    point2=i
    max1=x[i]-y[i]
max1=-10**10
for i in range(n):
  if -x[i]-y[i]>max1:
    point3=i
    max1=-x[i]-y[i]
max1=-10**10
for i in range(n):
  if -x[i]+y[i]>max1:
    point4=i
    max1=-x[i]+y[i]
ans=0
for i in range(n):
  ans=max(ans,abs(x[i]-x[point1])+abs(y[i]-y[point1]))
  ans=max(ans,abs(x[i]-x[point2])+abs(y[i]-y[point2]))
  ans=max(ans,abs(x[i]-x[point3])+abs(y[i]-y[point3]))
  ans=max(ans,abs(x[i]-x[point4])+abs(y[i]-y[point4]))
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    inlis = list()
    inlis2_x = list()
    inlis2_y = list()
    for _ in range(n):
        x, y = map(int, input().split())
        inlis.append([x,y])
        inlis2_x.append(x-y)
        inlis2_y.append(x+y)
    
    sa_x = max(inlis2_x) - min(inlis2_x)
    sa_y = max(inlis2_y) - min(inlis2_y)
    print(max(sa_x, sa_y))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

x_plus_y = []
x_minus_y = []

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

x_plus_y_max = max(x_plus_y)
x_plus_y_min = min(x_plus_y)
x_minus_y_max = max(x_minus_y)
x_minus_y_min = min(x_minus_y)

print(max(x_plus_y_max - x_plus_y_min,
          x_minus_y_max - x_minus_y_min))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.range = [(-1,n)] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.range[self.num + i] = (i,i)
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
            self.range[i] = (self.range[2 * i][0],self.range[2 * i + 1][1])

    def update(self, k, x):
        k += self.num
        self.tree[k] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

N = int(input())

p = [tuple(map(int,input().split())) for i in range(N)]
p.sort()

y_val = set([p[i][1] for i in range(N)])
y_val = list(y_val)
y_val.sort()
comp = {i:e for e,i in enumerate(y_val)}
n = len(y_val)

seg_low = SegmentTree([-10**18 for i in range(n)],max,-10**18)
seg_high = SegmentTree([-10**18 for i in range(n)],max,-10**18)

xmin = [-10**18 for i in range(n)]

ans = -10**18
for x,y in p:
    idx = comp[y]
    tmp1 = x+y+seg_low.query(0,idx)
    tmp2 = x-y+seg_high.query(idx,n)
    ans = max(ans,tmp1,tmp2)
    if xmin[idx]!=-10**18:
        if xmin[idx]>x:
            seg_low.update(idx,xmin[idx]-x)
            seg_high.update(idx,xmin[idx]-x)
            xmin[idx] = x
    else:
        seg_low.update(idx,-y-x+10**18)
        seg_high.update(idx,y-x+10**18)
        xmin[idx] = x

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
maxda = -10**18
minda = 10**18
maxdb = -10**18
mindb = 10**18
for i in range(n):
	x,y = map(int,input().split())
	maxda = max(maxda, x-y)
	minda = min(minda, x-y)
	maxdb = max(maxdb, x+y)
	mindb = min(mindb, y+x)
print(max(maxda-minda, maxdb-mindb))

Submission status: Accepted

Solution code:
def solve(n, x_list, y_list):
    # x + y
    xy_1_list = [x + y for x, y in zip(x_list, y_list)]
    # x - y
    xy_2_list = [x - y for x, y in zip(x_list, y_list)]

    res = max(max(xy_1_list) - min(xy_1_list), max(xy_2_list) - min(xy_2_list))
    return res


def main():
    n = int(input())
    x_list = [0] * n
    y_list = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        x_list[i] = x
        y_list[i] = y
    res = solve(n, x_list, y_list)
    print(res)


def test():
    assert solve(3, [1, 2, 3], [1, 4, 2]) == 4
    assert solve(2, [1, 1], [1, 1]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split()))for _ in range(n)]
xy1ma=-10**10
xy1mi=10**10
xy2ma=-10**10
xy2mi=10**10
for x,y in xy:
  xy1ma=max(xy1ma,x-y)
  xy1mi=min(xy1mi,x-y)
  xy2ma=max(xy2ma,x+y)
  xy2mi=min(xy2mi,x+y)
print(max(xy1ma-xy1mi,xy2ma-xy2mi))

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

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

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	N = int(input())
	L1 = []
	L2 = []	
	for i in range(N):
		x, y = getlist()
		L1.append(x + y)
		L2.append(x - y)
	L1.sort()
	L2.sort()
	ans1 = L1[-1] - L1[0]
	ans2 = L2[-1] - L2[0]
	ans = max(ans1, ans2)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
for i in range(n):
    tmp_x, tmp_y = list(map(int, input().split()))
    x.append(tmp_x + tmp_y)
    y.append(tmp_x - tmp_y)
    
max_x = max(x) - min(x)
max_y = max(y) - min(y)
print(max(max_x, max_y))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

ru.sort()
ld.sort()
ans = 0
ans = max(ru[-1] - ru[0], ans)
ans = max(ld[-1] - ld[0], ans)

print(ans)

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

print(max(Xs[-1]-Xs[0], Ys[-1]-Ys[0]))

Submission status: Accepted

Solution code:
n=int(input())
arr1=[]
arr2=[]
for i in range(n):
    h,m=list(map(int,input().split()))
    arr1.append(h)
    arr2.append(m)
    
l1, l2 ,l3, l4 = [], [], [], []
for i in range(len(arr1)):
    l1 += [arr1[i]+arr2[i]]
    l2 += [arr1[i]-arr2[i]]
    l3 += [-arr1[i]+arr2[i]]
    l4 += [-arr1[i]-arr2[i]]
res = []
res += [max(l1)-min(l1)]
res += [max(l2) -min(l2)]
res += [max(l3)-min(l3)]
res += [max(l4)-min(l4)]
print(max(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

A = []
B = []
for x,y in XY:
    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())
INF = 1000000001
nw, sw, ne, se = (INF, -INF), (INF, INF), (-INF, -INF), (-INF, INF)
for _ in range(n):
    x, y = [int(x) for x in input().split()]
    if y - x > nw[1] - nw[0]:
        nw = x, y
    if y - x < se[1] - se[0]:
        se = x, y
    if y + x > ne[1] + ne[0]:
        ne = x, y
    if y + x < sw[1] + sw[0]:
        sw = x, y

print(max(abs(ne[0] - sw[0]) + abs(ne[1] - sw[1]),
          abs(nw[0] - se[0]) + abs(nw[1] - se[1])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
mn = 10 ** 10
mx = -10 ** 10
mn2 = 10 ** 10
mx2 = -10 ** 10
qs = [tuple(map(int, input().split())) for _ in range(N)]
qs.sort()
for i in range(N):
  x, y = qs[i]
  mn = min(mn, x + y)
  mx = max(mx, x + y)
  mn2 = min(mn2, x - y)
  mx2 = max(mx2, x - y)
print(max(abs(mx2 - mn2), abs(mx - mn)))

Submission status: Accepted

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

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

print(max(abs(SUM[0] - SUM[-1]), abs(DIF[0] - DIF[-1])))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = [tuple(read_values()) for _ in range(N)]
    mX = V(min)
    MX = V(max)
    mY = V(min)
    MY = V(max)

    for p in P:
        x = p[0] + p[1]
        y = p[0] - p[1]
        mX.ud(x)
        MX.ud(x)
        mY.ud(y)
        MY.ud(y)
    
    print(max(MX.v - mX.v, MY.v - mY.v))


if __name__ == "__main__":
    main()