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())
xy = [list(map(int,input().split())) for _ in range(N)]
ma = -float('inf')
mi = float('inf')
for x,y in xy:
  ma = max(ma,x-y)
  mi = min(mi,x-y)
ans = ma - mi

ma = -float('inf')
mi = float('inf')
for x,y in xy:
  ma = max(ma,x+y)
  mi = min(mi,x+y)
  
ans = max(ans, ma - mi)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
C = [0] * N
D = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    C[i] = (x + y, x, y)
    D[i] = (x - y, x, y)
C = sorted(C)
D = sorted(D)
# a1, x1, y2 = C[-1]
# print(C)
ans = -INF
now = abs(C[-1][1] - C[0][1]) + abs(C[-1][2] - C[0][2])
ans = max(ans, now)
now = abs(D[-1][0] - D[0][0])
ans = max(ans, now)
print(ans)

Submission status: Accepted

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

che_x=[0]*n
che_y=[0]*n

for i in range(n):
    che_x[i]=x[i]-y[i]
    che_y[i]=x[i]+y[i]

ans=max(max(che_x)-min(che_x),max(che_y)-min(che_y))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
fx_list = []
fy_list = []

for i in range(n):
    x,y = (int(x) for x in input().split())
    fx_list.append(x-y)
    fy_list.append(x+y)

a = max(fx_list) - min(fx_list)
b = max(fy_list) - min(fy_list)

print(max([a,b]))

Submission status: Accepted

Solution code:
n = int(input())
dist = []
max1 = -pow(10, 11)
min1 = pow(10, 11)
max2 = -pow(10, 11)
min2 = pow(10, 11) 
for i in range(n):
    x, y = (int(x) for x in input().split())
    if max1 < x + y:
        max1 = x + y
    if min1 > x + y:
        min1 = x + y
    if max2 < x - y:
        max2 = x - y
    if min2 > x - y:
        min2 = x - y
print(max(max1-min1, max2-min2))

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
pos = []
for i in range(N):
	x, y = rl()
	pos.append((x,y))

pp = []
pm = []
mm = []
mp = []
for x, y in pos:
	pp.append(x+y)
	pm.append(x-y)
	mm.append(-x-y)
	mp.append(-x+y)
max_pp = max(pp)
max_pm = max(pm)
max_mm = max(mm)
max_mp = max(mp)

ans = max(max_pp+max_mm, max_pm+max_mp, max_mp+max_pm, max_mm+max_pp)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

f0_list = [x+y for x, y in p_list]
f1_list = [x-y for x, y in p_list]

max_f0 = max(f0_list) - min(f0_list)
max_f1 = max(f1_list) - min(f1_list)

print(max([max_f0, max_f1]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
xy = [tuple(MI()) for _ in range(N)]
A = [sum(xy[i]) for i in range(N)]
a = max(A)-min(A)
B = []
for i in range(N):
    x,y = xy[i]
    B.append(x-y)
b = max(B)-min(B)

print(max(a,b))

Submission status: Accepted

Solution code:
n = int(input())
i = []
for z in range(n):
    i.append([int(s) for s in input().split()])

ur = [ind[0]+ind[1] for ind in i]
ul = [ind[0]-ind[1] for ind in i]
print(max([max(ur)-min(ur), max(ul)-min(ul)]))

Submission status: Accepted

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

result = max(max(xsum)-min(xsum), max(xsub)-min(xsub))
print(result)

Submission status: Accepted

Solution code:
def main():
    point_count = int(input())
    sums = []
    diffs = []
    for _ in range(point_count):
        x, y = [int(x) for x in input().split()]
        sums.append(x + y)
        diffs.append(x - y)
    pat_sum = max(sums) - min(sums)  # max (Xi + Yi) - (Xj + Yj)
    pat_diff = max(diffs) - min(diffs)  # max (Xi - Yi) - (Xj - Yj)
    return max(pat_sum, pat_diff)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys


N = int(sys.stdin.readline())
points = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    points.append((x, y))

f1 = []
f2 = []
for (x, y) in points:
    f1.append(x-y)
    f2.append(x+y)

ans = max(max(f1) - min(f1), max(f2) - min(f2))
print(ans)

Submission status: Accepted

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

mx = 9
L = [0] * N
for i in range(N):
  x, y = xy[i]
  L[i] = x + y
  mx = max(mx, x)

L.sort()
ans = L[-1] - L[0]

for i in range(N):
  x, y = xy[i]
  L[i] = mx - x + y

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    point_count = int(input())
    sums = set()
    diffs = set()
    for _ in range(point_count):
        x, y = [int(x) for x in input().split()]
        sums.add(x + y)
        diffs.add(x - y)
    pat_sum = max(sums) - min(sums)  # max (Xi + Yi) - (Xj + Yj)
    pat_diff = max(diffs) - min(diffs)  # max (Xi - Yi) - (Xj - Yj)
    return max(pat_sum, pat_diff)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
xy = []
xplusy = []
xminusy = []

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


ans1 = max(xplusy) - min(xplusy)
ans2 = max(xminusy) - min(xminusy)

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n=int(input())
    X,Y,XY=[],[],[]
    for i in range(n):
      x,y=map(int,input().split())
      X.append(x+y)
      Y.append(x-y)
      XY.append((x+y,x-y))
    X.sort()
    Y.sort()
    ans=0
    for x,y in XY:
      ans=max(ans,max(x-X[0],X[-1]-x,y-Y[0],Y[-1]-y))
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

n = int(input())
ans = 0
peri = []
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort(key=lambda p: (p[0], p[1]))
peri.append(max(P, key=lambda p: (p[0], p[1])))
peri.append(min(P, key=lambda p: (p[0], p[1])))
peri.append(max(P, key=lambda p: (p[0], -p[1])))
peri.append(min(P, key=lambda p: (p[0], -p[1])))
peri.append(max(P, key=lambda p: (-p[0], p[1])))
peri.append(min(P, key=lambda p: (-p[0], p[1])))
peri.append(max(P, key=lambda p: (-p[0], -p[1])))
peri.append(min(P, key=lambda p: (-p[0], -p[1])))
peri.append(max(P, key=lambda p: (p[1], p[0])))
peri.append(min(P, key=lambda p: (p[1], p[0])))
peri.append(max(P, key=lambda p: (-p[1], p[0])))
peri.append(min(P, key=lambda p: (-p[1], p[0])))
peri.append(max(P, key=lambda p: (p[1], -p[0])))
peri.append(min(P, key=lambda p: (p[1], -p[0])))
peri.append(max(P, key=lambda p: (-p[1], -p[0])))
peri.append(min(P, key=lambda p: (-p[1], -p[0])))
peri.append(max(P, key=lambda p: p[0]+p[1]))
peri.append(max(P, key=lambda p: -p[0]+p[1]))
peri.append(max(P, key=lambda p: p[0]-p[1]))
peri.append(max(P, key=lambda p: -p[0]-p[1]))

peri = set(peri)

for p in P:
    for q in peri:
        ans = max(ans, dist(p, q))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
cx = sum(X)/N
cy = sum(Y)/N
dist1 = []
dist2 = []

for x, y in zip(X, Y):
    dist1_ = x-cx + y-cy
    dist1.append(dist1_)
    dist2_ = (x-cx) - (y-cy)
    dist2.append(dist2_)

p1_max = np.argmax(np.array(dist1))
p1_min = np.argmin(np.array(dist1))
p2_max = np.argmax(np.array(dist2))
p2_min = np.argmin(np.array(dist2))

ans1 = abs(X[p1_max] - X[p1_min]) + abs(Y[p1_max] - Y[p1_min])
ans2 = abs(X[p2_max] - X[p2_min]) + abs(Y[p2_max] - Y[p2_min]) 

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
from itertools import product


def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


N, *xy = map(int, open(0).read().split())
points = [(x, y) for x, y in zip(*[iter(xy)] * 2)]
values = [-float("inf") for _ in range(4)]
outrims = [points[0], points[0], points[0], points[0]]
for x, y in points:
    for i, (opx, opy) in enumerate(product([1, -1], repeat=2)):
        v = opx * x + opy * y
        if v > values[i]:
            values[i] = v
            outrims[i] = (x, y)

ans = 0
for p in points:
    for o in outrims:
        ans = max(ans, dist(p, o))
print(ans)

Submission status: Accepted

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

l.sort()
lans.sort()
#print(l)
print(max(l[-1]-l[0],lans[-1]-lans[0]))

'''
  ll1=[ll[1],ll[0]]
  lan.append(ll1)

l.sort()
lan.sort()
we=abs(l[0][0]-l[-1][0])+abs(l[0][1]-l[-1][1])
we1=abs(lan[0][0]-lan[-1][0])+abs(lan[0][1]-lan[-1][1])
print(max(we,we1))
'''

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    x = []
    y = []

    N = NI()

    for _ in range(N):
        a,b = LI()
        x.append(a+b)
        y.append(a-b)

    xm = max(x) - min(x)
    ym = max(y) - min(y)

    print(max(ym,xm))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    X, Y = [], []
    for x, y in XY:
        X.append(x+y)
        Y.append(x-y)
    X.sort()
    Y.sort()

    return max(X[-1]-X[0], Y[-1]-Y[0])


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

d0 = [0]*n
d1 = [0]*n
for i,[x,y] in enumerate(x) :
    d0[i] = x-y
    d1[i] = x+y
print(max(max(d0)-min(d0), max(d1)-min(d1)))

Submission status: Accepted

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


def maximize(ps):
    zs = sorted(x + y for x, y in ps)
    ws = sorted(x - y for x, y in ps)
    return max(abs(zs[0] - zs[-1]), abs(ws[0] - ws[-1]))


def main():
    n = int(input())
    ps = []
    for _ in range(n):
        ps.append(tuple(int(z) for z in input().split()))
    res = maximize(ps)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())
    ru = None
    rd = None
    lu = None
    ld = None

    for i in range(n):
        row = [int(x) for x in input().rstrip().split(" ")]
        if i == 0:
            ru = row
            rd = row
            lu = row
            ld = row
            continue

        if ru[0] + ru[1] < row[0] + row[1]:
            ru = row
        if rd[0] - rd[1] < row[0] - row[1]:
            rd = row
        if -lu[0] + lu[1] < -row[0] + row[1]:
            lu = row
        if -ld[0] - ld[1] < -row[0] - row[1]:
            ld = row

    ans = 0
    points = [ru, rd, lu, ld]
    for i in range(4):
        for j in range(i+1, 4):
            tmp = dist(points[i], points[j])
            if ans < tmp:
                ans = tmp

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

one=-float('inf')
two=-float('inf')
ans=0
for i in range(n):
    x,y=xy[i]
    ans=max(ans,x+max(y+one,two-y))
    one=max(one,-(x+y))
    two=max(two,y-x)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X,Y = [],[]
def func(p):
    return p[0]-p[1], p[0]+p[1]
for _ in range(N):
    x,y = func(list(map(int,input().split())))
    X.append(x)
    Y.append(y)
ans = 0
ans = max(max(X)-min(X),max(Y)-min(Y))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int, input().split())) for _ in range(n)]
a1=0
a2=xy[0][0]+xy[0][1]
b1=xy[0][0]-xy[0][1]
b2=xy[0][0]-xy[0][1]
for i in range(n):
    res1=xy[i][0]+xy[i][1]
    res2=xy[i][0]-xy[i][1]
    a1=max(a1,res1)
    a2=min(a2,res1)
    b1=max(b1,res2)
    b2=min(b2,res2)
ans=max(a1-a2,b1-b2)
print(ans)

Submission status: Accepted

Solution code:

N = int(input())

# (0,0)からと(0,10**9)からの距離でMinとMaxを持っておいてみる
from_0 = [(10**9, 10**9), (0,0)]
from_f = [(10**9, 10**9), (0,0)]

for i in range(N):
    x,y = map(int, input().split())
    if x + y < from_0[0][0] + from_0[0][1]:
        from_0[0] = (x,y)
    if x + y > from_0[1][0] + from_0[1][1]:
        from_0[1] = (x,y)
    
    new_y = 10**9 - y
    if x + new_y < from_f[0][0] + from_f[0][1]:
        from_f[0] = (x,new_y)
    if x + new_y > from_f[1][0] + from_f[1][1]:
        from_f[1] = (x,new_y)
    
dist_0 = abs(from_0[1][0] - from_0[0][0]) + abs(from_0[1][1] - from_0[0][1])
dist_f = abs(from_f[1][0] - from_f[0][0]) + abs(from_f[1][1] - from_f[0][1])
print(max(dist_0, dist_f))

Submission status: Accepted

Solution code:
n = int(input())

max_s = 1 - (10 ** 9)
min_s = 2 * (10 ** 9)
max_t = 1 - (10 ** 9)
min_t = 2 * (10 ** 9)
for _ in range(n):
    x, y = map(int, input().split())
    s = x - y
    t = x + y
    
    max_s = max(max_s, s)
    min_s = min(min_s, s)
    max_t = max(max_t, t)
    min_t = min(min_t, t)

print(max(max_s - min_s, max_t - min_t))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def main(n,x):
    x.sort()
    xmax = [0,x[0][1]+x[0][0]]
    xmin = [0,x[0][1]+x[0][0]]
    for i in range(1,n):
        idx = x[i]
        s = idx[1]+idx[0]
        if s>xmax[1]:
            xmax = [i,s]
        elif s<xmin[1]:
            xmin = [i,s]
    m1 = abs(x[xmax[0]][0]-x[xmin[0]][0])+abs(x[xmax[0]][1]-x[xmin[0]][1])
    ymax = [0,x[0][1]-x[0][0]]
    ymin = [0,x[0][1]-x[0][0]]
    for i in range(1,n):
        idx = x[i]
        s = idx[1]-idx[0]
        if s>ymax[1]:
            ymax = [i,s]
        elif s<ymin[1]:
            ymin = [i,s]
    m2 = abs(x[ymax[0]][0]-x[ymin[0]][0])+abs(x[ymax[0]][1]-x[ymin[0]][1])
    print(max(m1,m2))
    

if __name__=="__main__":
    n,x = getval()
    main(n,x)

Submission status: Accepted

Solution code:
def main():
    point_count = int(input())
    sums = []
    diffs = []
    for _ in range(point_count):
        x, y = [int(x) for x in input().split()]
        sums.append(x + y)
        diffs.append(x - y)
    pat_sum = abs(max(sums) - min(sums))
    pat_diff = abs(max(diffs) - min(diffs))
    return max(pat_sum, pat_diff)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

def dist(a,b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
def calc(xy):
    mn1 = min(xy, key=lambda z: z[0]+z[1])
    mx1 = max(xy, key=lambda z: z[0]+z[1])

    mn2 = min(xy, key=lambda z: z[0]-z[1])
    mx2 = max(xy, key=lambda z: z[0]-z[1])

    return max(dist(mn1, mx1), dist(mn2, mx2))
    
print(calc(xy))

Submission status: Accepted

Solution code:
def l_inf_dist(x,y,x0,y0):
    return max(abs(x - x0), abs(y - y0))

N = int(input())
pts = [tuple(map(int, input().split())) for _ in range(N)]
pts_conv_x = [pts[i][1] + pts[i][0] for i in range(N)]
pts_conv_y = [pts[i][1] - pts[i][0] for i in range(N)]

x_max_ind = pts_conv_x.index(max(pts_conv_x))
x_min_ind = pts_conv_x.index(min(pts_conv_x))
y_max_ind = pts_conv_y.index(max(pts_conv_y))
y_min_ind = pts_conv_y.index(min(pts_conv_y))

x_max_pt = (pts_conv_x[x_max_ind], pts_conv_y[x_max_ind])
x_min_pt = (pts_conv_x[x_min_ind], pts_conv_y[x_min_ind])
y_max_pt = (pts_conv_x[y_max_ind], pts_conv_y[y_max_ind])
y_min_pt = (pts_conv_x[y_min_ind], pts_conv_y[y_min_ind])

dist_max = 0
for i in range(N):
    dist_max = max(dist_max, l_inf_dist(x_max_pt[0], x_max_pt[1], pts_conv_x[i], pts_conv_y[i]), l_inf_dist(x_min_pt[0], x_min_pt[1], pts_conv_x[i], pts_conv_y[i]), l_inf_dist(y_max_pt[0], y_max_pt[1], pts_conv_x[i], pts_conv_y[i]), l_inf_dist(y_min_pt[0], y_min_pt[1], pts_conv_x[i], pts_conv_y[i]))

print(dist_max)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

N = INT()
U = []
V = []
for i in range(N):
    x, y = MAP()
    U.append(x+y)
    V.append(x-y)

U.sort()
V.sort()
ans = max(U[-1]-U[0], V[-1]-V[0])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

X = []
Y = []
ans = 0

for i in range(N):
    x, y = map(int, input().split())
    X.append(x+y)
    Y.append(x-y)
    
m = [max(X), max(Y)]
s = [min(X), min(Y)]
    
for i in range(2):
    ans = max(ans, m[i]-s[i])
    
print(ans)

Submission status: Accepted

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
N=int(input())
points=[list(map(int,input().split())) for _ in range(N)]


chebmax0=-float("inf")
chebmin0=float("inf")
chebmax1=-float("inf")
chebmin1=float("inf")

#chebmax0→x-yのmax
for l in points:
    chebmax0=max(chebmax0,l[0]-l[1])
for l in points:
    chebmin0=min(chebmin0,l[0]-l[1])
for l in points:
    chebmax1=max(chebmax1,l[0]+l[1])
for l in points:
    chebmin1=min(chebmin1,l[0]+l[1])
#print(chebmin1,chebmax1,chebmin0,chebmax0)
print(max(chebmax0-chebmin0,chebmax1-chebmin1))

Submission status: Accepted

Solution code:
N = int(input())
data_pp = [0]*N
data_pm = [0]*N
data_mp = [0]*N
data_mm = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    data_pp[i] = x+y
    data_pm[i] = x-y
    data_mp[i] = -x + y
    data_mm[i] = -x - y

tmp1 = max(data_pp) + max(data_mm)
tmp2 = max(data_mp) + max(data_pm)
tmp3 = max(data_pm) + max(data_mp)
tmp4 = max(data_mm) + max(data_pp)
print(max(tmp1, tmp2, tmp3, tmp4))
def d(p1, p2):
    xA = p1[0]
    xB = p2[0]

    yA = p1[1]
    yB = p2[1]
    return max(xA + yA - (xB + yB), - (xA - yA) - -1 * (xB - yB), xA - yA - (xB - yB), -1*(xA + yA)- -1 * (xB + yB))

Submission status: Accepted

Solution code:
input=__import__('sys').stdin.readline
def getdist(a,b):return abs(a[0]-b[0])+abs(a[1]-b[1])
n=int(input())
s=[]
for _ in range(n):s.append([*map(int,input().split())])
ans=0
def ff1(x):return x[0]+x[1]
def ff2(x):return x[0]-x[1]
f1=sorted(s,key=ff1)
f2=sorted(s,key=ff2)
ans=max(ans,getdist(f1[0],f1[-1]))
ans=max(ans,getdist(f1[0],f1[1]))
ans=max(ans,getdist(f1[-1],f1[-2]))
ans=max(ans,getdist(f2[0],f2[-1]))
ans=max(ans,getdist(f2[0],f2[1]))
ans=max(ans,getdist(f2[-1],f2[-2]))
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    xy_diff = [0] * N
    xy_plus = [0] * N

    for i in range(N):
        x, y = in_nn()
        xy_diff[i] = x - y
        xy_plus[i] = x + y

    d1 = max(xy_diff) - min(xy_diff)
    d2 = max(xy_plus) - min(xy_plus)

    print(max(d1, d2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L1, L2 = [], []
for i in range(N):
  l = list(map(int, input().split()))
  L1.append(l[0]-l[1])
  L2.append(l[0]+l[1])
  
ans = max(max(L1)-min(L1), max(L2)-min(L2))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = []
b = []
for _ in range(n):
    x,y = inpl()
    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())
xy = [list(map(int,input().split())) for _ in range(n)]

L1 = [i[0] + i[1] for i in xy]
L2 = [i[0] - i[1] for i in xy]

m1 = max(L1) - min(L1)
m2 = max(L2) - min(L2)

print( max(m1, m2) )

Submission status: Accepted

Solution code:
n=int(input())
l_x=[]
l_y=[]

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

	l_x.append(x+y)
	l_y.append(x-y)

tmpx=max(l_x)-min(l_x)
tmpy=max(l_y)-min(l_y)

if tmpx>tmpy:
	print(tmpx)
else:
	print(tmpy)

Submission status: Accepted

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

n = int(input())

INF = float('inf')

plusmax = minusmax =-INF
plusmin = minusmin = INF

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

    x_minus_y = x-y
    x_plus_y = x+y

    plusmax = max(plusmax, x_plus_y)
    plusmin = min(plusmin, x_plus_y)
    minusmax = max(minusmax, x_minus_y)
    minusmin = min(minusmin, x_minus_y)

ans0 = plusmax - plusmin
ans1 = minusmax - minusmin
print( max(ans0, ans1))

Submission status: Accepted

Solution code:
input=__import__('sys').stdin.readline
def getdist(a,b):return abs(a[0]-b[0])+abs(a[1]-b[1])
n=int(input())
s=[]
for _ in range(n):s.append([*map(int,input().split())])
ans=0
sx=sorted(s)
sy=sorted(s,key=lambda x:x[1])
ans=max(ans,getdist(sx[-1],sx[-2]))
ans=max(ans,getdist(sx[0],sx[1]))
ans=max(ans,getdist(sy[-1],sy[-2]))
ans=max(ans,getdist(sy[0],sy[1]))
def ff1(x):return x[0]+x[1]
def ff2(x):return x[0]-x[1]
f1=sorted(s,key=ff1)
f2=sorted(s,key=ff2)
ans=max(ans,getdist(f1[0],f1[-1]))
ans=max(ans,getdist(f1[0],f1[1]))
ans=max(ans,getdist(f1[-1],f1[-2]))
ans=max(ans,getdist(f2[0],f2[-1]))
ans=max(ans,getdist(f2[0],f2[1]))
ans=max(ans,getdist(f2[-1],f2[-2]))
def ff1(x):return abs(x[0]+x[1])
def ff2(x):return abs(x[0]-x[1])
f1=sorted(s,key=ff1)
f2=sorted(s,key=ff2)
ans=max(ans,getdist(f1[0],f1[-1]))
ans=max(ans,getdist(f1[0],f1[1]))
ans=max(ans,getdist(f1[-1],f1[-2]))
ans=max(ans,getdist(f2[0],f2[-1]))
ans=max(ans,getdist(f2[0],f2[1]))
ans=max(ans,getdist(f2[-1],f2[-2]))
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    # A:和、B:差
    A = [0] * N
    B = [0] * N
    for i in range(N):
        x, y = map(int, readline().split())
        A[i] = x+y
        B[i] = x-y

    ans = max(max(A)-min(A), max(B)-min(B))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
arr1=[0]*n
arr2=[0]*n
for i in range(n):
    x,y=map(int, input().split())
    arr1[i]=x+y
    arr2[i]=x-y

arr1=sorted(arr1)
p=arr1[-1]-arr1[0]
arr2=sorted(arr2)
q=arr2[-1]-arr2[0]
print(max(p,q))

Submission status: Accepted

Solution code:
n = int(input())
mi0,ma0 = 10**9,-(10**9)
mi1,ma1 = 10**9,-(10**9)
for i in range(n):
    a,b = map(int, input().split())
    c,d = a-b,a+b
    if c < mi0:
        mi0 = c
    if c > ma0:
        ma0 = c
    if d < mi1:
        mi1 = d
    if d > ma1:
        ma1 = d
print(max(ma0-mi0,ma1-mi1))

Submission status: Accepted

Solution code:
n = int(input())

top1= -10**10
bot1= 10**10
top2= -10**10
bot2= 10**10
for _ in range(n):
	
	x,y = map(int, input().split(' '))
	tot1= x+y
	tot2= x-y
	if tot1> top1:
		top1= tot1
	if tot1< bot1:
		bot1= tot1
	if tot2>top2:
		top2= tot2
	if tot2<bot2:
		bot2= tot2

print(max(top1-bot1, top2-bot2))

Submission status: Accepted

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

ans = 0
for i in range(2):
    ans = max(ans, max(d[i])-min(d[i]))
print(ans)

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.append(y)


ans = -float("inf")

left = -float("inf")
right = float("inf")
for i in range(N):
    left = max(left, X[i]-Y[i])
    right = min(right, X[i]-Y[i])

ans = max(ans, left - right)

left = -float("inf")
right = float("inf")
for i in range(N):
    left = max(left, X[i]+Y[i])
    right = min(right, X[i]+Y[i])

ans = max(ans, left - right)

print(ans)