Problem:


Score : 500 points

Problem Statement

There are N points on the 2D plane, i-th of which is located on (x_i, y_i).
There can be multiple points that share the same coordinate.
What is the maximum possible Manhattan distance between two distinct points?

Here, the Manhattan distance between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq x_i,y_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the answer.

Sample Input 1

3
1 1
2 4
3 2

Sample Output 1

4

The Manhattan distance between the first point and the second point is |1-2|+|1-4|=4, which is maximum possible.

Sample Input 2

2
1 1
1 1

Sample Output 2

0



Sample input:
3
1 1
2 4
3 2


Sample output:
4

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
zahyo = [l() for _ in range(N)]
zahyo2 = [sum(zahyo[i]) for i in range(N)]
zahyo3 = [zahyo[i][0]-zahyo[i][1] for i in range(N)]
ans = 0
print(max(max(zahyo2)-min(zahyo2),max(zahyo3)-min(zahyo3)))

Submission status: Accepted

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

f0 = [x - y for x, y in xy]
f1 = [x + y for x, y in xy]

f0.sort()
f1.sort()

ans = max((f0[-1] - f0[0]), (f1[-1] - f1[0]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
M = xy[0][0] + xy[0][1]
m = xy[0][0] - xy[0][1]
for x, y in xy[1:]:
    ans = max(ans, M-x-y, m-x+y)
    M = max(M, x+y)
    m = max(m, x-y)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

import itertools


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


def dx(p1, p2):
    return abs(p1[0] + p2[0]) // 2


def dy(p1, p2):
    return abs(p1[0] - p2[0]) // 2


def slow_solve(N, XYs):
    ans = 0
    for points in itertools.combinations(XYs, 2):
        ans = max(ans, d(points[0], points[1]))
    return ans


def solve(N, XYs):
    def transrate(XYs):
        return [(A[0] - A[1], A[0] + A[1]) for A in XYs]

    XYs = transrate(XYs)

    # x_max = max(XYs, key=lambda x: x[0])
    # x_min = min(XYs, key=lambda x: x[0])
    # tans = d(x_min, x_max)
    #
    # y_max = max(XYs, key=lambda x: x[1])
    # y_min = min(XYs, key=lambda x: x[1])
    # tans2 = d(y_min, y_max)

    def candidates():
        return [
            # max(XYs, key=lambda x: (x[0], x[1])),
            # max(XYs, key=lambda x: (x[0], -x[1])),
            # max(XYs, key=lambda x: (x[1], x[0])),
            # max(XYs, key=lambda x: (x[1], -x[0])),
            # max(XYs, key=lambda x: (-x[0], x[1])),
            # max(XYs, key=lambda x: (-x[0], -x[1])),
            # max(XYs, key=lambda x: (-x[1], x[0])),
            # max(XYs, key=lambda x: (-x[1], -x[0])),
            max(XYs, key=lambda x: x[0]),
            min(XYs, key=lambda x: x[0]),
            max(XYs, key=lambda x: x[1]),
            min(XYs, key=lambda x: x[1]),
        ]

    XYs.sort(key=lambda p: p[0], reverse=True)
    xmax = XYs[0][0] - XYs[-1][0]
    XYs.sort(key=lambda p: p[1], reverse=True)
    ymax = XYs[0][1] - XYs[-1][1]
    return max(xmax, ymax)
#
#
# assert (solve(4, [(5, 6), (6, 1), (6, 5), (4, 3)]) == 6)
#
# import random
#
#
# def create_rand(N):
#     X = 6
#     return [(random.randint(1, X), random.randint(1, X)) for _ in range(N)]
#
#
# N = 4
# for case in range(10000):
#     points = create_rand(N)
#     actual = solve(N, points)
#     expected = slow_solve(N, points)
#     if actual != expected:
#         print("NG!!!")
#         print(N)
#         print(points)
#         print(f"actual : {actual}")
#         print(f"expected : {expected}")
#         exit(0)
# print("OK")

if __name__ == "__main__":
    N = int(input())
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]

    print(solve(N, XYs))

Submission status: Accepted

Solution code:
import sys
r=sys.stdin.readline
N=int(r())
def md(x,y,a,b):
    return abs(x-a)+abs(y-b)
left_top=(0,0)
left_down=(0,0)
right_top=(0,0)
right_down=(0,0)
for i in range(N):
    x,y = map(int,r().split())
    if i==0:
        left_top=(x,y)
        left_down=(x,y)
        right_top=(x,y)
        right_down=(x,y)
    else:
        if md(0,0,left_down[0],left_down[1])>md(0,0,x,y):
            left_down=(x,y)
        if md(0,0,right_top[0],right_top[1])<md(0,0,x,y):
            right_top=(x,y)
        if right_down[0]-right_down[1]<x-y:
            right_down=(x,y)
        if left_top[1]-left_top[0]<y-x:
            left_top=(x,y)
a=md(left_down[0],left_down[1],right_top[0],right_top[1])
b=md(left_top[0],left_top[1],right_down[0],right_down[1])
print(max([a,b]))

Submission status: Accepted

Solution code:
import copy
n = int(input())

p1 = list(map(int,input().split()))
p2 = copy.copy(p1)
p3 = copy.copy(p1)
p4 = copy.copy(p1)

for i in range(n-1):

    p = list(map(int,input().split()))
    if p1[0]+p1[1] > p[0]+p[1]:
        p1 = copy.copy(p)

    if p4[0]+p4[1] < p[0]+p[1]:
        p4 = copy.copy(p)

    if p2[0]-p2[1] < p[0]-p[1]:
        p2 = copy.copy(p)

    if -p3[0]+p3[1] < -p[0]+p[1]:
        p3 = copy.copy(p)

print(max(p4[0]-p1[0]+p4[1]-p1[1], p2[0]-p3[0]+p3[1]-p2[1]))

Submission status: Accepted

Solution code:
#create date: 2020-09-13 22:30

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    amax = [0, 0]
    amin = [10**20, 10**20]
    for _ in range(n):
        x, y = na()
        amin[0] = min(amin[0], x+y)
        amax[0] = max(amax[0], x+y)
        amin[1] = min(amin[1], -x+y)
        amax[1] = max(amax[1], -x+y)
    print(max(amax[0]-amin[0], amax[1]-amin[1]))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
data = []
for i in range(n):
	x,y = readInts()
	data.append([x+y,x,y,x-y])
ans = 0
data.sort(key=lambda x:x[0])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[1])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[2])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[3])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
print(ans)

Submission status: Accepted

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


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

max_x = -2000000000
min_x = 2000000000
max_y = -2000000000
min_y = 2000000000
for xi, yi in p:
    f1, f2 = f(xi, yi)
    max_x = max(max_x, f1)
    min_x = min(min_x, f1)
    max_y = max(max_y, f2)
    min_y = min(min_y, f2)

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

Submission status: Accepted

Solution code:
Row=int(input())
X=[]
Y=[]
for i in range(Row):
    n,a=input().split()
    X.append(int(n))
    Y.append(int(a))
A=[]
B=[]
for i in range(len(X)):
    A.append(X[i]-Y[i])
    B.append(X[i]+Y[i])
maxmax1=A[0]
maxmax2=B[0]
minmin1=A[0]
minmin2=B[0]
for i in range(len(A)):
    maxmax1=max(maxmax1,A[i])
    minmin1=min(minmin1,A[i])
for i in range(len(B)):
    maxmax2=max(maxmax2,B[i])
    minmin2=min(minmin2,B[i])
print(max((maxmax1-minmin1),(maxmax2-minmin2)))

Submission status: Accepted

Solution code:
from itertools import combinations


def main():
    N = int(input())

    max_x = (float("-inf"), 0)
    min_x = (float("inf"), 0)

    max_y = (0, float("-inf"))
    min_y = (0, float("inf"))

    max_xy = (float("-inf"), 0)
    min_xy = (float("inf"), 0)

    max_yx = (0, float("-inf"))
    min_yx = (0, float("inf"))

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

        if x > max_x[0]:
            max_x = (x, y)
        if x < min_x[0]:
            min_x = (x, y)
        if y > max_y[1]:
            max_y = (x, y)
        if y < min_y[1]:
            min_y = (x, y)
        if x + y > max_xy[0] + max_xy[1]:
            max_xy = (x, y)
        if x + y < min_xy[0] + min_xy[1]:
            min_xy = (x, y)
        if y - x > max_yx[1] - max_yx[0]:
            max_yx = (x, y)
        if y - x < min_yx[1] - min_yx[0]:
            min_yx = (x, y)

    ans = 0
    for a, b in combinations(
        (max_x, min_x, max_y, min_y, max_xy, min_xy, max_yx, min_yx), 2):
        ans = max(ans, abs(a[0] - b[0]) + abs(a[1] - b[1]))

    print(ans)


main()

Submission status: Accepted

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

ans_1 = plus[-1]-plus[0]
ans_2 = abs(minus[-1]-minus[0])
print(max(ans_1,ans_2))

Submission status: Accepted

Solution code:
N = int(input())
v = [list(map(int, input().split())) for i in range(N)]
minx = min([v[i][0] for i in range(N)])
miny = min([v[i][1] for i in range(N)])
v.sort(key = lambda x:x[0] - minx + x[1] - miny)
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
result = d
v.sort(key = lambda x:x[0] - minx - (x[1] - miny))
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(max(d, result))

Submission status: Accepted

Solution code:
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
a,c,b,d=0,10**10,0,10**10
for i in range(n):
    y,x=r[i]
    a=max(a,x+y)
    c=min(c,x+y)
    b=max(b,x-y)
    d=min(d,x-y)
print(max(abs(a-c),abs(b-d)))

Submission status: Accepted

Solution code:
from operator import itemgetter

def sm(lis):
    return (lis[0]*2 + lis[1]**2)**0.5


def main():
    n = int(input())
    XY = [list(map(int,input().split())) for _ in range(n)]
    ans = 0
    a = [0,0]
    b = [0,0]
    c = [0,0]
    d = [0,0]
    y1 = 0
    y2 = 0
    x1 = 0
    x2 = 0
    for x,y in XY:
        if x >= x1:
            x1 = x
        if x <= x2:
            x2 = x
        if y >= y1:
            y1 = y
        if y <= y2:
            y2 = y
    a = [x1,y1]
    b = [x2,y1]
    c = [x2,y2]
    d = [x1,y2]
    Ans = []

            


    XY.sort(key = lambda xy:abs(xy[0] - a[0]) + abs(xy[1] - a[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])
    XY.sort(key = lambda xy:abs(xy[0] - b[0]) + abs(xy[1] - b[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    XY.sort(key = lambda xy:abs(xy[0] - c[0]) + abs(xy[1] - c[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    XY.sort(key = lambda xy:abs(xy[0] - d[0]) + abs(xy[1] - d[1]))
    Ans.append(XY[-1])
    Ans.append(XY[-2])

    for x,y in Ans:
        for xx,yy in Ans:
            ans  = max(abs(x - xx) + abs(y - yy),ans)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

ans = 0
tmp_M0 = -float("inf")
tmp_m0 = float("inf")
tmp_M1 = -float("inf")
tmp_m1 = float("inf")
for i in range(N):
    x,y =map(int, input().split())
    if x-y > tmp_M0:
        tmp_M0 = x-y
    if x-y < tmp_m0:
        tmp_m0 = x-y
    if x+y > tmp_M1:
        tmp_M1 = x+y
    if x+y < tmp_m1:
        tmp_m1 = x+y
    
    if max(tmp_M0-tmp_m0, tmp_M1-tmp_m1) > ans:
        ans = max(tmp_M0-tmp_m0, tmp_M1-tmp_m1)
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

z = [0]*n
w = [0]*n

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

a = max(z)
b = min(z)
c = max(w)
d = min(w)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]


N = int(input())

X, Y = [], []
for i in range(N):
    x, y = li()
    X.append(x)
    Y.append(y)


def maxAbsValExpr(arr1, arr2):
    maxVal = 0
    for x, y in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
        distances = [x * arr1[i] + y * arr2[i] for i in range(len(arr1))]
        maxVal = max(maxVal, max(distances) - min(distances))
    return maxVal

ans = maxAbsValExpr(X, Y)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y

    if x+y > summax:
        summax = x+y
    if x+y < summin:
        summin = x+y
    if x-y > diffmax:
        diffmax = x-y
    if x-y < diffmin:
        diffmin = x-y

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)

Submission status: Accepted

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

def main():
    input = sys.stdin.readline
    n = int(input())
    Z = []
    W = []
    for _ in range(n):
        x, y = map(int, input().split())
        z = x + y
        w = x - y
        Z.append(z)
        W.append(w)
    Z.sort()
    W.sort()
    print(max(abs(Z[0] - Z[-1]), abs(W[0] - W[-1])))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, *xy = map(int, open(0).read().split())
    f = [(i - j, i + j) for i, j in zip(xy[::2], xy[1::2])]

    a = max(x[0] for x in f)
    b = min(x[0] for x in f)

    c = max(x[1] for x in f)
    d = min(x[1] for x in f)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []

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

aa = max(a)-min(a)
bb = max(b)-min(b)

if aa >= bb:
    print(aa)
else:
    print(bb)

Submission status: Accepted

Solution code:
n = int(input())
p = []
m = []

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

mnp = min(p)
mxp = max(p)
mnm = min(m)
mxm = max(m)

res = [mxp-mnp, mxm-mnm, mnm, mxm, mnp-mxp]
print(max(res))

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())

L1=[0 for _ in range(N)]
L2=[0 for _ in range(N)]
for i in range(N):
    x,y=map(int,input().split())
    L1[i],L2[i]=x-y,x+y


mi1=min(L1)
ma1=max(L1)
mi2=min(L2)
ma2=max(L2)

ans=max(ma1-mi1,ma2-mi2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

max1 = -1 * (10 ** 10)
min1 = 10 ** 10
max0 = -1 * (10 ** 10)
min0 = 10 ** 10

for i in range(n):
    x,y = list(map(int,input().split()))
    k0 = x - y
    k1 = x + y
    if k0 > max0:
        max0 = k0
    if k0 < min0:
        min0 = k0
    if k1 > max1:
        max1 = k1
    if k1 < min1:
        min1 = k1


ans = int(max(max1-min1,max0-min0))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

max_1 = -float('inf')
min_1 = float('inf')

max_2 = -float('inf')
min_2 = float('inf')

for a, b in lst:
    max_1 = max(max_1, a - b)
    min_1 = min(min_1, a - b)

    max_2 = max(max_2, a + b)
    min_2 = min(min_2, a + b)


ans = max(max_1 - min_1, max_2 - min_2)

print(ans)

Submission status: Accepted

Solution code:
def ii(): return int(input())


def mi(): return map(int, input().split())


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


n = ii()

ps = []

xmin = (1e9, 0)
xmax = (-1e9, 0)
ymin = (0, 1e9)
ymax = (0, -1e9)

for _ in range(n):
    x, y = mi()
    ps.append((x, y))

l1 = list(sorted(ps, key=lambda p: p[0] + p[1]))
l2 = list(sorted(ps, key=lambda p: p[0] - p[1]))


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


a1 = d(l1[0], l1[n-1])
a2 = d(l2[0], l2[n-1])

print(max(a1, a2))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    xy = [0] * N
    d = {}
    offset = 0
    mina = 10 ** 9
    minb = 2 * (10 ** 9 + 1)
    maxa = -10 ** 9 -1
    maxb = 2
    for n in range(N):
        x, y = [int(x) for x in input().strip().split()]
        if (x, y) in d:
            offset += 1
            continue
        d[(x, y)] = 1
        a, b = y - x, y + x
        xy[n-offset] = (x, y, a, b)
        mina = min(mina, a)
        minb = min(minb, b)
        maxa = max(maxa, a)
        maxb = max(maxb, b)
    # print(mina, maxa, minb, maxb)
    print(max(maxa-mina, maxb-minb))

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)
print(max(max(a)-min(a), max(b)-min(b)))

Submission status: Accepted

Solution code:
N = int(input())

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

ans_max_p = 0
ans_min_p = 2*10**9+1
ans_max_n = 0
ans_min_n = 2*10**9+1
ans = 0

for i in range(N):
    ans_min_p = min(ans_min_p, x_list[i] + y_list[i])
    ans_max_p = max(ans_max_p, x_list[i] + y_list[i])
    ans_min_n = min(ans_min_n, -1*x_list[i] + y_list[i])
    ans_max_n = max(ans_max_n, -1*x_list[i] + y_list[i])
    
ans_p = ans_max_p - ans_min_p
ans_n = ans_max_n - ans_min_n
ans = max(ans_p, ans_n)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n)]

a = 2*10**9+5
b = -2*10**9+5
c = 2*10**9+5
d = -2*10**9+5

for i in range(n):
    a = min(a, C[i][0]+C[i][1])
    b = max(b, C[i][0]+C[i][1])
    c = min(c, C[i][0]-C[i][1])
    d = max(d, C[i][0]-C[i][1])

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

Submission status: Accepted

Solution code:
n = int(input())
pp = []
pm = []
mp = []
mm = []

for i in range(n):
    x, y = list(map(int, input().split()))
    pp.append(x + y)
    pm.append(x - y)
    mp.append(-x + y)
    mm.append(-x - y)

max_pp = max(pp)
min_pp = min(pp)
max_pm = max(pm)
min_pm = min(pm)
max_mp = max(mp)
min_mp = min(mp)
max_mm = max(pm)
min_mm = min(pm)

max_val = max(max_pp - min_pp, max_pm - min_pm, max_mp - min_mp, max_mm - min_mm)
print(max_val)

Submission status: Accepted

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

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)

mnp=min(a)
mxp=max(a)
mnm=min(b)
mxm=max(b)

res=[mxp-mnp,mxm-mnm,mnm,mxm,mnp-mxp]
print(max(res))

Submission status: Accepted

Solution code:
n = int(input())
x,y = map(int,input().split())
max_xpy = x+y
min_xpy = x+y
max_xmy = x-y
min_xmy = x-y
for i in range(n-1):
  x,y = map(int,input().split())
  max_xpy = max(max_xpy,x+y)
  min_xpy = min(min_xpy,x+y)
  max_xmy = max(max_xmy,x-y)
  min_xmy = min(min_xmy,x-y)
print(max(max_xpy-min_xpy,max_xmy-min_xmy))

Submission status: Accepted

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

Submission status: Accepted

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

def s(points, k, l):
    np = list(map(lambda arg:  k*arg[0] + l*arg[1], points))
    return abs(max(np)-min(np))

def solve(N: int, x: "List[int]", y: "List[int]"):
    points = list(zip(x, y))
    print(max([
            s(points, +1, +1),
            s(points, -1, -1),
            s(points, +1, -1),            
            s(points, -1, +1),            
    ]))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
D=0
d=10**10
f=10**10
F=-10**10
for i in range(n):
    x,y=[int(x) for x in input().split()]
    l=x+y
    d=min(d,l)
    D=max(D,l)
    if y-x<f:
        m=[x,y]
        f=y-x
    if y-x>F:
        M=[x,y]
        F=y-x
e=abs(m[0]-M[0])+abs(m[1]-M[1])
ans=max(D-d,e)
print(ans)

Submission status: Accepted

Solution code:

n=int(input())
lx=[]
ly=[]
for i in range(n):
  x,y=map(int,input().split())
  lx.append(x+y)
  ly.append(x-y)
ax,bx,ay,by=max(lx),min(lx),max(ly),min(ly)
print(max(ax-bx,ay-by))

Submission status: Accepted

Solution code:
N = int(input())
Y_MAX = 0
X_MAX = 0
Y_MIN = 1000000000000
X_MIN = 1000000000000

for i in range(N):
    x, y = map(int, input().split())
    if abs(0 - x) + abs(y - 1000000000000) > Y_MAX:
        Y_MAX = abs(0 - x) + abs(y - 1000000000000)
    if abs(0 - x) + abs(y - 1000000000000) < Y_MIN:
        Y_MIN = abs(0 - x) + abs(y - 1000000000000)
    if abs(0 - x) + abs(0 - y) > X_MAX:
        X_MAX = abs(0 - x) + abs(0 - y)
    if abs(0 - x) + abs(0 - y) < X_MIN:
        X_MIN = abs(0 - x) + abs(0 - y)

print(max(Y_MAX - Y_MIN, X_MAX - X_MIN))

Submission status: Accepted

Solution code:
import sys
N=int(sys.stdin.readline().strip())
XY=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
X=[]
Y=[]
for x,y in XY:
    X.append(x-y)
    Y.append(x+y)
X.sort()
Y.sort()
print max(abs(X[0]-X[-1]),abs(Y[0]-Y[-1]))

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    x, y = MI()
    x1 = x
    x2 = x
    x3 = x
    x4 = x
    y1 = y
    y2 = y
    y3 = y
    y4 = y
    for _ in range(n-1):
        x, y = MI()
        if x+y > x1+y1:
            x1 = x
            y1 = y
        if -x+y > -x2+y2:
            x2 = x
            y2 = y
        if -x-y > -x3-y3:
            x3 = x
            y3 = y
        if x-y > x4-y4:
            x4 = x
            y4 = y
    temp = [abs(x1-x2)+abs(y1-y2), abs(x1-x3)+abs(y1-y3), abs(x1-x4)+abs(y1-y4), abs(x2-x3)+abs(y2-y3), abs(x2-x4)+abs(y2-y4), abs(x3-x4)+abs(y3-y4)]
    ans = max(temp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
if x1+y1 > x2+y2:
    max1 = x1+y1
    min1 = x2+y2
else:
    max1 = x2+y2
    min1 = x1+y1

if x1-y1 > x2-y2:
    max2 = x1-y1
    min2 = x2-y2
else:
    max2 = x2-y2
    min2 = x1-y1

for i in range(N-2):
    x, y = map(int, input().split())
    if x+y > max1:
        max1 = x+y
    elif x+y < min1:
        min1 = x+y
    
    if x-y > max2:
        max2 = x-y
    elif x-y < min2:
        min2 = x-y


ans = print(max((max1-min1),(max2-min2)))

Submission status: Accepted

Solution code:
N=int(input())

P=[tuple(map(int,input().split())) for _ in [0]*N]

xM,yM,xm,ym=-3*10**9,-3*10**9,-3*10**9,-3*10**9
xM_list,xm_list,yM_list,ym_list=[],[],[],[]

for i in range(N):
    x,y=P[i]
    nr=(x+y,x-y,-x+y,-x-y)
    
    if xM<nr[0]:
        xM=nr[0]
        xM_list=[P[i]]
    elif xM==nr[0]:
        xM_list.append(P[i])
    if xm<nr[1]:
        xm=nr[1]
        xm_list=[P[i]]
    elif xm==nr[1]:
        xm_list.append(P[i])
    if yM<nr[2]:
        yM=nr[2]
        yM_list=[P[i]]
    elif yM==nr[2]:
        yM_list.append(P[i])
    if ym<nr[3]:
        ym=nr[3]
        ym_list=[P[i]]
    elif ym==nr[3]:
        ym_list.append(P[i])

xm_list.sort(lambda x:x[1])
xM_list.sort(lambda x:x[1])
ym_list.sort(lambda x:x[0])
yM_list.sort(lambda x:x[0])

# print(xm_list,xM_list,ym_list,yM_list)
goodP=[]

if len(xm_list)>1:
    goodP.append(xm_list[-1])
    goodP.append(xm_list[0])
else:
    goodP.append(xm_list[0])
if len(xM_list)>1:
    goodP.append(xM_list[-1])
    goodP.append(xM_list[0])
else:
    goodP.append(xM_list[0])
if len(ym_list)>1:
    goodP.append(ym_list[-1])
    goodP.append(ym_list[0])
else:
    goodP.append(ym_list[0])
if len(yM_list)>1:
    goodP.append(yM_list[-1])
    goodP.append(yM_list[0])
else:
    goodP.append(yM_list[0])

res=[]
for i in range(len(goodP)):
    for j in range(len(goodP)):
        if not i<j:
            continue
        res.append(abs(goodP[i][0]-goodP[j][0])+abs(goodP[i][1]-goodP[j][1]))
print(max(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]

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

aaa=min(a)
aaaa=max(a)
bbb=min(b)
bbbb=max(b)

ans=[]

ans.append(aaaa-aaa)
ans.append(bbbb-bbb)
ans.append(bbb)
ans.append(bbbb)
ans.append(aaa-aaaa)

res=max(ans)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p = sorted(p, key=lambda i: i[0] + i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = abs((x1 + y1) - (x2 + y2))
p = sorted(p, key=lambda i: i[0] - i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = max(abs((x1 - y1) - (x2 - y2)), res)
print(res)

Submission status: Accepted

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

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


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


n = I()

points = set()
hmin = 10 ** 9
wmin = 10 ** 9
hmax = -(10 ** 9)
wmax = -(10 ** 9)
for _ in range(n):
    x, y = MI()
    points.add((x, y))
    hmin = min(hmin, y)
    hmax = max(hmax, y)
    wmin = min(wmin, x)
    wmax = max(wmax, x)

max_dist = manhattan((wmin, hmin), (wmax, hmax))
hs = max_dist
ms = max_dist
mu = max_dist
hu = max_dist
for p in points:
    hs = min(hs, manhattan((wmin, hmin), p))
    ms = min(ms, manhattan((wmax, hmin), p))
    mu = min(mu, manhattan((wmax, hmax), p))
    hu = min(hu, manhattan((wmin, hmax), p))

print(max_dist - min(hs + mu, hu + ms))

Submission status: Accepted

Solution code:
N = int(input())

M = 10**9

x,y = map(int, input().split())
r = (x,y)
l = (x,y)
u = (x,y)
d = (x,y)

for i in range(N-1):
    x,y = map(int, input().split())
    if abs(x-0)+abs(y-0)<abs(l[0]-0)+abs(l[1]-0):
        l = (x,y)
    if abs(x-M)+abs(y-0)<abs(r[0]-M)+abs(r[1]-0):
        r = (x,y)
    if abs(x-0)+abs(y-M)<abs(u[0]-0)+abs(u[1]-M):
        u = (x,y)
    if abs(x-M)+abs(y-M)<abs(d[0]-M)+abs(d[1]-M):
        d = (x,y)

print(max(
    abs(l[0]-r[0])+abs(l[1]-r[1]),
    abs(l[0]-u[0])+abs(l[1]-u[1]),
    abs(l[0]-d[0])+abs(l[1]-d[1]),
    abs(r[0]-u[0])+abs(r[1]-u[1]),
    abs(r[0]-d[0])+abs(r[1]-d[1]),
    abs(u[0]-d[0])+abs(u[1]-d[1]),
))

Submission status: Accepted

Solution code:
N = int(input())
x = [] * N
y = [] * N
for i in range(N):
    a, b = list(map(int, input().split()))
    x.append(a)
    y.append(b)
d = 0
ma = x[0] + y[0]
ima = 0
mi = x[0] + y[0]
imi = 0
for i in range(N):
    if x[i] + y[i] < mi:
        mi = x[i] + y[i]
        imi = i
    if x[i] + y[i] > ma:
        ma = x[i] + y[i]
        ima = i
d1 = abs(x[ima] - x[imi]) + abs(y[ima] - y[imi])
ma = - x[0] + y[0]
ima2 = 0
mi = - x[0] + y[0]
imi2 = 0
for i in range(N):
    if -x[i] + y[i] < mi:
        mi = -x[i] + y[i]
        imi2 = i
    if -x[i] + y[i] > ma:
        ma = -x[i] + y[i]
        ima2 = i
d2 = abs(x[ima2] - x[imi2]) + abs(y[ima2] - y[imi2])
if d1 > d2:
    print(d1)
else:
    print(d2)

Submission status: Accepted

Solution code:
def main():
    point_count = int(input())
    inf = 10 ** 10
    max_sum, min_sum, max_diff, min_diff = - inf, inf,  - inf, inf
    for _ in range(point_count):
        x, y = [int(x) for x in input().split()]
        max_sum = max(x + y, max_sum)
        min_sum = min(x + y, min_sum)
        max_diff = max(x - y, max_diff)
        min_diff = min(x - y, min_diff)
    return max(max_sum - min_sum, max_diff - min_diff)


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

Submission status: Accepted

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

i_maxu = None
i_minu = None
maxu = None
minu = None
i_maxv = None
i_minv = None
maxv = None
minv = None
for i,(u,v) in enumerate(tra):
    if maxu is None or u > maxu:
        maxu = u
        i_maxu = i
    if maxv is None or v > maxv:
        maxv = v
        i_maxv = i
    if minu is None or u < minu:
        minu = u
        i_minu = i
    if minv is None or v < minv:
        minv = v
        i_minv = i

if maxu - minu > maxv - minv:
    i,j = i_minu,i_maxu
else:
    i,j = i_minv,i_maxv

x1,y1 = ori[i]
x2,y2 = ori[j]
print( abs(x1-x2) + abs(y1-y2) )

Submission status: Accepted

Solution code:
N = int(input())
A = 0
Xmin = Ymin = 3e9 + 5
Xmax = Ymax = -3e9 - 5
for _ in range(N):
    x, y = map(int, input().split())
    X = x + y
    Y = x - y
    Xmin = min(Xmin, X)
    Xmax = max(Xmax, X)
    Ymin = min(Ymin, Y)
    Ymax = max(Ymax, Y)
if Xmin == 3e9 + 5:
    Xmin = Xmax
if Ymin == 3e9 + 5:
    Ymin = Ymax
if Xmax == -3e9 - 5:
    Xmax = Xmin
if Ymax == -3e9 -5:
    Ymax = Ymin
Z = max(Xmax - Xmin, Ymax - Ymin)
print(Z)

Submission status: Accepted

Solution code:
N = int(input())
points = [list(map(int, input().split())) for _ in range(N)]
INF = 10**10
xmax = -INF
xmin = INF
ymax = -INF
ymin = INF
for x, y in points:
  minus = x-y
  plus = x+y
  xmax = max(xmax, minus)
  xmin = min(xmin, minus)
  ymax = max(ymax, plus)
  ymin = min(ymin, plus)
print(max(xmax-xmin, ymax-ymin))

Submission status: Accepted

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

print(max(max(xy_1) - min(xy_1), max(xy_2)-min(xy_2)))

Submission status: Accepted

Solution code:
n = int(input().rstrip())
xmax = -10_000_000_000
xmin = 10_000_000_000
ymax = -10_000_000_000
ymin = 10_000_000_000
for i in range(n):
    x, y = map(int,input().split())
    xpy = x+y
    xmy = x-y
    xmax = max(xpy,xmax)
    xmin = min(xpy,xmin)
    ymax = max(xmy,ymax)
    ymin = min(xmy,ymin)
print(max(xmax-xmin,ymax-ymin))