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:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
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())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
mxx = [0,0]
mnx = [10**9+5,0]
mxy = [0,0]
mny = [10**9+5,10**9+5]
for i in range(n):
    x,y = inm()
    if mxx[0] < x:
        mxx[0] = x
        mxx[1] = y
    if mxy[1] < y:
        mxy[0] = x
        mxy[1] = y
    if mnx[0] > x:
        mnx[0] = x
        mnx[1] = y
    if mny[1] > y:
        mny[0] = x
        mny[1] = y

ans = 0
for x1,y1 in [mxx,mnx,mxy,mny]:
    for x2,y2 in [mxx,mnx,mxy,mny]:
        ans = max(ans,abs(x1-x2)+abs(y1-y2))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ma = 0
mi = float('inf')
for x,y in xy:
  ma = max(ma,x-y)
  mi = min(mi,x-y)
ans = ma - mi

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()
ans = x_list[-1] - x_list[0] + y_list[-1] - y_list[0]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]
s=[]
for i in range(n):
    xi,yi=map(int,input().split())
    x.append(xi)
    y.append(yi)
    s.append(xi+yi)
mini=s.index(min(s))
maxi=s.index(max(s))
absx=abs(x[mini]-x[maxi])
absy=abs(y[mini]-y[maxi])
print(absx+absy)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=[]
s=[]
f=[]
for _ in range(n):
    x,y=map(int,input().split())
    k.append(x+y)
    s.append(x)
    f.append(y)


p=k.index(max(k))
q=k.index(min(k))
print((abs(s[p]-s[q]))+(abs(f[p]-f[q])))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

max_li = [0]*N
min_li = [0]*N

for i in range(N):
  x,y = map(int, input().split())
  if x-y >= 0:
    arr = [x+y,x-y]
  else:
    arr = [x+y,y-x]
  
  max_li[i] = max( arr )
  min_li[i] = min( arr )

print( max(max_li)-min(min_li) -2 )

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
Min = float('inf')
Max = 0
Sum_y = defaultdict(lambda:[])
for i in range(N):
    x,y = map(int,input().split())
    Sum = x+y
    Min = min(Min,Sum)
    Max = max(Max,Sum)
    Sum_y[Sum].append(y)
ans = Max-Min

for key in Sum_y.keys():
    ans = max(ans,2*(max(Sum_y[key])-min(Sum_y[key])))
print(ans)

Submission status: Wrong Answer

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

    return d[-1] - d[0]


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
c,v,b,m=0,0,0,0
for i in range(n):
    x,y=map(int,input().split())
    c=max(x+y,c)
    if i==0:
        v=x+y
    else:
        v=min(x+y,v)

    
    if math.fabs(x-y)>b:
        m=b
    b=max(math.fabs(x-y),b)
print(int(max(c-v, b+m)))

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            kyori = (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2 + 2 * (x[i] - x[j]) * (y[i] - y[j])
            if ans < kyori:
                ans = kyori
    print(int(pow(ans, (1/2))))
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x, y = map(int, input().split())
A = B = C = D = E = F = G = H = [x, y]
for _ in range(N - 1):
    x, y = map(int, input().split())
    if x <= A[0] and y <= A[1]:
        A = [x, y]
    if x <= B[0] and y >= B[1]:
        B = [x, y]
    if x >= C[0] and y >= C[1]:
        C = [x, y]
    if x >= D[0] and y <= D[1]:
        D = [x, y]
    if (x <= A[0] or x <= B[0]) and A[1] <= y <= B[1]:
        E = [x, y]
    if (y >= B[1] or y >= C[1]) and B[0] <= x <= C[0]:
        F = [x, y]
    if (x >= C[0] or x >= D[0]) and D[1] <= y <= C[1]:
        G = [x, y]
    if (y <= A[1] or y <= D[1]) and A[0] <= x <= D[0]:
        H = [x, y]
L = []
L.append(abs(A[0] - B[0]) + abs(A[1] - B[1]))
L.append(abs(A[0] - C[0]) + abs(A[1] - C[1]))
L.append(abs(A[0] - D[0]) + abs(A[1] - D[1]))
L.append(abs(A[0] - E[0]) + abs(A[1] - E[1]))
L.append(abs(A[0] - F[0]) + abs(A[1] - F[1]))
L.append(abs(A[0] - G[0]) + abs(A[1] - G[1]))
L.append(abs(A[0] - H[0]) + abs(A[1] - H[1]))
L.append(abs(B[0] - C[0]) + abs(B[1] - C[1]))
L.append(abs(B[0] - D[0]) + abs(B[1] - D[1]))
L.append(abs(B[0] - E[0]) + abs(B[1] - E[1]))
L.append(abs(B[0] - F[0]) + abs(B[1] - F[1]))
L.append(abs(B[0] - G[0]) + abs(B[1] - G[1]))
L.append(abs(B[0] - H[0]) + abs(B[1] - H[1]))
L.append(abs(C[0] - D[0]) + abs(C[1] - D[1]))
L.append(abs(C[0] - E[0]) + abs(C[1] - E[1]))
L.append(abs(C[0] - F[0]) + abs(C[1] - F[1]))
L.append(abs(C[0] - G[0]) + abs(C[1] - G[1]))
L.append(abs(C[0] - H[0]) + abs(C[1] - H[1]))
L.append(abs(D[0] - E[0]) + abs(D[1] - E[1]))
L.append(abs(D[0] - F[0]) + abs(D[1] - F[1]))
L.append(abs(D[0] - G[0]) + abs(D[1] - G[1]))
L.append(abs(D[0] - H[0]) + abs(D[1] - H[1]))
L.append(abs(E[0] - F[0]) + abs(E[1] - F[1]))
L.append(abs(E[0] - G[0]) + abs(E[1] - G[1]))
L.append(abs(E[0] - H[0]) + abs(E[1] - H[1]))
L.append(abs(F[0] - G[0]) + abs(F[1] - G[1]))
L.append(abs(F[0] - H[0]) + abs(F[1] - H[1]))
L.append(abs(G[0] - H[0]) + abs(G[1] - H[1]))
print(max(L))

Submission status: Wrong Answer

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

r_max = point_list[0][0]
r_min = point_list[0][0]
u_max = point_list[0][1]
u_min = point_list[0][1]

for point in point_list:
    r_max = max(r_max, point[0])
    r_min = min(r_min, point[0])
    u_max = max(u_max, point[1])
    u_min = min(u_min, point[1])

r_offset = (r_max + r_min) // 2
u_offset = (u_max + u_min) // 2

max_dist = 0
max_dist_index = -1

for i, point in enumerate(point_list):
    dist = abs(point[0] + r_offset) + abs(point[1] + u_offset)
    if dist > max_dist:
        max_dist = dist
        max_dist_index = i

ans = 0

for point in point_list:
    ans = max(ans, abs(point[0] - point_list[max_dist_index][0]) + abs(point[1] - point_list[max_dist_index][1]))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())


# x_max = 0
# x_min = 10**10
# y_max = 0
# y_min = 10**10


# 最初の2点
# x0, y0 = map(lambda x: int(x), input().split())
# x1, y1 = map(lambda x: int(x), input().split())

edge0 = list(map(lambda x: int(x), input().split()))
edge1 = list(map(lambda x: int(x), input().split()))
dis = abs(edge0[0]-edge1[0]) + abs(edge0[1]-edge1[1])

# dis = abs(x0 - x1) + abs(y0 - y1)
# x_max = max(x0, x1)
# x_min = min(x0, x1)
# y_max = max(y0, y1)
# y_min = min(y0, y1)

for  _ in range(n-2):
    x, y = map(lambda x: int(x), input().split())
    if (x < min(edge0[0], edge1[0])) | (max(edge0[0], edge1[0]) < x) | (y < min(edge0[1], edge1[1])) | (max(edge0[1], edge1[1]) < y):
            dis_from_edge0 = abs(x-edge0[0]) + abs(y-edge0[1])
            dis_from_edge1 = abs(x-edge1[0]) + abs(y-edge1[1])

            # 更新なし
            if max(dis_from_edge0, dis_from_edge1) <= dis:
                continue
            # どちらも更新
            if min(dis_from_edge0, dis_from_edge1) > dis:
                if dis_from_edge0 < dis_from_edge1:
                    dis  = dis_from_edge1
                    edge0 = [x, y]
                else:
                    dis = dis_from_edge0
                    edge1 = [x, y]
                continue
            if dis_from_edge0 > dis:
                dis = dis_from_edge0
                edge1 = [x, y]
                continue
    #       if dis_from_edge1 > dis:
            dis = dis_from_edge1
            edge0 = [x, y]
print(dis)

    #     x_max = max(x, x_max)
    #     x_min = min(x, x_min)
    #     y_max = max(y, y_max)
    #     y_min = min(y, y_min)

Submission status: Wrong Answer

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def maxAbsValExpr(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] + i
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res

A= []
N = int(input())
x,y =[],[]
for i in range(N):
    a,b = ilele()
    x.append(a);y.append(b)

print(maxAbsValExpr(x, y)-1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

upper = []
lower = []
for _ in range(N):
    x, y = mapint()
    if x<=y:
        upper.append((x, y))
    else:
        lower.append((x, y))
upper.sort()
lower.sort()

if len(upper):
    upper_max = abs(upper[0][0]-upper[-1][0]) + abs(upper[0][1]-upper[-1][1])
else:
    upper_max = 0
if len(lower):
    lower_max = abs(lower[0][0]-lower[-1][0]) + abs(lower[0][1]-lower[-1][1])
else:
    lower_max = 0

if len(upper) and len(lower):
    upper.sort(key=lambda x:x[0]-x[1])
    lower.sort(key=lambda x:x[1]-x[0])
    upper_lower = abs(upper[0][0]-lower[0][0]) + abs(upper[0][1]-lower[0][1])
else:
    upper_lower = 0
print(max(upper_max, lower_max, upper_lower))

Submission status: Wrong Answer

Solution code:
N = int(input())

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for x, y in P:
    X.append(x)
    Y.append(y)
mx = (min(X) + max(X)) // 2
my = (min(X) + max(X)) // 2

Q = []
for x, y in P:
    x, y = x-mx, y-my
    Q.append((x+y, x-y))

ans = 0
for x, y in Q:
    ans = max(ans, abs(x) + abs(y))
print(ans)

Submission status: Wrong Answer

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

    x_dl, y_dl = XY[0]
    for i in range(n):
        ans = max(ans, abs(XY[i][0]-x_dl)+abs(XY[i][1]-y_dl))
    XY = sorted(XY, key=lambda x: (-x[0], x[1]))
    x_dr, y_dr = XY[0]
    for i in range(n):
        ans = max(ans, abs(XY[i][0]-x_dr)+abs(XY[i][1]-y_dr))
    XY = sorted(XY, key=lambda x: (-x[1], x[0]))  
    x_ul, y_ul = XY[0]
    for i in range(n):
        ans = max(ans, abs(XY[i][0]-x_ul)+abs(XY[i][1]-y_ul))
    XY = sorted(XY, key=lambda x: (-x[1], -x[0]))
    x_ur, y_ur = XY[0]
    for i in range(n):
        ans = max(ans, abs(XY[i][0]-x_ur)+abs(XY[i][1]-y_ur))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())


# x_max = 0
# x_min = 10**10
# y_max = 0
# y_min = 10**10


# 最初の2点
# x0, y0 = map(lambda x: int(x), input().split())
# x1, y1 = map(lambda x: int(x), input().split())

edge0 = list(map(lambda x: int(x), input().split()))
edge1 = list(map(lambda x: int(x), input().split()))
dis = abs(edge0[0]-edge1[0]) + abs(edge0[1]-edge1[1])

# dis = abs(x0 - x1) + abs(y0 - y1)
# x_max = max(x0, x1)
# x_min = min(x0, x1)
# y_max = max(y0, y1)
# y_min = min(y0, y1)

for  _ in range(n-2):
    x, y = map(lambda x: int(x), input().split())
    if (x < min(edge0[0], edge1[0])) | (max(edge0[0], edge1[0]) < x) | (y < min(edge0[1], edge1[1])) | (max(edge0[1], edge1[1]) < y):
            dis_from_edge0 = abs(x-edge0[0]) + abs(y-edge0[1])
            dis_from_edge1 = abs(x-edge1[0]) + abs(y-edge1[1])

            # 更新なし
            if max(dis_from_edge0, dis_from_edge1) <= dis:
                continue
            # どちらも更新
            if min(dis_from_edge0, dis_from_edge1) > dis:
                if dis_from_edge0 < dis_from_edge1:
                    dis  = dis_from_edge1
                    edge0 = [x, y]
                else:
                    dis = dis_from_edge0
                    edge1 = [x, y]
                continue
            if dis_from_edge0 > dis:
                dis = dis_from_edge0
                edge1 = [x, y]
                continue
    #       if dis_from_edge1 > dis:
            dis = dis_from_edge1
            edge1 = [x, y]
print(dis)

    #     x_max = max(x, x_max)
    #     x_min = min(x, x_min)
    #     y_max = max(y, y_max)
    #     y_min = min(y, y_min)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def manha(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1] - p2[1])

N = int(input())
x = [0] * N
y = [0] * N

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

MAX = 0
MIN = 10 ** 10
x_min = (MIN, 0)
x_max = (MAX, 0)
y_min = (0, MIN)
y_max = (0, MAX)

for i in range(N):
    tmp_x = x[i]
    tmp_y = y[i]

    if tmp_x < x_min[0]:
        x_min = (tmp_x, tmp_y)

    if x_max[0] < tmp_x:
        x_max = (tmp_x, tmp_y)

    if tmp_y < y_min[1]:
        y_min = (tmp_x, tmp_y)

    if y_max[1] < tmp_y:
        y_max = (tmp_x, tmp_y)

result = max(manha(x_min, y_min), manha(x_min, x_max), manha(x_min, y_max), manha(y_min, y_max), manha(y_min, x_max), manha(y_max, x_max))
print(result)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[]
  for _ in range(n):
    a,b=LI()
    l.append((a,b,a+b))

  l=sorted(l,key=lambda x:x[2])

  ans=0
  for a,b,c in l[:2]:
    for d,e,f in l[1:]:
      ans=max(ans,abs(a-d)+abs(b-e))
  return ans

# main()
print(main())

Submission status: Wrong Answer

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

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

n = readInt()
minPoint,maxPoint = [],[]
allPOints = []
for _ in range(n):
    x,y = readIntList()
    allPOints.append([x,y])

allPOints.sort(key=lambda x: x[0])
a = allPOints[0]
b = allPOints[-1]
allPOints.sort(key=lambda x: x[1])
c = allPOints[0]
d = allPOints[-1]

def getDist(x,y):
    return abs(x[0]-y[0]) + abs(x[1]-y[1])

res = max(getDist(a,b),getDist(a,c),getDist(a,d),getDist(b,c),getDist(b,d),getDist(c,d))

print(res)

Submission status: Wrong Answer

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


def solve(N: int, x):
    x = list(set(x))
    xs = [_[0] for _ in x]
    ys = [_[1] for _ in x]
    sum_n = [x_+y_ for x_, y_ in zip(xs, ys)]
    sum_m = [x_-y_ for (x_,y_) in zip(xs, ys)]

    a = max(max(sum_n)- min(sum_n), max(sum_m)-min(sum_n))
    print(a)
    

    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

p = []

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

x = []
x.append(max(p, key=lambda a: a[0]))
x.append(max(p, key=lambda a: a[1]))
x.append(min(p, key=lambda a: a[0]))
x.append(min(p, key=lambda a: a[1]))
x.append(max(p, key=lambda a: a[0] + a[1]))
x.append(min(p, key=lambda a: a[0] + a[1]))

ans = 0

for i in range(5):
    for j in range(i + 1, 6):
        d = abs(x[i][0] - x[j][0]) + abs(x[i][1] - x[j][1])
        ans = max(ans, d)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)]

a = xy[0][0]
b = xy[0][1]

m_len = -1

for i in range(n-1):
    tmp = abs(xy[i+1][0]-a)+abs(xy[i+1][1]-b)
    if m_len < tmp:
         m_len = tmp
         idx = i

a = xy[i][0]
b = xy[i][1]

for i in range(n):
    if i == idx:
        continue
    tmp = abs(xy[i][0]-a)+abs(xy[i][1]-b)
    if m_len < tmp:
        m_len = tmp
        
print(m_len)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict,deque,Counter
from fractions import Fraction
import bisect
import itertools
from itertools import accumulate
from copy import deepcopy

import heapq
import random
import time
import os
import sys
from functools import lru_cache,reduce
readline=sys.stdin.readline
sys.setrecursionlimit(100000)
alp="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Set():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(bool)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        if not self.find(x):
            heapq.heappush(self.heap,x)
            self.dic[x]=True
            self.size+=1

    def remove(self,x):
        if self.find(x):
            self.dic[x]=False
            self.size-=1

    def find(self,x):
        return self.dic[x]
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==False:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class multiset():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(int)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        heapq.heappush(self.heap,x)
        self.dic[x]+=1
        self.size+=1

    def remove(self,x):
        if self.dic[x]>0:
            self.dic[x]-=1
            self.size-=1
    
    def count(self,x):
        return self.dic[x]

    def find(self,x):
        return self.dic[x]>0
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==0:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class Point():
    def __init__(self,y,x):
        self.x=x
        self.y=y
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):print("yes" if b else "no")
def Yn(b):print("Yes" if b else "No")
def YN(b):print("YES" if b else "NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(b,t,f):return t if b else f
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def inputintlist(row=1): 
    if row==1:
        ret=list(map(int,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=int(input())
    return ret
def inputfloatlist(row=1): 
    if row==1:
        ret=list(map(float,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=float(input())
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    from queue import PriorityQueue
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def zipsort(*args):
    ziplist=sorted(zip(*args))
    for a in range(len(args)):
        for b in range(len(ziplist)):
            args[a][b]=ziplist[b][a]
def zipreverse(*args):
    ziplist=list(zip(*args))
    rev=[]
    for a in range(len(ziplist)-1,-1,-1):
        rev.append(ziplist[a])
    for a in range(len(args)):
        for b in range(len(rev)):
            args[a][b]=rev[b][a]

def to10(A):
    ret=0
    for a in range(len(A)-1,-1,-1):
        ret+=X[a]*2**(N-1-a)
    return ret
######################################################################################################
n=int(input())
X=[0]*n
Y=[0]*n
for a in range(n):
    X[a],Y[a]=inputintlist()
zipsort(X,Y)

maxp=0
for a in range(n):
    if X[maxp]+Y[maxp]<X[a]+Y[a]:
        maxp=a
minp=0
for a in range(n):
    if X[minp]+Y[minp]>X[a]+Y[a]:
        minp=a
ans=abs(X[maxp]-X[minp])+abs(Y[maxp]-Y[minp])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ma = 0
mi = float('inf')
for x,y in xy:
  ma = max(ma,abs(x-y))
  mi = min(mi,abs(x-y))
ans = ma - mi

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

print(ans)

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]
	for i in range(N - 1):
		D.append(abs(P["x"] - p[i]["x"]) + abs(P["y"] - p[i]["y"]))
	print(max(D))

main()