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())
arr = []
for i in range(n):
  arr.append(tuple(map(int, input().split())))
arr.sort(key = sum)
mx = 0
for i in arr[1:]:
  if mx <= abs(i[0] - arr[0][0]) + abs(i[1] - arr[0][1]):
    mx = abs(i[0] - arr[0][0]) + abs(i[1] - arr[0][1])
print(mx)

Submission status: Wrong Answer

Solution code:
#from collections import deque
#from math import gcd
#MOD = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
ans = 0
#print(ans)
r = []
for k in range(N):
  r.append(tuple(map(int, input().split())))
r.sort(key = lambda x:x[0])
#print(r)
nowx = -1
lastx_min = r[0][0]
lastx_max = r[0][0]

miny = r[0][1]
maxy = r[0][1]
k = 0
while k < N:
  if nowx != r[k][0]:
    print(lastx_min, lastx_max, miny, maxy)
    nowx = r[k][0]
    while r[k][0] == nowx:
      ans = max(ans, abs(miny - r[k][1]) + nowx - lastx_min, abs(maxy-r[k][1])+ nowx -lastx_max)
      if miny - (nowx - lastx_min) > r[k][1]:
        miny = r[k][1]
        lastx_min = nowx
      if maxy + (nowx - lastx_max) < r[k][1]:
        maxy = r[k][1]
        lastx_max = nowx
      k += 1
      if k == N:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for i in range(n):
    l = list(map(int, input().split()))
    xy.append(l[0]+l[1])
print(max(xy)-min(xy))

Submission status: Wrong Answer

Solution code:
N = int(input())
minxy = 3*10**9
maxxy = 0
for i in range(N):
    x,y = map(int,input().split())
    minxy = min(minxy,x+y)
    maxxy = max(maxxy,x+y)
print(maxxy-minxy)

Submission status: Wrong Answer

Solution code:
N = int(input())
x1, y1 = map(int, input().split())
centre = [x1, y1]

left_bottom = [x1, y1]
left_bottom_dist = 0

left_top = [x1, y1]
left_top_dist = 0

right_bottom = [x1, y1]
right_bottom_dist = 0

right_top = [x1, y1]
right_top_dist = 0

for i in range(N-1):
  xi, yi = map(int, input().split())
  if xi <= x1 and yi <= y1:
    if x1 - xi + y1 - yi >= left_bottom_dist:
      left_bottom = [xi, yi]
      left_bottom_dist = x1 - xi + y1 - yi
  if xi <= x1 and yi >= y1:
    if x1 - xi + yi - y1 >= left_top_dist:
      left_top = [xi, yi]
      left_top_dist = x1 - xi + yi - y1
  if xi >= x1 and yi <= y1:
    if xi - x1 + y1 - yi >= right_bottom_dist:
      right_bottom = [xi, yi]
      right_bottom_dist = xi - x1 + y1 - yi 
  if xi >= x1 and yi >= y1:
    if xi - x1 + yi - y1 >= right_top_dist:
      right_top = [xi, yi]
      right_top_dist = xi - x1 + yi - y1

D1 = abs(right_top[0] - left_bottom[0]) + abs(right_top[1] - left_bottom[1])
D2 = abs(right_bottom[0] - left_top[0]) + abs(right_bottom[1] - left_top[1])
D3 = abs(left_top[0] - left_bottom[0]) + abs(left_top[1] - left_bottom[1])
D4 = abs(right_top[0] - right_bottom[0]) + abs(right_top[1] - right_bottom[1])
D5 = abs(left_top[0] - right_top[0]) + abs(left_top[1] - right_top[1])
D6 = abs(left_bottom[0] - right_bottom[0]) + abs(left_bottom[1] - right_bottom[1])

print(max(D1, D2, D3, D4, D5, D6))

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))
 
    x_dr, y_dr = XY[-1]
    for i in range(n):
        ans = max(ans, abs(XY[i][0]-x_dr)+abs(XY[i][1]-y_dr))
    XY.sort(key = itemgetter(1))    
    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))
    x_ur, y_ur = XY[-1]
    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())
k=[]
for _ in range(n):
    x,y=map(int,input().split())
    k.append(x+y)


p=max(k)
q=min(k)
print(p-q)

Submission status: Wrong Answer

Solution code:
N = int(input())
Array = []
for i in range(N):
    next_x, next_y = map(int, input().split())
    Array.append([next_x,next_y])

print(Array)
Array2 = []
Point1x = 0
Point1y = 0
Point2x = 0
Point2y = 0
for i in range(N):
    for j in range(N):
        Point1x = Array[i][0]
        Point1y = Array[i][1]
        Point2x = Array[j][0]
        Point2y = Array[j][1]
        Dist = abs(Point1x-Point2x) + abs(Point1y-Point2y)
        Array2.append(Dist)

print(max(Array2))

Submission status: Wrong Answer

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

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

maXP = max(p, key=lambda x:x[0])
miXP = min(p, key=lambda x:x[0])
maYP = max(p, key=lambda x:x[1])
miYP = min(p, key=lambda x:x[1])
mp = [maXP, miXP, maYP, miYP]
md = -1
for i in range(3):
  for j in range(i+1, 4):
    x1, y1 = mp[i]
    x2, y2 = mp[j]
    md = abs(x1 - x2) + abs(y1 - y2)
    md = int(md)
print(md)

Submission status: Wrong Answer

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[i] = x[i] - y[i]
  y[i] = x[i] + y[i]
  
print(max(max(x),max(y))-min(min(x),min(y))-1)

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)

   
    b=max(math.fabs(x-y),b)
    if i==0:
        m=math.fabs(x-y)
    else:
        m=min(math.fabs(x-y),m)
print(int(max(c-v, b-m)))

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
matrix = []
for i in range(n):
  a=[]
  for j in range(1):
    k = input()
    a= [int(i) for i in k.split()]
    matrix.append(a)
mu = []
for i in range(n):
  for j in range (n):
    sum = abs(matrix[i][0]-matrix[j][0])+ abs(matrix[i][1]-matrix[j][0])
    mu.append(sum)
mu.sort()
print(mu[-1])

Submission status: Wrong Answer

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

pos.sort()

print(abs(pos[0][0]-pos[n-1][0])+abs(pos[0][1]-pos[n-1][1]))

Submission status: Wrong Answer

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

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

print(max(f) - min(f))

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

XY = []
for _ in range(N):
    x, y = mapint()
    XY.append((x, y))

XY.sort()
sx, sy = XY[0]
tmp = -1
for nx, ny in XY[1:]:
    if abs(sx-nx)+abs(sy-ny)>tmp:
        tmp = abs(sx-nx)+abs(sy-ny)
        ex, ey = nx, ny

ans_x = -1
for nx, ny in XY:
    if abs(ex-nx)+abs(ey-ny)>ans_x:
        ans_x = abs(ex-nx)+abs(ey-ny)

XY.sort(key=lambda x:x[1])
sx, sy = XY[0]
tmp = -1
for nx, ny in XY[1:]:
    if abs(sx-nx)+abs(sy-ny)>tmp:
        tmp = abs(sx-nx)+abs(sy-ny)
        ex, ey = nx, ny

ans_y = -1
for nx, ny in XY:
    if abs(ex-nx)+abs(ey-ny)>ans_y:
        ans_y = abs(ex-nx)+abs(ey-ny)

print(max(ans_x, ans_y))

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    """
    https://www.quora.com/How-can-I-find-the-maximum-Manhattan-distance-between-2-points-from-a-given-set-of-points
    """
    N = int(input())
    x, y = map(int, input().split())
    maximal = x + y
    minimal = x + y
    for _ in range(N - 1):
        x, y = map(int, input().split())
        maximal = max(maximal, x + y)
        minimal = min(minimal, x + y)
    print(maximal - minimal)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
input=__import__('sys').stdin.readline
def getdist(a,b):return abs(a[0]-b[0])+abs(a[1]-b[1])
n=int(input())
s=[]
for _ in range(n):
    s+=[*map(int,input().split())],
s.sort()
ans=0
for i in s:
    ans=max(ans,getdist(s[0],i))
    ans=max(ans,getdist(s[-1],i))
s.sort(key=lambda x:x[1])
for i in s:
    ans=max(ans,getdist(s[0],i))
    ans=max(ans,getdist(s[-1],i))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
list = []
(a, b) = map(int, input().split())
xmax = a
xmin = a
ymax = b
ymin = b
co1 = (a, b)
co2 = (a, b)
co3 = (a, b)
co4 = (a, b)
for n in range (1, N):
    (a, b) = map(int, input().split())
    if a < xmin:
        xmin = a
        co1 = (a, b)
    if a > xmax:
        xmax = a
        co2 = (a, b)
    if b < ymin:
        ymin = b
        co3 = (a, b)
    if b > ymax:
        ymax = b
        co4 = (a, b)

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

distances = [man(co1, co2), man(co1, co3), man(co1, co4), man(co2, co3), man(co2, co3), man(co3, co4)]

print(max(distances))

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]
    elif x <= B[0] and y >= B[1]:
        B = [x, y]
    elif x >= C[0] and y >= C[1]:
        C = [x, y]
    elif x >= D[0] and y <= D[1]:
        D = [x, y]
    elif x <= A[0] and x <= B[0] and A[1] <= y <= B[1]:
        E = [x, y]
    elif y >= B[1] and y >= C[1] and B[0] <= x <= C[0]:
        F = [x, y]
    elif x >= C[0] and x >= D[0] and D[1] <= y <= C[1]:
        G = [x, y]
    elif y <= A[1] and 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:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
xy = [tuple(MI()) for _ in range(N)]
x_max = max(xy[i][0] for i in range(N))
y_max = max(xy[i][1] for i in range(N))
x_min = min(xy[i][0] for i in range(N))
y_min = min(xy[i][1] for i in range(N))

A = []
B = []
C = []
D = []
for i in range(N):
    x,y = xy[i]
    if x == x_max:
        A.append((x,y))
    if x == x_min:
        B.append((x,y))
    if y == y_max:
        C.append((x,y))
    if y == y_min:
        D.append((x,y))

A = list(set(A))
B = list(set(B))
C = list(set(C))
D = list(set(D))

A.sort()
B.sort()
C.sort()
D.sort()


def dist(a,b):
    a0,a1 = a
    b0,b1 = b
    return abs(a0-b0) + abs(a1-b1)


a1 = D[0]
a2 = D[-1]
a3 = A[0]
a4 = A[-1]
a5 = C[-1]
a6 = C[0]
a7 = B[-1]
a8 = B[0]

print(max(dist(a1,a4),dist(a1,a5),dist(a8,a4),dist(a8,a5),dist(a2,a6),dist(a2,a7),dist(a3,a6),dist(a3,a7)))

Submission status: Wrong Answer

Solution code:
x = input()

max = 1
min = 10**9
mem_max_x = 0
mem_max_y = 0
mem_min_x = 0
mem_min_y = 0

for _ in range(int(x)):
 a = input()
 ax = int(a.split()[0])
 ay = int(a.split()[1])
 l = (ax*ax + ay*ay)**0.5
# l = (ax*1 + ay*1)**1
# print(l)
 if l > max: 
  max = l
  mem_max_x = ax
  mem_max_y = ay
 if l < min:
  min = l
  mem_min_x = ax
  mem_min_y = ay
  
# a<x<b, c<y<d
# manhatan = max - min
#print("manha")
#print( max - min)
print( abs(mem_max_x - mem_min_x) +abs(mem_max_y - mem_min_y))

# bd, ac, ad, bc

Submission status: Wrong Answer

Solution code:
N=int(input())
D=[]
for i in range(N):
  x,y=map(int, input().split())
  D.append((x,y))
D=sorted(D)
a,b=D[0],D[-1]
D=sorted(D,reverse=True, key=lambda x: x[1])
c,d=D[0],D[-1]
F=[a,b,c,d]
ans=0
for i in range(4):
  for j in range(4):
    f=abs(F[i][0]-F[j][0])+abs(F[i][1]-F[j][1])
    ans=max(ans,f)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

top1= 0
bot1= 10**10
top2= 0
bot2= 10**10
for _ in range(n):
	
	x,y = map(int, input().split(' '))
	tot1= x+y
	tot2= x-y
	if tot1> top1:
		top1= tot1
	if tot1< bot1:
		bot1= tot1
	if tot2>top2:
		top2= tot2
	if tot2<bot2:
		bot2= tot2

print(max(top1-bot1, top2-bot2))

Submission status: Wrong Answer

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

man = [0] * N
for i in range(N):
    man[i] = xy[i][0] + xy[i][1]
print(max(man) - min(man))

Submission status: Wrong Answer

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

lst = sorted(lst)
minx, miny = lst[0]
maxx, maxy = lst[0]
maxdist = 0
for i in range(N-1):
  x,y = lst[i+1]
  dist1 = abs(minx - x) + abs(miny - y)
  dist2 = abs(maxx - x) + abs(maxy - y)
  if dist1 > maxdist:
    maxx = x
    maxy = y
    maxdist = dist1
  elif dist2 > maxdist:
    minx = x
    miny = y
    maxdist = dist2
    
print(maxdist)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
xy = tuple(map(int, input().split()))
pM = sum(xy)
pm = sum(xy)
mM = abs(xy[1] - xy[0])
mm = abs(xy[1] - xy[0])
for _ in range(n - 1):
    xy = tuple(map(int, input().split()))
    s = sum(xy)
    d = abs(xy[0] - xy[1])
    if s > pM:
        pM = s
    elif s < pm:
        pm = s
    if d > mM:
        mM = d
    elif d < mm:
        mm = d
print(max(abs(pM-pm), abs(mM-mm)))

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    def manhattan_distance(p1,p2):
        x1,y1 = p1
        x2,y2 = p2
        return abs(x1-x2) + abs(y1-y2)


    N = II()
    # N = 10
    from random import random
    x_first = defaultdict(list)
    y_first = defaultdict(list)
    for i in range(N):
        x,y = LMIIS()
        # x = int(random()*10**2)
        # y = int(random()*10**2)
        x_first[x].append(y)
        y_first[y].append(x)

    candidates = []

    x_keys = x_first.keys()
    y_keys = y_first.keys()
    min_x = min(x_keys)
    max_x = max(x_keys)
    min_y = min(y_keys)
    max_y = max(y_keys)

    vertical_left  = sorted(x_first[min_x])
    candidates.append((min_x, vertical_left[0]))
    candidates.append((min_x, vertical_left[-1]))
    
    vertical_right = sorted(x_first[max_x])
    candidates.append((max_x, vertical_right[0]))
    candidates.append((max_x, vertical_right[-1]))

    horizontal_upper = sorted(y_first[max_y])
    candidates.append((max_y, horizontal_upper[0]))
    candidates.append((max_y, horizontal_upper[-1]))

    horizontal_lower = sorted(y_first[min_y])
    candidates.append((min_y, horizontal_lower[0]))
    candidates.append((min_y, horizontal_lower[-1]))

    ans = 0
    for i in range(len(candidates)):
        for j in range(i+1,len(candidates)):
            ans = max(ans,manhattan_distance(candidates[i],candidates[j]))
    print(ans)
    # dbg(x_first)
    # dbg(y_first)
    # dbg(candidates)


    
main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l1=[]
l2=[]
for _ in range(n):
    x,y=map(int,input().split())
    l1.append(x+y)
    l2.append(abs(x-y))
print(max(max(l1)-min(l1),max(l2)-min(l2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []

for i in range(n):
    x,y = map(int, input().split())
    tmp = x + y
    if i == 0:
      tmp_max = tmp
      tmp_min = tmp
    else:
      if tmp > tmp_max:
        tmp_max = tmp
      if tmp < tmp_min:
        tmp_min = tmp
ans = tmp_max - tmp_min
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
r = []

for i in range(N):
  tmp_x, tmp_y = list(map(int, input().split()))
  x.append(tmp_x)
  y.append(tmp_y)
  r.append((x[i]**2 + y[i]**2)**0.5)
  
tgt = r.index(max(r))

ans = []
for i in range(N):
  ans.append(abs(x[tgt]-x[i])+abs(y[tgt]-y[i]))
print(max(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i],y[i] = map(int,input().split())
ans = 0
x_max = max(x)
xs = list([i for i, a in enumerate(x) if a == x_max])
y_max = max(y)
ys = list([i for i, a in enumerate(y) if a == y_max])
x_min = min(x)
y_min = min(y)
xss = list([i for i, a in enumerate(x) if a == x_min])
yss = list([i for i, a in enumerate(y) if a == y_min])
for i in range(len(xs)):
    for j in range(len(ys)):
          if abs(x[xs[i]] - x[ys[j]]) + abs(y[xs[i]] - y[ys[j]]) > ans:
              ans = abs(x[xs[i]] - x[ys[j]]) + abs(y[xs[i]] - y[ys[j]])
for i in range(len(xss)):
    for j in range(len(yss)):
          if abs(x[xss[i]] - x[yss[j]]) + abs(y[xss[i]] - y[yss[j]]) > ans:
              ans = abs(x[yss[i]] - x[xss[j]]) + abs(y[xss[i]] - y[yss[j]])
for i in range(len(xss)):
    for j in range(len(ys)):
          if abs(x[xss[i]] - x[ys[j]]) + abs(y[xss[i]] - y[ys[j]]) > ans:
              ans = abs(x[xss[i]] - x[ys[j]]) + abs(y[xss[i]] - y[ys[j]])
for i in range(len(xs)):
    for j in range(len(yss)):
          if abs(x[xs[i]] - x[yss[j]]) + abs(y[xs[i]] - y[yss[j]]) > ans:
              ans = abs(x[xs[i]] - x[yss[j]]) + abs(y[xs[i]] - y[yss[j]])
for i in range(len(xss)):
    for j in range(len(xs)):
          if abs(x[xss[i]] - x[xs[j]]) + abs(y[xss[i]] - y[xs[j]]) > ans:
              ans = abs(x[xss[i]] - x[xs[j]]) + abs(y[xss[i]] - y[xs[j]])
for i in range(len(yss)):
    for j in range(len(ys)):
          if abs(x[yss[i]] - x[ys[j]]) + abs(y[yss[i]] - y[ys[j]]) > ans:
              ans = abs(x[yss[i]] - x[ys[j]]) + abs(y[yss[i]] - y[ys[j]])
print(ans)

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    qqqq = 0
    wwww = 1000000000000000000000000000
    for i in range(n):
        x,y = invr()
        q = max(q,x + y)
        qq = max(qq,x - y)
        w = min(w,x + y)
        ww = min(ww,x - y)
        qqqq = max(qqqq,y - x)
        wwww = min(wwww,y - x)
    print(max(q - w,qq - ww,qqqq - wwww))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
for i in range(N):
    a = tuple(map(int, input().split()))
    if a[0] > a[1]:
        x.append((a[0], a[1]))
    else:
        y.append((a[0], a[1]))

x.sort(key=lambda x: x[0] + x[1])
y.sort(key=lambda x: x[0] + x[1])

if len(x) and len(y):
    print(
        max(
            abs(x[0][0] - y[-1][0]) + abs(x[0][1] - y[-1][1]),
            abs(x[-1][0] - y[0][0]) + abs(x[-1][1] - y[0][1]),
            abs(x[0][0] - x[-1][0]) + abs(x[0][1] - x[-1][1]),
            abs(y[-1][0] - y[0][0]) + abs(y[-1][1] - y[0][1]),
        )
    )

elif len(x):
    print(abs(x[-1][0] - x[0][0]) + abs(x[-1][1] - x[0][1]))

else:
    print(abs(y[-1][0] - y[0][0]) + abs(y[-1][1] - y[0][1]))

Submission status: Wrong Answer

Solution code:
import random

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

ans = 0
o = 0
for _ in range(6):
  m = 0
  mp = 0
  for i in range(N):
    d = abs(x[i]-x[o])+abs(y[i]-y[o])
    if d>m:
      m = d
      mp = i
  ans = max(ans, m)
  o = mp
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xy.sort()
dist = [None] * N
for i in range(N):
    dist[i] = abs(xy[i][0] - xy[0][0]) + abs(xy[i][1] - xy[0][1])

s = dist.index(max(dist))
dist2 = [None] * N
for i in range(N):
    dist2[i] = abs(xy[i][0] - xy[s][0]) + abs(xy[i][1] - xy[s][1])
print(max(dist2))

Submission status: Wrong Answer

Solution code:
input=__import__('sys').stdin.readline
n=int(input())
s=[]
for _ in range(n):
    s+=[*map(int,input().split())],
s.sort()
ans=0
ans=max(ans,abs(s[0][0]-s[-1][0])+abs(s[0][1]-s[-1][1]))
s.sort(key=lambda x:x[1])
ans=max(ans,abs(s[0][0]-s[-1][0])+abs(s[0][1]-s[-1][1]))
print(ans)

Submission status: Wrong Answer

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

d = [0]*N
for i in range(N):
    d[i] = xy[i][0] + xy[i][1]

print(max(d) - min(d))

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
s,p=10**10,10**10
t,q=-1,-1

for i in range(n):
  x,y=map(int,input().split())
  s=min(s,x+y)
  t=max(t,x+y)
  p=min(p,x-y)
  q=max(q,x-y)
  
print(max(t-s,q-p))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=[]
for i in range(0,n):
	x1,y1=list(map(int ,input().split()))
	l.append(x1)
	l.append(y1)
for i in range(1,len(l)):
	if(i%2==0):
		j=[]
		formula1=l[i-1]-l[i]
		j.append(abs(formula1))
		
	elif(i%2!=0):
		k=[]
		formula2=l[i-1]-l[i]
		k.append(abs(formula2))
		
myans1=max(j)
myans2=max(k)

print((myans1+myans2))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    coords = []
    for i in range(n):
        x,y = map(int,input().split())
        coords.append(x+y)

    coords.sort()
    print(coords[-1]-coords[0])
    


main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
N = int(input())
Z = [list(map(int,input().split())) for _ in range(N)]
ans = 0
ZX = sorted(Z,key=lambda x: x[0])
ZY = sorted(Z,key=lambda x: x[1])
ZZ = [ZX[0],ZX[-1],ZY[0],ZY[-1]]
for x in itertools.combinations(ZZ,2):
  ans = max(ans, abs(x[0][0]-x[1][0])+abs(x[0][1]-x[1][1]))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    Xmax = [(-INF, 0)]
    Xmin = [(INF, 0)]
    Ymax = [(0, -INF)]
    Ymin = [(0, INF)]
    for _ in range(N):
        x, y = map(int, readline().split())
        if Xmax[0][0] < x:
            Xmax = [(x, y)]
        elif Xmax[0][0] == x:
            Xmax.append((x, y))
        if Xmin[0][0] > x:
            Xmin = [(x, y)]
        elif Xmin[0][0] == x:
            Xmin.append((x, y))
        if Ymax[0][1] < y:
            Ymax = [(x, y)]
        elif Ymax[0][1] == y:
            Ymax.append((x, y))
        if Ymin[0][1] > y:
            Ymin = [(x, y)]
        elif Ymin[0] == y:
            Ymin.append((x, y))

    ans = 0

    for x1, y1 in Xmax:
        for x2, y2 in Xmin:
            ans = max(ans, abs(x1 - x2) + abs(y1 - y2))

    for x1, y1 in Ymax:
        for x2, y2 in Ymin:
            ans = max(ans, abs(x1 - x2) + abs(y1 - y2))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(N):
  x, y = map(int, input().split())
  if i==0:
    x1, y1, x2, y2, x3, y3, x4, y4 = x, y, x, y, x, y, x, y
  else:
    if x<x1 and y<y1:
      x1, y1 = x, y
    elif x<x2 and y>y2:
      x2, y2 = x, y
    elif x>x3 and y>y3:
      x3, y3 = x, y
    elif x>x4 and y<y4:
      x4, y4 = x, y
print(max(abs(x1-x3)+abs(y1-y3),abs(x2-x4)+abs(y2-y4)))

Submission status: Wrong Answer

Solution code:
N=int(input())
minab=10**11
maxab=0
mina=10**11
minb=10**11
maxa=0
maxb=0
for i in range(N):

    a,b=map(int,input().split())
    if  a+b>maxab:
        maxab=a+b
        maxa=a
        maxb=b
    if a+b<minab:
        minab=a+b
        mina=a
        minb=b
    

print(abs(maxa-mina)+abs(maxb-minb))

Submission status: Wrong Answer

Solution code:
def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

n = int(input())
ans = 0
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort()
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[0], -p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], -p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
print(ans)