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:
# ---------------------------iye ha aam zindegi---------------------------------------------
import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
#threading.stack_size(10**8)
mod = 10 ** 9 + 7
mod1 = 998244353

# ------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
#sys.setrecursionlimit(300000)

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


# -------------------game starts now----------------------------------------------------import math
class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n


# -----------------------------------------------binary seacrh tree---------------------------------------
class SegmentTree1:
    def __init__(self, data, default=0, func=lambda a, b: max(a , b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# -------------------game starts now----------------------------------------------------import math
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b:a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# -------------------------------iye ha chutiya zindegi-------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


# --------------------------------------iye ha combinations ka zindegi---------------------------------
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m


# --------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z


# --------------------------------------------------product----------------------------------------
def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por


# --------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] < key):
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


# --------------------------------------------------binary----------------------------------------
def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c
def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)


# --------------------------------------------------binary------------------------------------
n=int(input())
ans=0
d=defaultdict(int)
d1=defaultdict(int)
m=-10**13
m1=-10**13
mi=10**13
mi1=10**13
for i in range(n):
    a,b=map(int,input().split())
    m=max(m,a+b)
    mi=min(mi,a+b)
    m1=max(m1,a-b)
    mi1=min(mi1,a-b)
#print(mi,mi1,m,m1)
print(max(m-mi,m1-mi1))

Submission status: Accepted

Solution code:
N = int(input())
W = []
S = []
for _ in range(N):
    x,y = [int(hoge) for hoge in input().split()]
    wa = x+y
    sa = x-y
    W.append(wa)
    S.append(sa)
T = max(W)- min(W)
Y = max(S)- min(S)
print(max(T,Y))

Submission status: Accepted

Solution code:
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    x = list()
    y = list()
    for _ in range(n):
        xi, yi = _ia()
        x.append(xi - yi)
        y.append(xi + yi)
    return max(max(x) - min(x), max(y) - min(y))


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

Submission status: Accepted

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

# 左下右上
mi = min(XY, key=lambda x: x[0] + x[1])
ma = max(XY, key=lambda x: x[0] + x[1])
ans1 = ma[0]-mi[0] + ma[1]-mi[1]

# 左上右下
mi = min(XY, key=lambda x: x[0] + (10**9)-x[1])
ma = min(XY, key=lambda x: (10**9)-x[0] + x[1])
ans2 = abs(ma[0]-mi[0]) + abs(ma[1]-mi[1])
print(max(ans1, ans2))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    
    minA = minB = float('inf')
    maxA = maxB = - float('inf')
    
    for i in range(N):
        x, y = MI()
        x2, y2 = x - y, x + y
        minA = min(minA, x2)
        maxA = max(maxA, x2)
        minB = min(minB, y2)
        maxB = max(maxB, y2)
    
    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,x,y])
  b.append([x-y,x,y])
a.sort()
b.sort()
ans=abs(a[0][1]-a[n-1][1])+abs(a[0][2]-a[n-1][2])
aa=abs(b[0][1]-b[n-1][1])+abs(b[0][2]-b[n-1][2])
print(max(ans,aa))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    N, = map(int, input().split())

    kmin=100000000000
    kmax = 0
    lmin = 100000000000
    lmax = 0
    for i in range(N):
        x,y = map(int, input().split())
        k = y-x
        l = y+x
        kmin = min(kmin,k)
        lmin = min(lmin, l)
        kmax = max(kmax, k)
        lmax = max(lmax, l)


    print(max(kmax-kmin,lmax-lmin))
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 1
2 4
3 2"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
1 1
1 1"""
        output = """0"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,*f = map(int, open(0).read().split())
xy = [f[i*2:i*2+2] for i in range(N)]
s = [sum(z) for z in xy]
a = max(s) - min(s)
t = [z[0]-z[1] for z in xy]
b = max(t) - min(t)
print(max(a,b))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    P = [list(map(int, input().split())) for _ in range(n)]
    C0, C1 = [], []
    ans = 0

    for pi in P:
        C0.append(pi[0] - pi[1])
        C1.append(pi[0] + pi[1])

    C0min = min(C0)
    C0max = max(C0)
    C1min = min(C1)
    C1max = max(C1)

    print(max(C0max - C0min, C1max - C1min))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i],Y[i] = map(int,input().split())
for i in range(N):
    x = X[i]
    y = Y[i]
    b1 = x+y
    b2 = -x+y
    if i == 0:
        minb1=b1
        maxb1=b1
        minb2=b2
        maxb2=b2
        lowb1=[x,y]
        highb1=[x,y]
        lowb2=[x,y]
        highb2=[x,y]
    else:
        if b1<minb1:
            lowb1=[x,y]
            minb1 = b1
        if b1>maxb1:
            highb1=[x,y]
            maxb1 = b1
        if b2<minb2:
            lowb2=[x,y]
            minb2 = b2
        if b2>maxb2:
            highb2=[x,y]
            maxb2 = b2
            
candidate1 = highb1[0]-lowb1[0]+highb1[1]-lowb1[1]
candidate2 = lowb2[0]-highb2[0]+highb2[1]-lowb2[1]
print(max(candidate1,candidate2))

Submission status: Accepted

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

edge=[ab[0][0],ab[0][1],ab[0][0],ab[0][1],ab[0][0],ab[0][1],ab[0][0],ab[0][1]]
tate = 0
yoko = 0
summ = 10**10
sumn = 0

for i in range(n):
    x = ab[i][0]
    y = ab[i][1]
    if x+y <= summ :
        edge[0] = x
        edge[1] = y
        summ = x+y
    if x+y >= sumn :
        edge[2] = x
        edge[3] = y
        sumn = x+y
    if x-y <= tate:
        edge[4] =x
        edge[5] =y
        tate = x-y
    if y-x <= yoko:
        edge[6] =x
        edge[7] =y
        yoko = y-x

a = abs(edge[0]-edge[2]) +abs(edge[1]-edge[3])
b = abs(edge[0]-edge[4]) +abs(edge[1]-edge[5])
c = abs(edge[0]-edge[6]) +abs(edge[1]-edge[7])
d = abs(edge[2]-edge[4]) +abs(edge[3]-edge[5])
e = abs(edge[2]-edge[6]) +abs(edge[3]-edge[7])
f = abs(edge[4]-edge[6]) +abs(edge[5]-edge[7])

print(max(a,b,c,d,e,f))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    n = int(input())
    XY = [tuple(map(int,input().split())) for i in range(n)]
    XY.sort()
    ans = 0
    SXY = [[0,0,0] for i in range(n)]
    for i in range(n):
        SXY[i][0] = XY[i][0] + XY[i][1] 
        SXY[i][1] = XY[i][0]
        SXY[i][2] = XY[i][1]
    SXY.sort()
    ans = abs(SXY[0][1]-SXY[-1][1])+abs(SXY[0][2]-SXY[-1][2]) 
    SXY = [[0,0,0] for i in range(n)]
    for i in range(n):
        SXY[i][0] = XY[i][1] - XY[i][0] 
        SXY[i][1] = XY[i][0]
        SXY[i][2] = XY[i][1]
    SXY.sort()
    ans = max(ans,abs(SXY[0][1]-SXY[-1][1])+abs(SXY[0][2]-SXY[-1][2])) 
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]
p = []
q = []
i = 0
while i < N:
  p.append(x[i]+y[i])
  q.append(x[i]-y[i])
  i += 1
print(max(max(p)-min(p),max(q)-min(q)))

Submission status: Accepted

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

def get_ans2(tpl1, tpl2):
    ans2 = abs(tpl1[0]-tpl2[0])+abs(tpl1[1]-tpl2[1])
    return ans2

lst=[]
mx_dis1, mn_dis1 = 0, 10**9
mx_y = 0
mn_y = 10**9
mx_y_idx = -1
mn_y_idx = -1
mx_x = 0
mn_x = 10**9
mx_x_idx = -1
mn_x_idx = -1
for i in range(n):
    x, y = map(int, input().split())
    lst.append((x,y))
    dis1 = x + y
    dis2 = abs(x-y)
    mx_dis1 = max(dis1, mx_dis1)
    mn_dis1 = min(dis1, mn_dis1)
    if x>=y:
        if dis2 > mx_x:
            mx_x = dis2
            mx_x_idx = i
        if dis2 < mn_x:
            mn_x = dis2
            mn_x_idx=i
    else:
        if dis2 > mx_y:
            mx_y = dis2
            mx_y_idx = i
        if dis2 < mn_y:
            mn_y = dis2
            mn_y_idx = i
    

ans1 = mx_dis1-mn_dis1

if mx_x_idx<0:
    ans2 = get_ans2(lst[mx_y_idx], lst[mn_y_idx])
elif mn_y_idx<0:
    ans2 = get_ans2(lst[mx_x_idx], lst[mn_x_idx])
else:
    ans2 = get_ans2(lst[mx_x_idx], lst[mx_y_idx])

print(max(ans2, ans1))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
xy = [[] for _ in range(n)]
f1 = []
f2 = []
for i in range(n):
    x, y = map(int, input().split())
    f1.append(x + y)
    f2.append(x - y)
    xy[i].append(x + y)
    xy[i].append(abs(-x - y))

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

Submission status: Accepted

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

def main():
    N = int(readline())
    m = map(int,read().split())
    XY = list(zip(m,m))

    ans = 0
    z = [x-y for (x, y) in XY]
    # print(z)
    z.sort()
    ans = z[-1] - z[0]
    z = [x+y for (x, y) in XY]
    # print(z)
    z.sort()
    ans = max(ans, z[-1] - z[0])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = float("inf")
r = -float("inf")
b = float("inf")
a = -float("inf")
lis = []
for i in range(n):
  j,k=map(int, input().split())
  if j>r:
    r=j
  if j<l:
    l=j
  if k>a:
    a=k
  if k<b:
    b=k
  lis.append([j, k])
  
lb = -1
lbd = float("inf")

rb = -1
rbd = float("inf")

for i in range(n):
  j, k = lis[i]
  if abs(j-l)+abs(k-b)<lbd:
    lbd =  abs(j-l)+abs(k-b)
    lb=i
  if abs(r-j)+abs(k-b)<rbd:
    rbd =  abs(r-j)+abs(k-b)
    rb=i
  
ans = 0
for i in range(n):
  a, b = lis[lb]
  j, k = lis[i]
  if abs(a-j)+abs(b-k)>ans:
    ans=abs(a-j)+abs(b-k)

for i in range(n):
  a, b = lis[rb]
  j, k = lis[i]
  if abs(a-j)+abs(b-k)>ans:
    ans=abs(a-j)+abs(b-k)
print(ans)

Submission status: Accepted

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

d = [0] * N
s = [0] * N
    
for i in range(N):
  d[i] = x[i] - y[i]
  s[i] = x[i] + y[i]


print(max(max(s)-min(s), max(d)-min(d)))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
d1 = [A[i][0] - A[i][1] for i in range(n)]
d2 = [A[i][0] + A[i][1] for i in range(n)]

print(max(max(d1) - min(d1), max(d2)-min(d2)))

Submission status: Accepted

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

for i in ten:
    x = i[0]
    y = i[1]
    i[0] = x-y
    i[1] = x+y

xmax = i[0]
xmin = i[0]
ymax = i[1]
ymin = i[1]
for i in ten:
    xmax = max(xmax,i[0])
    xmin = min(xmin,i[0])
    ymax = max(ymax,i[1])
    ymin = min(ymin,i[1])

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

Submission status: Accepted

Solution code:
#https://naoyat.hatenablog.jp/entry/k-dimension-manhattan-distance
N=int(input())
kouho=[(10**10)*(-1)]*4#xmax,ymax,xmin,ymin
kouho[2]=10**10
kouho[3]=10**10
ans=0
for i in range(N):
    x,y=map(int,input().split())
    newx=x-y
    newy=x+y
    if newx>kouho[0]:
        kouho[0]=newx
    if newx<kouho[2]:
        kouho[2]=newx
    if newy>kouho[1]:
        kouho[1]=newy
    if newy<kouho[3]:
        kouho[3]=newy
ans=max(kouho[0]-kouho[2],kouho[1]-kouho[3])
print(ans)

Submission status: Accepted

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


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

    pairs = []

    for i in range(N):
        x, y = MI()
        pairs.append((x, y))

    modified = []

    max_a = -1 * 10 ** 9
    min_a = 10 ** 9
    max_b = -1 * 10 ** 9
    min_b = 10 ** 9

    for i in range(len(pairs)):
        x, y = pairs[i]
        modified.append([x - y, x + y])

        max_a = max(max_a, x-y)
        min_a = min(min_a, x-y)
        max_b = max(max_b, x+y)
        min_b = min(min_b, x+y)

    ans = max(max_a - min_a, max_b - min_b)
    print(ans)


main()

Submission status: Accepted

Solution code:
import numpy as np

def dist(d1, d2):
    return abs(d1[0]-d2[0]) + abs(d1[1]-d2[1])

n = int(input())
list1 = np.zeros((n))
list2 = np.zeros((n))
xy_list = []
for i in range(n):
    x, y = map(int, input().split())
    xy_list.append([x, y])
    list1[i] = x+y
    list2[i] = x-y

num = np.zeros((4), dtype=int)
num[0] = np.argmax(list1)
num[1] = np.argmax(list2)
num[2] = np.argmin(list1)
num[3] = np.argmin(list2)

ans = 0
for d1 in range(4):
    for d2 in range(d1+1, 4):
        # print(num[d1], num[d2], dist(xy_list[num[d1]], xy_list[num[d2]]))
        ans = max(ans, dist(xy_list[num[d1]], xy_list[num[d2]]))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
pmax = 0
pmin = 0
mmax = 0
mmin = 0
for i in range(n):
    x, y = map(int, input().split())
    if(i ==0 or pmax < x + y):
        pmax = x+y
    if(i == 0 or pmin > x+y):
        pmin = x+y
    if(i == 0 or mmax < x-y):
        mmax = x-y
    if(i == 0 or mmin > x-y):
        mmin = x-y
print(max(pmax - pmin, mmax - mmin))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
(n,), *d = [[*map(int, o.split())] for o in open(0)]
M = [[x - y for x, y in d], [x + y for x, y in d]]
print(max(max(M[d]) - min(M[d]) for d in [0, 1]))

Submission status: Accepted

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

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

a = sorted(a, key = lambda x: x[2])
candidate1 = abs(a[0][0] - a[-1][0]) + abs(a[0][1] - a[-1][1])

a = sorted(a, key = lambda x: x[3])
candidate2 = abs(a[0][0] - a[-1][0]) + abs(a[0][1] - a[-1][1])

print(max([candidate1, candidate2]))

Submission status: Accepted

Solution code:
n=int(input())
ma=2
mi=10**9+7
mu=2
me=10**10
for i in range(n):
    x,y=map(int,input().split())
    l=x+y
    s=-x+10**9+1+y
    ma=max(ma,l)
    mi=min(mi,l)
    mu=max(mu,s)
    me=min(me,s)
print(max(ma-mi,mu-me))