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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()


da = []
daa = []

for i in range(n):
    x,y = m()

    da.append([x+y,x,y])
    daa.append([x-y,x,y])

da.sort()
daa.sort()

print(max(abs(da[0][0]-da[-1][0]),abs(daa[0][0]-daa[-1][0])))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
xy = [tuple(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x: x[0] + x[1])
a = xy[0]
xy.sort(key=lambda x: x[0] - x[1])
b = xy[0]
xy.sort(key=lambda x: -x[0] + x[1])
c = xy[0]
xy.sort(key=lambda x: -x[0] - x[1])
d = xy[0]

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

ans = 0
ans = max(ans, man(a, b))
ans = max(ans, man(a, c))
ans = max(ans, man(a, d))
ans = max(ans, man(b, c))
ans = max(ans, man(b, d))
ans = max(ans, man(d, d))
print(ans)

Submission status: Accepted

Solution code:
xy = []
xy2 = []

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

min_xy = min(xy)
max_xy = max(xy)
min_xy2 = min(xy2)
max_xy2 = max(xy2)

ans = max(max_xy - min_xy, min_xy2 - max_xy2, max_xy2 - min_xy2, min_xy - max_xy)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
point_list = []

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

max1 = [point_list[0][0] + point_list[0][1], 0]
min1 = [point_list[0][0] + point_list[0][1], 0]
max2 = [point_list[0][0] - point_list[0][1], 0]
min2 = [point_list[0][0] - point_list[0][1], 0]

for i in range(1, n):
    sum1 = point_list[i][0] + point_list[i][1]
    sum2 = point_list[i][0] - point_list[i][1]
    if sum1 > max1[0]:
        max1 = [sum1, i]
    
    if sum1 < min1[0]:
        min1 = [sum1, i]

    if sum2 > max2[0]:
        max2 = [sum2, i]
    
    if sum2 < min2[0]:
        min2 = [sum2, i]
    
man1 = abs(point_list[max1[1]][0]-point_list[min1[1]][0]) + abs(point_list[max1[1]][1]-point_list[min1[1]][1])
man2 = abs(point_list[max2[1]][0]-point_list[min2[1]][0]) + abs(point_list[max2[1]][1]-point_list[min2[1]][1])

ans = max([man1, man2])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=[];ans2=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append(a+b)
    ans2.append(10**9+1-a+b)
print(max( max(ans)-min(ans), max(ans2)-min(ans2)))

Submission status: Accepted

Solution code:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def solve():
    n = getN()

    points = [getList() for i in range(n)]

    inf = 10 ** 10

    org = []
    far = []
    for x, y in points:
        org.append(x + y)
        far.append(y + inf-x)

    org.sort()
    far.sort()

    a1 = abs(org[0] - org[-1])
    a2 = abs(far[0] - far[-1])

    ans = max(a1, a2)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    N = int(input())
    X = set()
    Y = {}
    for _ in range(N):
        x, y = map(int, input().split())
        X.add(x)
        if x not in Y:
            Y[x] = {y}
        else:
            Y[x].add(y)
    X = sorted(list(X))
    NX = len(X)
    for x in X:
        Y[x] = sorted(list(Y[x]))

    ymin = Y[X[0]][0]
    ymax = Y[X[0]][-1]
    ans = 0
    for i in range(1, NX):
        x = X[i]
        dx = X[i] - X[i-1]
        ymin_new = Y[x][0]
        ymax_new = Y[x][-1]
        ans = max(ans, ymax - ymin_new + dx, ymax_new - ymin + dx)
        ymax = max(ymax + dx, ymax_new)
        ymin = min(ymin - dx, ymin_new)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

ans1 = []
ans2 = []
max_xy = 10**9
for _ in range(n):
    x, y = na()
    ans1.append(x+y)
    ans2.append((max_xy-x)+y)

print(max(max(ans1) - min(ans1), max(ans2) - min(ans2)))

Submission status: Accepted

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

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

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

cand = []
for i in (-1,0,1):
    for j in (-1,0,1):
        best = -10 ** 9
        bestP = (0,0)
        for p in points:
            val = i * p[0] + j * p[1]
            if val > best:
                best = val
                bestP = p
        cand.append(bestP)
                
best = 0
for i in cand:
    for p in points:
       best = max(best,dist(i,p))
print(best)

Submission status: Accepted

Solution code:
def main():
    import sys
    N=int(sys.stdin.readline())

    xpy=[]
    xmy=[]

    for i in range(N):
        x,y=list(map(int,sys.stdin.readline().split()))
        xpy.append(x+y)
        xmy.append(x-y)

    t1=max(xpy)-min(xpy)
    t2=max(xmy)-min(xmy)

    print(max(t1,t2))

main()

Submission status: Accepted

Solution code:
#import
#import math
#import numpy as np
N = int(input())
XY= [list(map(int, input().split())) for _ in range(N)]

pmaxint = -10**10
pminint = 10**10
mmaxint = -10**10
mminint = 10**10

for x, y in XY:
    t1 = x + y
    t2 = x - y
    if t1 > pmaxint:
        pmaxint = t1
    if t1 < pminint:
        pminint = t1
    
    if t2 > mmaxint:
        mmaxint = t2
    if t2 < mminint:
        mminint = t2

print(max(abs(pmaxint - pminint), abs(mmaxint - mminint)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

inf = 10**15
axis_p_max = -1 * inf
axis_p_min = inf
axis_m_max = -1 * inf
axis_m_min = inf

it = iter(data)
for x,y in zip(it,it):
    axis_p_max = max(axis_p_max, x+y)
    axis_p_min = min(axis_p_min, x+y)
    axis_m_max = max(axis_m_max, x-y)
    axis_m_min = min(axis_m_min, x-y)

ans = max(axis_p_max-axis_p_min, axis_m_max-axis_m_min)
print(ans)

Submission status: Accepted

Solution code:
def func(x, y):
    res, n = 0, len(x)
    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)
    return res

n = int(input())
x,y = [],[]
for i in range(n):
    a,b = list(map(int,input().split()))
    x.append(a)
    y.append(b)
print(func(x,y))

Submission status: Accepted

Solution code:
sumi=[]
diff=[]
t=int(input())
for _ in range(t):
  z=list(map(int,input().split()))
  sumi.append(z[0]+z[1])
  diff.append(z[0]-z[1])
print (max(max(diff)-min(diff),max(sumi)-min(sumi)))

Submission status: Accepted

Solution code:

n = int(input())

l1 = []
l2 = []

for i in range(n):
    x1,y1 = map(int,input().split())
    l1.append(x1-y1)
    l2.append(x1+y1)

l1 = sorted(l1)
l2 = sorted(l2)
a = l1[-1]
b = l1[0]
c = l2[-1]
d = l2[0]
ans = max(a-b, c-d)
print(ans)

Submission status: Accepted

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

xy.sort()

xy2 = [(x-y,x+y) for x,y in xy]

xd, yd = zip(*xy2)

dx = max(xd) - min(xd)
dy = max(yd) - min(yd)
print(max(dx,dy))

Submission status: Accepted

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
ans = 0
ma1, mi1 = -10000000000, 10000000000
ma2, mi2 = -10000000000, 10000000000
for i in range(n):
    x = s[i][0] + s[i][1]
    y = s[i][0] - s[i][1]
    ma1 = max(ma1, x)
    mi1 = min(mi1, x)
    ma2 = max(ma2, y)
    mi2 = min(mi2, y)
    ans = max(ans, ma1 - mi1, ma2 - mi2)
print(ans)

Submission status: Accepted

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

xy1 = []
xy2 = []

for x,y in xy:
    xy1.append(x+y)
    xy2.append(x-y)

xy1.sort()
xy2.sort()

print(max(xy1[-1] - xy1[0], xy2[-1] - xy2[0]))

Submission status: Accepted

Solution code:
num = int(input())
sumList = [0] * num
minusList = [0] * num
for id in range(num):
    x, y = map(int, input().split())
    sumList[id-1] = x + y
    minusList[id-1] = x - y
sumMax = max(sumList) - min(sumList)
minusMax = max(minusList) - min(minusList)
print(max(sumMax, minusMax))

Submission status: Accepted

Solution code:
import sys


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

AM, Am, BM, Bm = -1*10**9*2, 10**9*2, -1*10**9*2, 10**9*2
for _ in range(N):
    x, y = map(int, input().split())
    AM = max(AM, x+y)
    Am = min(Am, x+y)
    BM = max(BM, x-y)
    Bm = min(Bm, x-y)


print(max(AM-Am, BM-Bm))

Submission status: Accepted

Solution code:
N = int(input())
xpy = [0]*N
xmy = [0]*N
for i in range(N):
  x,y = map(int, input().split())
  xpy[i] = x+y
  xmy[i] = x-y
xpy.sort()
xmy.sort()
print(max(xpy[-1]-xpy[0],xmy[-1]-xmy[0]))

Submission status: Accepted

Solution code:
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase

def main():
    n = int(input())
    maxi_pl = 0
    mini_pl = 10**10
    maxi_mi = -10**10
    mini_mi = 10**10
    for _ in range(n):
        x,y = map(int,input().split())
        maxi_pl = max(maxi_pl,x+y)
        mini_pl = min(mini_pl,x+y)
        maxi_mi = max(maxi_mi,x-y)
        mini_mi = min(mini_mi,x-y)
    print(max(maxi_pl-mini_pl,maxi_mi-mini_mi))

#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

a, b = map(int, input().split())
mini = a+b
maxi = a+b

mini1 = a-b
maxi1 = a-b

for i in range(n-1):
    a, b = map(int, input().split())
    
    mini = min(a+b, mini)
    maxi = max(a+b, maxi)
    mini1 = min(a-b, mini1)
    maxi1 = max(a-b, maxi1)
    
ans = max(maxi-mini, maxi1-mini1)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

ans=[]
ans1=[]

for _ in range(n):
  a,b=map(int,input().split())
  d=a-b
  c=a+b
  ans.append(c)
  ans1.append(d)
  
m=min(ans)
M=max(ans)

P=M-m
Q=max(ans1)-min(ans1)

print(max(P,Q))

Submission status: Accepted

Solution code:
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
L_1 = [l[0]+l[1] for l in L]
L_2 = [(10**9+1-l[0])+l[1] for l in L]
L_3 = [(10**9+1-l[1])+l[0] for l in L]
L_4 = [(10**9+1-l[0])+(10**9+1-l[1]) for l in L]
L_1.sort()
a = L_1[-1]-L_1[0]
L_2.sort()
b = L_2[-1]-L_2[0]
L_3.sort()
c = L_3[-1]-L_3[0]
L_4.sort()
d = L_4[-1]-L_4[0]
print(max(a,b,c,d))

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    n = ii()
    L = []
    for _ in range(n):
        x, y = mi()
        L.append((x - y, x + y))
    
    candidate = []
    for d in range(2):
        M = max(map(lambda x: x[d], L))
        m = min(map(lambda x: x[d], L))
        candidate.append(M - m)

    print(max(candidate))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    X = [] # x+y
    Y = [] # x-y
    for i in range(N):
        x,y=mi()
        X.append(x+y)
        Y.append(x-y)
    
    X.sort()
    Y.sort()
    ans = max(X[-1]-X[0],Y[-1]-Y[0])

    print(ans)







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n = int(input())
#XY = [0]*n
Z = [0]*n
W = [0]*n
for i in range(n):
    x, y = map(int, input().split())
    #XY[i] = (x, y)
    Z[i] = x+y
    W[i] = x-y

Z.sort()
W.sort()
#print(Z)
#print(W)
maxz = Z[-1]-Z[0]
maxw = W[-1]-W[0]
ans = max(maxw, maxz)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n=I()

A1=[]
A2=[]
for i in range(n):
    x,y=LI()
    A1+=[x+y]
    A2+=[x-y]

ans=max(max(A1)-min(A1),max(A2)-min(A2))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
num=[list(map(int,input().split())) for _ in range(n)]
n1=[]
num1=10**9
ans=0
for i in range(n):
    n1.append(num[i][0]+num[i][1])
ans=max(ans,max(n1)-min(n1))
n1=[]
for i in range(n):
    n1.append(num1-num[i][0]+num[i][1])
ans=max(ans,max(n1)-min(n1))
print(ans)

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N = int(input())
    R = [tuple(map(int, input().split())) for i in range(N)]
    A = sorted(R, key = lambda x: x[0] + x[1])
    B = sorted(R, key = lambda x: x[0] - x[1])
    a = abs(A[-1][0] - A[0][0]) + abs(A[-1][1] - A[0][1])
    b = abs(B[-1][0] - B[0][0]) + abs(B[-1][1] - B[0][1])
    print(max(a, b))
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

p = [0] * N
m = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    p[i] = x + y
    m[i] = x - y

pm = max(p) - min(p)
mm = max(m) - min(m)

print(max(pm, mm))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xy = [list(map(int, input().split())) for _ in [0]*n]
    z1 = [x+y for x, y in xy]
    z2 = [x-y for x, y in xy]
    z3 = [-x+y for x, y in xy]
    z4 = [-x-y for x, y in xy]
    print(max([max(z1)-min(z1), max(z2)-min(z2),
               max(z3)-min(z3), max(z4)-min(z4)]))


main()

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
d1, d2, d3, d4 = [[] for _ in range(4)]
for a, b in xy:
    d1.append(a + b)
    d2.append(a - b)
    d3.append(-a + b)
    d4.append(-a - b)
ans = 0
for d in d1, d2, d3, d4:
    ans = max(ans, max(d) - min(d))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

xy=[[int(_) for _ in input().split()]for i in range(n)]

print(max(max([a[0]+a[1] for  a in xy])-min([a[0]+a[1] for  a in xy]),max([a[0]-a[1] for  a in xy])-min([a[0]-a[1] for  a in xy])))
# print(max([a[0]-a[1] for  a in xy])-min([a[0]-a[1] for  a in xy]))

Submission status: Accepted

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

ans1 = []
ans2 = []
for i in range(n):
    x, y = info[i]
    ans1.append(x + y)
    ans2.append(x - y)
    
ans1 = sorted(ans1)
ans2 = sorted(ans2)
ans = max(abs(ans1[0] - ans1[-1]), abs(ans2[0] - ans2[-1]))
print(ans)

Submission status: Accepted

Solution code:
# by the authority of GOD
import os,sys
from io import BytesIO, IOBase


def maxAbsValExpr(arr1,arr2) :
    minX, maxX = min(arr1), max(arr1)
    minY, maxY = min(arr2), max(arr2)

    ans = 0
    for point in [(minX, minY), (maxX, minY), (minX, maxY), (maxX, maxY)]:
        minD = float('inf')
        maxD = float('-inf')
        for i in range(0, len(arr1)):
            distance = abs(arr1[i] - point[0]) + abs(arr2[i] - point[1])
            minD = min(minD, distance)
            maxD = max(maxD, distance)
        ans = max(ans, maxD - minD)
    return ans
def main():
    x=[]
    y=[]
    for i in range(int(input())):

        a,b =map(int,input().split())
        x.append(a)
        y.append(b)
    print(maxAbsValExpr(x,y))
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
import sys
sys.setrecursionlimit(2*10**5)
from random import randint
def lis():
    return list(sep())

def maxAbsValExpr(x, y):
    res, n = 0, len(y)
    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 =   q * y[i] + p * x[i]
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res
n=int(input())
x=[]
y=[]
for _ in range(n):
    a,b=sep()
    x.append(a)
    y.append(b)
print(maxAbsValExpr(x,y))

Submission status: Accepted

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

def dist(A, B):
	return abs(A[0]-B[0]) + abs(A[1]-B[1])

N = INT()
xy = [LIST()+[i] for i in range(N)]

xy1 = [[xy[i][0]+xy[i][1], i] for i in range(N)]
xy1.sort(key=lambda x:x[0])
idx_a = xy1[0][1]
idx_b = xy1[-1][1]
a = xy[idx_a]
b = xy[idx_b]

xy2 = [[-xy[i][0]+xy[i][1], i] for i in range(N)]
xy2.sort(key=lambda x:x[0])
idx_c = xy2[0][1]
idx_d = xy2[-1][1]
c = xy[idx_c]
d = xy[idx_d]

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

Submission status: Accepted

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

INF = 10**18

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

XY.sort()

ans = 0
x0, y0 = XY[0]
m1 =  -x0+y0# 今ままでのmax
m2 = x0+y0
for x, y in XY:
    ans = max(ans, x+m1 - y)
    ans = max(ans, y - (-x+m2))
    m1 = max(m1, -x+y)
    m2 = min(m2, x+y)
print(ans)

Submission status: Accepted

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

minus.sort()
plus.sort()

ans = 0
for x, y in coords:
    now_minus, now_plus = x-y, x+y
    ans = max(ans, abs(now_minus-minus[0]), abs(now_minus-minus[-1]))
    ans = max(ans, abs(now_plus-plus[0]), abs(now_plus-plus[-1]))

print(ans)

Submission status: Accepted

Solution code:
n,*z=map(int,open(0).read().split())
a,b=[],[]
for x,y in zip(*[iter(z)]*2):
    a+=x+y,
    b+=x-y,
print(max(abs(max(a)-min(a)),abs(max(b)-min(b))))

Submission status: Accepted

Solution code:
n = int(input())

X_min = float("inf")
X_max = -float("inf")
Y_min = float("inf")
Y_max = -float("inf")

for _ in range(n):
    x, y = map(int, input().split())
    X = x - y
    Y = x + y
    X_min = min(X_min, X)
    X_max = max(X_max, X)
    Y_min = min(Y_min, Y)
    Y_max = max(Y_max, Y)

print(max(X_max-X_min, Y_max-Y_min))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

MAX_P = 0
MIN_P = 10 ** 10
MAX_M = -(10 ** 10)
MIN_M = 10 ** 10

for x, y in XY:
    P = x + y
    M = x - y

    MAX_P = max(MAX_P, P)
    MIN_P = min(MIN_P, P)

    MAX_M = max(MAX_M, M)
    MIN_M = min(MIN_M, M)

ans = max(MAX_P - MIN_P, MAX_M - MIN_M)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans1 = max(plus) - min(plus)
ans2 = max(minus) - min(minus) 

print(max(ans1,ans2))