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: Wrong Answer

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for i in range(N)]
d=set()
for i, j in zip(range(N),range(1,N)):
    d.add(abs(l[i][0]-l[j][0]) + abs(l[i][1]-l[j][1]))
print(max(d))

Submission status: Wrong Answer

Solution code:
N=int(input())
x_numbers=[]
y_numbers=[]
for _ in range(N):
    x,y=map(int,input().split())
    x_numbers.append([x,y])
    y_numbers.append([y,x])
sort_x_numbers=sorted(x_numbers)
sort_y_numbers=sorted(y_numbers)
ans1=[]
ans2=[]
x1=sort_x_numbers[-1]
for n in x_numbers:
    ans1.append(abs(n[0]-x1[0])+abs(n[1]-x1[1]))
ans11=max(ans1)
x2=sort_y_numbers[-1]
for n in x_numbers:
    ans2.append(abs(n[0]-x2[1])+abs(n[1]-x2[0]))
ans22=max(ans2)
print(max(ans11,ans22))

Submission status: Wrong Answer

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################


n = int(input())
arr = set()
for i in range(n):
	x ,y = map(int , input().split())
	arr.add((x,y))
arr1 = sorted(arr , key = lambda x : (x[0]+x[1]))
arr2 = sorted(arr , key = lambda x : (x[0],x[1]))
arr3 = sorted(arr , key = lambda x : (x[1],x[0]))
#print(arr)
#print(abs(arr[0][0] - arr[len(arr)-1][0]) + abs(arr[0][1] - arr[len(arr)-1][1]))
ans = float("-inf")
for i in range(1,len(arr)):
	#print("!!",abs(arr[0][0] - arr[i][0]) , abs(arr[0][1] - arr[i][1]))
	ans = max(ans , abs(arr1[0][0] - arr1[i][0]) + abs(arr1[0][1] - arr1[i][1]))
	ans = max(ans , abs(arr2[0][0] - arr2[i][0]) + abs(arr2[0][1] - arr2[i][1]))
	ans = max(ans , abs(arr3[0][0] - arr3[i][0]) + abs(arr3[0][1] - arr3[i][1]))
print(ans)






'''
# Wrap solution for more recursion depth
#submit as python3
import collections,sys,threading
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)



threading.Thread(target=solve).start()
'''

Submission status: Wrong Answer

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)
syou = x[0]+y[0]
dai = x[0]+y[0]
for i in range (N):
    if x[i]+y[i]>dai:
        dai = x[i]+y[i]
    if x[i]+y[i]<syou:
        syou = x[i]+y[i]
ans = dai - syou
print (ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
for i in range(N):
    x,y=[int(i) for i in input().split()]
    A.append(x)
    B.append(y)

mm = (10**9)*2
mmn = 0
pm = 10**9
pmn = 0
mp = 10**9
mpn = 0
pp = 0
ppn = 0
for j in range (N):
    if (A[j]+B[j])>pp:
        pp = A[j]+B[j]
        ppn = j
    if (A[j]-B[j])>pm:
        pp = A[j]-B[j]
        pmn = j
    if (B[j]-A[j])>mp:
        mp = B[j]-A[j]
        mpn = j
    if (A[j]+B[j])<mm:
        mm = A[j]+B[j]
        mmn = j
ans1 = abs(A[ppn] - A[mmn]) + abs(B[ppn] - B[mmn])
ans2 = abs(A[pmn] - A[mpn]) + abs(B[mpn] - B[pmn])
ans = max(ans1,ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
#https://naoyat.hatenablog.jp/entry/k-dimension-manhattan-distance
N=int(input())
kouho=[0]*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: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


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


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


def search(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())

xmax = xmin = ymin = ymax = 0
xmax_i = ymax_i = xmin_i = ymin_i = 0

X = []
for i in range(N):
    x, y = acinput()
    X.append([x, y])
    if x > xmax:
        xmax = x
        xmax_i = i
    if y > ymax:
        ymax = y
        ymax_i = i
    if x < xmin:
        xmin = x
        xmin_i = i
    if y < ymin:
        ymin = y
        ymin_i = i

s = [xmax_i, xmin_i, ymax_i, ymin_i]
res = 0

S = []
for i in s:
    S.append(X[i])

for i in range(3):
    for j in range(i+1, 4):
        tmp = abs(S[j][0]-S[i][0])+abs(S[j][1]-S[i][1])
        res = max(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    a = list(map(int,input().split()))
    x.append(a)
c_1 = sorted(x, key=lambda x:x[1],reverse = True)
c_2= sorted(x, key=lambda x:x[0],reverse = True)
ans_1 = abs(abs(c_1[0][0]) - abs(c_1[-1][0])) + abs(abs(c_1[0][1]) - abs(c_1[-1][1]))
ans_2 = abs(abs(c_2[0][0]) - abs(c_2[-1][0])) + abs(abs(c_2[0][1]) - abs(c_2[-1][1]))

print(max(ans_1,ans_2))

Submission status: Wrong Answer

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 = 0
    min_a = 10 ** 9
    max_b = 0
    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: Wrong Answer

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################


n = int(input())
arr = set()
for i in range(n):
	x ,y = map(int , input().split())
	arr.add((x,y))
arr1 = sorted(arr , key = lambda x : (x[0]+x[1]))
arr2 = sorted(arr , key = lambda x : (x[0]+x[1]))
arr3 = sorted(arr , key = lambda x : (x[0]+x[1]))
#print(arr)
#print(abs(arr[0][0] - arr[len(arr)-1][0]) + abs(arr[0][1] - arr[len(arr)-1][1]))
ans = float("-inf")
for i in range(1,len(arr)):
	#print("!!",abs(arr[0][0] - arr[i][0]) , abs(arr[0][1] - arr[i][1]))
	ans = max(ans , abs(arr1[0][0] - arr1[i][0]) + abs(arr1[0][1] - arr1[i][1]))
	ans = max(ans , abs(arr2[0][0] - arr2[i][0]) + abs(arr2[0][1] - arr2[i][1]))
	ans = max(ans , abs(arr3[0][0] - arr3[i][0]) + abs(arr3[0][1] - arr3[i][1]))
print(ans)






'''
# Wrap solution for more recursion depth
#submit as python3
import collections,sys,threading
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)



threading.Thread(target=solve).start()
'''

Submission status: Wrong Answer

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

x0 = 10 ** 9
y0 = 10 ** 9

d = x0 + y0

M = 0
m = 2 * d + 1
for x, y in XY:
    p = x + y + d
    if p > M:
        M = p
    elif p < m:
        m = p

# print(M, m)

print(M - m)

Submission status: Wrong Answer

Solution code:
N=int(input())
migisita=[0,10^9]
migiue=[0,0]
hidarisita=[10^9,10^9]
hidariue=[10^9,0]
for i in range(0,N):
    a,b=list(map(int,input().split()))
    if migiue[0]<a and migiue[1]<b:
        migiue=[a,b]
    if migisita[0]<a and migisita[1]>b:
        migisita=[a,b]
    if hidariue[0]>a and hidariue[1]<b:
        hidariue=[a,b]
    if hidarisita[0]>a and hidarisita[1]>b:
        hidarisita=[a,b]

one=abs(migiue[0]-hidarisita[0])+abs(migiue[1]-hidarisita[1])
two=abs(hidariue[0]-migisita[0])+abs(hidariue[1]-hidarisita[1])
three=abs(migiue[0]-migisita[0])+abs(migiue[1]-migisita[1])
four=abs(hidariue[0]-hidarisita[0])+abs(hidariue[1]-hidarisita[1])
print(max(one,two,three,four))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[0]*n
y=[0]*n
z=[0]*n
a=-1
b=-1
for i in range(n):
    x[i],y[i] = list(map(int, input().strip().split()))
for i in range(n):
    z[i]=x[i]**2+y[i]**2
s=max(z)
t=min(z)
for i in range(n):
    if z[i]==s:
        a=i
        
    if z[i]==t:
        b=i
        
print(abs(x[a]-x[b])+abs(y[a]-y[b]))

Submission status: Wrong Answer

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


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

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

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

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

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

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


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

xy.sort()
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((max(abs(sx-tx), abs(sy-ty)), si, ti))

xy.sort(key=lambda x: x[1])
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((max(abs(sx-tx), abs(sy-ty)), si, ti))

uf = UnionFind(n)
ans = 0
G.sort()
for c, x, y in G:
    if uf.same(x, y):
        continue
    uf.union(x, y)
    ans += c
print(ans)

Submission status: Wrong Answer

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=0
m1=0
mi=10**11
mi1=10**11
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(max(m-mi,m1-mi1))

Submission status: Wrong Answer

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 = [zahyo[i][0] for i in range(N)]
zahyo3 = [zahyo[i][1] for i in range(N)]
h = 0
l = 10**9
hx = zahyo[0][0]
hy = zahyo[0][1]
lx = zahyo[0][0]
ly = zahyo[0][1]
for i in range(N):
    h = max(h,sum(zahyo[i]))
    l = min(l,sum(zahyo[i]))
    hx = max(hx,zahyo[i][0])
    hy = max(hy,zahyo[i][1])
    lx = min(lx,zahyo[i][0])
    ly = min(ly,zahyo[i][1])
ans = h-l
ans2 = hx-lx+abs(zahyo3[zahyo2.index(hx)]-zahyo3[zahyo2.index(lx)])
ans3 = hy-ly+abs(zahyo2[zahyo3.index(hy)]-zahyo2[zahyo3.index(ly)])
print(max(ans,ans2,ans3))

Submission status: Wrong Answer

Solution code:
N=int(input())
kouho=[0]*4#xmax,ymax,xmin,ymin
kouho[2]=10**9+1
kouho[3]=10**9+1
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: Wrong Answer

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

    pairs = list(set(pairs))

    modified = []

    max_a = 0
    min_a = 10 ** 9
    max_b = 0
    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: Wrong Answer

Solution code:
def main():
	N = int(input())
	p = []
	for i in range(N):
		x, y = [int(a) for a in input().split(" ")]
		p.append({"x" : x, "y" : y})
	aveX = 0
	aveY = 0
	for i in range(N):
		aveX += p[i]["x"]
		aveY += p[i]["y"]
	aveX /= N
	aveY /= N
	for i in range(N):
		p[i]["d"] = abs(aveX - p[i]["x"]) + abs(aveY - p[i]["y"])
	p.sort(key=lambda z: z["d"])
	D = []
	P = [p[-1], p[-2]]
	for i in range(N - 1):
		D.append(abs(P[0]["x"] - p[i]["x"]) + abs(P[0]["y"] - p[i]["y"]))
		D.append(abs(P[1]["x"] - p[i]["x"]) + abs(P[1]["y"] - p[i]["y"]))
	print(max(D))

main()