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:
curr_x = 0
curr_y = 0
num_inputs = int(input())
first_inputs = input().split(" ")
second_inputs = input().split(" ")
if ((int(first_inputs[0])+int(first_inputs[1])) >
    (int(second_inputs[0])+int(second_inputs[1]))):
  max_x = int(first_inputs[0])
  max_y = int(first_inputs[1])
  min_x = int(second_inputs[0])
  min_y = int(second_inputs[1])
else:
  min_x = int(first_inputs[0])
  min_y = int(first_inputs[1])
  max_x = int(second_inputs[0])
  max_y = int(second_inputs[1])
max_dist = abs(max_x - min_x) + abs(max_y - min_y)
# Check if max distance, then capture both pairs -> either could be large or small values.
for i in range(0, num_inputs - 2):
  pair = input().split(" ")
  curr_x = int(pair[0])
  curr_y = int(pair[1])
  curr_dist_max = abs(max_x - curr_x) + abs(max_y - curr_y)
  curr_dist_min = abs(min_x - curr_x) + abs(min_y - curr_y)
  max_min = curr_dist_max > curr_dist_min
  if max_min and (curr_dist_max > max_dist):
    min_x = curr_x
    min_y = curr_y
  elif not(max_min) and (curr_dist_min > max_dist):
    max_x = curr_x
    max_y = curr_y
  print(max_x, max_y, min_x, min_y)
  max_dist =  abs(min_x - max_x) + abs(min_y - max_y)

print(max_dist)

Submission status: Wrong Answer

Solution code:
curr_x = 0
curr_y = 0
num_inputs = int(input())
first_inputs = input().split(" ")
max_x = int(first_inputs[0])
max_y = int(first_inputs[1])
second_inputs = input().split(" ")
min_x = int(second_inputs[0])
min_y = int(second_inputs[1])
max_dist = abs(max_x - min_x) + abs(max_y - min_y)
# Check if max distance, then capture both pairs -> either could be large or small values.
for i in range(0, num_inputs - 2):
  pair = input().split(" ")
  curr_x = int(pair[0])
  curr_y = int(pair[1])
  curr_dist_max = abs(max_x - curr_x) + abs(max_y - curr_y)
  curr_dist_min = abs(min_x - curr_x) + abs(min_y - curr_y)
  max_min = curr_dist_max > curr_dist_min
  if max_min and (curr_dist_max > max_dist):
    min_x = curr_x
    min_y = curr_y
  elif not(max_min) and (curr_dist_min > max_dist):
    max_x = curr_x
    max_y = curr_y
  print(max_x, max_y, min_x, min_y)
  max_dist =  abs(min_x - max_x) + abs(min_y - max_y)

print(max_dist)

Submission status: Wrong Answer

Solution code:
curr_x = 0
curr_y = 0
num_inputs = int(input())
first_inputs = input().split(" ")
max_x = int(first_inputs[0])
max_y = int(first_inputs[1])
second_inputs = input().split(" ")
min_x = int(second_inputs[0])
min_y = int(second_inputs[1])
max_dist = 0
# Check if max distance, then capture both pairs -> either could be large or small values.
for i in range(0, num_inputs - 2):
  pair = input().split(" ")
  curr_x = int(pair[0])
  curr_y = int(pair[1])
  curr_dist_max = abs(max_x - curr_x) + abs(max_y - curr_y)
  curr_dist_min = abs(min_x - curr_x) + abs(min_y - curr_y)
  max_min = curr_dist_max > curr_dist_min
  if max_min and (curr_dist_max > max_dist):
    min_x = curr_x
    min_y = curr_y
  elif not(max_min) and (curr_dist_min > max_dist):
    max_x = curr_x
    max_y = curr_y
  max_dist =  abs(min_x - max_x) + abs(min_y - max_y)

print(max_dist)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

O = XY[0]
S = XY[0]
for xy in XY:
    if dist(O, S) < dist(O, xy):
        S = xy
O = S
for xy in XY:
    if dist(O, S) < dist(O, xy):
        S = xy

print(dist(O, S))

Submission status: Wrong Answer

Solution code:
curr_x = 0
curr_y = 0
num_inputs = int(input())
first_inputs = input().split(" ")
max_x = int(first_inputs[0])
max_y = int(first_inputs[1])
min_x = 0
min_y = 0
max_dist = 0
# Check if max distance, then capture both pairs -> either could be large or small values.
for i in range(0, num_inputs - 1):
  pair = input().split(" ")
  curr_x = int(pair[0])
  curr_y = int(pair[1])
  curr_dist_max = abs(max_x - curr_x) + abs(max_y - curr_y)
  curr_dist_min = abs(min_x - curr_x) + abs(min_y - curr_y)
  max_min = curr_dist_max > curr_dist_min
  if max_min and (curr_dist_max > max_dist):
    min_x = curr_x
    min_y = curr_y
  elif not(max_min) and (curr_dist_min > max_dist):
    max_x = curr_x
    max_y = curr_y
  max_dist =  abs(min_x - max_x) + abs(min_y - max_y)

print(max_dist)

Submission status: Wrong Answer

Solution code:
curr_x = 0
curr_y = 0
num_inputs = int(input())
first_inputs = input().split(" ")
max_x = int(first_inputs[0])
max_y = int(first_inputs[1])
max_dist = 0
curr_dist = 0
for i in range(0, num_inputs - 1):
  pair = input().split(" ")
  curr_x = int(pair[0])
  curr_y = int(pair[1])
  curr_dist = abs(max_x - curr_x) + abs(max_y - curr_y)
  if curr_dist > max_dist:
    max_x = curr_x
    max_y = curr_y
    max_dist = curr_dist

print(max_dist)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    xy = [list(map(int, rl().split())) for _ in range(N)]
    xy.sort(key=lambda n: sum(n))
    ans = sum(xy[-1]) - sum(xy[0])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
plus_max = 0
plus_min = 10**20
minus_max = 0
minus_min = 10**20
for _ in range(n):
    x, y = map(int, input().split())
    plus_max = max(plus_max, x + y)
    plus_min = min(plus_min, x + y)
    minus_max = max(minus_max, x - y)
    minus_min = min(minus_min, x - y)
print(max(plus_max - plus_min, minus_max - minus_min))

Submission status: Wrong Answer

Solution code:
n = int(input())
plus_max = 0
plus_min = 10**10
minus_max = 0
minus_min = 10**10
for _ in range(n):
    x, y = map(int, input().split())
    plus_max = max(plus_max, x + y)
    plus_min = min(plus_min, x + y)
    minus_max = max(minus_max, x - y)
    minus_min = min(minus_min, x - y)
print(max(plus_max - plus_min, minus_max - minus_min))

Submission status: Wrong Answer

Solution code:
n=int(input())
z_max,z_min=0,10**10
w_max,w_min=0,10**10
for i in range(n):
    a,b=map(int,input().split())
    z=a+b
    w=a-b
    z_max=max(z_max,z)
    z_min=min(z_min,z)
    w_max=max(w_max,w)
    w_min=min(w_min,w)
print(max(z_max-z_min,w_max-w_min))

Submission status: Wrong Answer

Solution code:
n = int(input())
m = []
for _ in range(n):
  l = list(map(int,input().split()))
  m.append(l)
mx = float('-inf')
for i in range(n):
  for j in range(i+1,n):
    mx = max(mx,abs(m[i][0]+m[j][0])+abs(m[i][1]+m[i][1]))
print(mx)

Submission status: Wrong Answer

Solution code:
# Fast IO (be careful about bytestring, not on interactive)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())

sumList = []
subList = []

for _ in range(N):
    x,y = map(int,input().split())
    sumList.append(x + y)
    subList.append(x - y)

print(max(max(sumList),max(subList)))

Submission status: Wrong Answer

Solution code:
n = int(input())
# 各点のy=xへの写像を考える
x = []
y = []
t = []
for i in range(n):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    t.append([xi+yi, i])
t.sort(key=lambda x:x[0])
#print(t)
min_idx = t[0][1]
max_idx = t[-1][1]
ans = abs(x[max_idx]-x[min_idx]) + abs(y[max_idx]-y[min_idx])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def cos(v1, v2):
  if (v1 == np.array([0,0])).all() or (v2 == np.array([0,0])).all():
    return -1
  naiseki = 0
  for i in range(len(v1)):
    naiseki += (v1[i] * v2[i])
  asize = (v1**2).sum()
  bsize = (v2**2).sum()
  return naiseki/asize/bsize

N = int(input())
XY = []
for i in range(N):
  XY.append([int(i) for i in input().split()])

XY = np.array(XY)
X = XY[:,0]
Y = XY[:,1]
xmaxi = np.argmax(X)
xmini = np.argmin(X)
ymaxi = np.argmax(Y)
ymini = np.argmin(Y)
v1 = XY[ymaxi] - XY[xmini]
v2 = XY[ymaxi] - XY[xmaxi]
v3 = XY[xmini] - XY[ymini]
v4 = XY[xmaxi] - XY[ymini]
cand = []
for xy in XY:
  if cos(v1,xy) >= 0 or cos(xy,v2) >= 0 or cos(v3,xy) >= 0 or cos(xy,v4) >= 0:
    cand.append(xy)

manh=[]
for xy in cand:
  for xxyy in cand:
    manh.append(abs(xy[0] - xxyy[0]) + abs(xy[1] - xxyy[1]))
if manh == []:
  print(0)
  exit()
print(max(manh))

Submission status: Wrong Answer

Solution code:
n = int(input())
# 各点のy=xへの写像を考える
x = []
y = []
t = []
for i in range(n):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    t.append([xi+yi, i])
t.sort(key=lambda x:x[0])
print(t)
min_idx = t[0][1]
max_idx = t[-1][1]
ans = abs(x[max_idx]-x[min_idx]) + abs(y[max_idx]-y[min_idx])
print(ans)

Submission status: Wrong Answer

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

fn=[lambda x:x[0]+x[1],lambda x:x[0]+x[1]]
ans=0
for f in fn:
    xy.sort(key = f)
    ans=max(ans,abs(f(xy[0])-f(xy[-1])))
print(ans)

Submission status: Wrong Answer

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

th = pow(10, 9)
right_up_max = 0
left_down_min = th
left_up_max = 0
right_down_min = th

for x, y in xy_array:
    right_up_max = max(x + y, right_up_max)
    left_down_min = min(x + y, left_down_min)
    left_up_max = max(th - x + y, left_up_max)
    right_down_min = min(th - x + y, right_down_min)

ans = max(right_up_max - left_down_min, left_up_max - right_down_min)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from scipy.spatial import distance


def main():
    N = int(input())
    xy = [list(map(int,input().split())) for i in range(N)]

    xy = np.array(xy)

    print(0)



main()

Submission status: Wrong Answer

Solution code:
N = int(input())
i = 0
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 1-10**9

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    
    if sub > s_max:
        s_max = sub
    if sub < s_min:
        s_min = sub

d_add = a_max - a_min
d_sub = s_max - s_min

#if d_add >= d_sub:
#    print(d_add)
#if d_add < d_sub:
#    print(d_sub)
print(max(d_add,d_sub))

Submission status: Wrong Answer

Solution code:
l, m = list(), list()
for _ in range(int(input())):
    x, y = map(int, input().split())
    l.append([x, y])
    m.append([y, x])
l.sort(), m.sort()
print(max(l[-1][0]-l[0][0]+l[-1][1]-l[0][1], m[-1][0]-l[0][0]+l[-1][1]-l[0][1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
i = 0
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 10**9-1

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    
    if sub > s_max:
        s_max = sub
    if sub < s_min:
        s_min = sub

d_add = a_max - a_min
d_sub = s_max - s_min

#if d_add >= d_sub:
#    print(d_add)
#if d_add < d_sub:
#    print(d_sub)
print(max(d_add,d_sub))

Submission status: Wrong Answer

Solution code:
n = int(input())


max_z = 0
min_z = 10**10
max_w = 0
min_w = 10**10

for _ in range(n):
    x, y = map(lambda x: int(x), input().split())
    max_z = max(max_z, x + y)
    min_z = min(min_z, x + y)
    max_w = max(max_w, x - y)
    min_w = min(min_w, x - y)

print(max(max_z-min_z, max_w-min_w))

Submission status: Wrong Answer

Solution code:

n = int(input())
points = []
min1, max1 = float('inf'), float('-inf')
min2, max2 = float('inf'), float('-inf')

for tp in range(n):
    x, y = map(int, input().split())
    max1 = max(max1, x+y)
    min1 = min(min1, x+y)

    max2 = max(max1, x-y)
    min2 = max(min2, x-y)
    
ans = max(max1 - min1, max2 - min2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
i = 0
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 10**9-1

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    if sub > s_max:
        s_max = sub
    if sub < s_max:
        s_max = sub

d_add = a_max - a_min
d_sub = s_max - s_min

if d_add >= d_sub:
    print(d_add)
if d_add < d_sub:
    print(d_sub)
#print(max(d_add,d_sub))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 10**9-1

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    if sub > s_max:
        s_max = sub
    if sub < s_max:
        s_max = sub

d_add = a_max - a_min
d_sub = s_max - s_min

if d_add >= d_sub:
    print(d_add)
if d_add < d_sub:
    print(d_sub)

Submission status: Wrong Answer

Solution code:
N = int(input())
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 10**9-1

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    if sub > s_max:
        s_max = sub
    if sub < s_max:
        s_max = sub

d_add = a_max - a_min
d_sub = s_max - s_min

print(max(d_add,d_sub))

Submission status: Wrong Answer

Solution code:
N = int(input())
a_max = 2
a_min = 2*(10**9)
s_max = 0
s_min = 10**9

for i in range(N):
    x,y=map(int,input().split())
    add = x+y
    sub = x-y

    if add > a_max:
        a_max = add
    if add < a_min:
        a_min = add
    if sub > s_max:
        s_max = sub
    if sub < s_max:
        s_max = sub

d_add = a_max - a_min
d_sub = s_max - s_min

print(max(d_add,d_sub))

Submission status: Wrong Answer

Solution code:
n = int(input())
maxx1 =maxx2 =0
minn1 = minn2 =  2000000001
for i in range(n):
    x,y = map(int,input().split())
    minn1 = min(minn1,x+y)
    maxx1 = max(maxx1,x+y)
    minn2 = min(minn2,x-y)
    maxx2 = max(maxx2,x-y)
print(max(maxx1-minn1,maxx2-minn2))

Submission status: Wrong Answer

Solution code:
n = int(input())
maxx1 =maxx2 =0
minn1 = minn2 =  2000000001
for i in range(n):
    x,y = map(int,input().split())
    minn1 = min(minn1,x+y)
    maxx1 = max(maxx1,x+y)
    minn2 = min(minn2,abs(x-y))
    maxx2 = max(maxx2,abs(x-y))
print(max(maxx1-minn1,maxx2+minn2))

Submission status: Wrong Answer

Solution code:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
for i in range(0,n):#左上
    maxlocal=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

Submission status: Wrong Answer

Solution code:

N = int(input())

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

#f = [[0]*2 for i in range(N)]
X=[]
Y=[]
for i in range(N):
    #f[i][0] = x[i]-x[i]
    #f[i][1] = x[i]+y[i]
    X.append(x[i]-x[i])
    Y.append(x[i]+y[i])

dam1 = max(X) - min(X)
dam2 = max(Y) - min(Y)
print(max(dam1,dam2))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n):
  l.append(list(map(int,input().split())))
def ma(start, end):
       sx, sy = start
       ex, ey = end
       return abs(ex - sx) + abs(ey - sy)
k = []
for i in l:
  a,b = i
  k.append([a+b,[a,b],i])
  k.append([a-b,[a,-b],i])
  k.append([b-a,[-a,b],i])
  k.append([-a-b,[-a,-b],i])
k.sort()
m = [i for i in k]
m.reverse()
a,b = 0,0
while(True):
  if -k[a][0] + m[b][0] == ma(k[a][2] ,m[b][2]):
    print(ma(k[a][2] ,m[b][2]))
    quit()
  else:
    if k[a+1][0] - k[a][0] >= -m[b+1][0] + m[b][0]:
      a += 1
    else:
      b += 1

Submission status: Wrong Answer

Solution code:
def solve(xy):
    ans = 0
    pos = [xy[0] for _ in range(4)]

    for p in xy:
        if pos[0][0] + pos[0][1] < p[0] + p[1]:
            pos[0] = p
        if pos[1][0] + pos[1][1] > p[0] + p[1]:
            pos[1] = p
        if pos[2][0] - pos[2][1] < p[0] - p[1]:
            pos[2] = p
        if pos[3][0] - pos[3][1] > p[0] - p[1]:
            pos[3] = p

    return max(pos[0][0]+pos[0][1]-pos[1][0]-pos[1][1], pos[2][0]+pos[2][1]-pos[3][0]-pos[3][1])


if __name__ == "__main__":
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]
    print(solve(xy))

Submission status: Wrong Answer

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

    print(max(candidates)-min(candidates))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

tmp1 = []
tmp2 = []
for i in range(n):
    tmp1.append([xy[i][0]+xy[i][1], xy[i][0], xy[i][1]])
    tmp2.append([xy[i][0]-xy[i][1], xy[i][0], xy[i][1]])
tmp1.sort()
tmp2.sort()

if n <= 1000:
    ii = n
    jj = n+1
else:
    ii = 1000
    jj = 1000

ans = 0
for i in range(ii):
    for j in range(1, jj):
        if (tmp1[-j][2]-tmp1[i][2]) >= (tmp1[-j][1]-tmp1[i][1]):
            tmp = tmp1[-j][0]-tmp1[i][0]
            ans = max(tmp, ans)
        if (tmp2[-j][2]-tmp2[i][2]) < (tmp2[-j][1]-tmp2[i][1]):
            tmp = tmp2[-j][0]-tmp2[i][0]
            ans = max(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
for i in range(0,n):#左上
    local=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

Submission status: Wrong Answer

Solution code:
def solve(xy):
    ans = 0
    pos = [xy[0] for _ in range(4)]

    for p in xy:
        if pos[0][0] + pos[0][1] < p[0] + p[1]:
            pos[0] = p
        if pos[1][0] + pos[1][1] > p[0] + p[1]:
            pos[1] = p
        if pos[2][0] - pos[2][1] < p[0] - p[1]:
            pos[2] = p
        if pos[3][0] - pos[3][1] < p[0] - p[1]:
            pos[3] = p

    return max(pos[0][0]+pos[0][1]-pos[1][0]-pos[1][1], pos[2][0]+pos[2][1]-pos[3][0]-pos[3][1])


if __name__ == "__main__":
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]
    print(solve(xy))

Submission status: Wrong Answer

Solution code:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=0
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
for i in range(0,n):#左上
    local=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

Submission status: Wrong Answer

Solution code:
def solve(xy):
    ans = 0
    pos = [xy[0] for _ in range(4)]

    for p in xy:
        if pos[0][0] + pos[0][1] < p[0] + p[1]:
            pos[0] = p
        if pos[1][0] + pos[1][1] > p[0] + p[1]:
            pos[1] = p
        if pos[2][0] - pos[2][1] < p[0] - p[1]:
            pos[2] = p
        if pos[3][0] - pos[3][1] < p[0] - p[1]:
            pos[3] = p

    return max(pos[0][0]+pos[0][1]-pos[1][0]-pos[1][0], pos[2][0]+pos[2][1]-pos[3][0]-pos[3][0])


if __name__ == "__main__":
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]
    print(solve(xy))

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    D = 16
    x1 = y1 = 10**9+1
    x2 = y2 = 0
    vis = set()
    for xy in zip(it, it):
        if xy in vis:
            continue
        vis.add(xy)
        x, y = xy
        x1 = min(x1, x); x2 = max(x2, x)
        y1 = min(y1, y); y2 = max(y2, y)
    dd = max(1, (x2-x1) // D, (y2-y1) // D)
    dx = (x2-x1)//dd + 2
    dy = (y2-y1)//dd + 2
    d = [[[] for j in range(dx)] for i in range(dy)]

    md = [[] for i in range(dx+dy-1)]
    for b1 in range(dy):
        for b2 in range(b1, dy):
            b3 = abs(b2 - b1)
            for a1 in range(dx):
                for a2 in range(dx):
                    a3 = abs(a2 - a1)
                    md[a3+b3].append((a1, b1, a2, b2))

    for xy in vis:
        x, y = xy
        ix = (x-x1) // dd
        iy = (y-y1) // dd
        d[iy][ix].append(xy)


    ans = 0
    for md1 in reversed(md):
        for x1, y1, x2, y2 in md1:
            for xx1, yy1 in d[y1][x1]:
                for xx2, yy2 in d[y2][x2]:
                    val = abs(xx1-xx2) + abs(yy1-yy2)

                    ans = max(ans, val)
        if ans:
            break
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
import bisect


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N =int(input())

    W_max =0
    W_min= 10**9
    Y_max=0
    Y_min=10**9

    for i in range(N):
        x,y =map(int,input().split())
        W_max =max(W_max,x+y)
        W_min =min(W_min,x+y)
        Y_max =max(Y_max,x-y)
        Y_min =min(Y_min,x-y)

    print(max(W_max - W_min,Y_max - Y_min))






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
# L = [LIST() for i in range(N)]

zmax, zmin, wmax, wmin = 0, 10 ** 9, 0, 10 ** 9
# for i in range(N):
for i in range(N):
    x, y = MAP()
    zmax = max(zmax, x + y)
    zmin = min(zmin, x + y)
    wmax = max(wmax, x - y)
    wmin = min(wmin, x - y)
print(max(zmax - zmin, wmax - wmin))

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]))
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,y=map(int, input().split())
mn = x+y
minx = x
miny = y
mx = x+y
maxx = x
maxy = y  

for i in range(n-1):
    x,y=map(int, input().split())
    if mn > x+y:
        mn = x+y
        minx = x
        miny = y
    elif mx < x+y:
        mx = x+y
        maxx = x
        maxy = y

print(abs(maxx-minx)+abs(maxy-miny))

Submission status: Wrong Answer

Solution code:
n=int(input())
xbox=[]
ybox=[]
for i in range(n):
    x,y = map(int,input().split())
    xbox.append(x)
    ybox.append(y)
xmax=max(xbox)
ymax=max(ybox)
box=[]
for i in range(n):
    box.append(xmax+ymax-xbox[i]-ybox[i])
print(max(box)-min(box))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
xy = [0] * n

xy_plus_max = 0
xy_plus_min = 10 ** 10
xy_minus_max = 0
xy_minus_min = 10 ** 10
for i in range(n):
    x, y = map(int, input().split())
    xy_plus_max = max(xy_plus_max, abs(x + y))
    xy_plus_min = min(xy_plus_min, abs(x + y))
    xy_minus_max = max(xy_minus_max, abs(x - y))
    xy_minus_min = min(xy_minus_min, abs(x - y))

print(max(xy_plus_max - xy_plus_min, xy_minus_max - xy_minus_min))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int,input().split())))
a,b=xy[0]
m1=a+b
p1=xy[0]
m2=a-b
p2=xy[0]
p3=xy[0]
p4=xy[0]
m3=-a-b
m4=-a+b

for x,y in xy:
    if x+y > m1:
        p1 = [x,y]
    if x-y > m2:
            p2 = [x,y]
    if -x-y > m3:
            p3 = [x,y]
    if -x+y > m4:
            p4 = [x,y]
m = 0
for x0,y0 in [p1,p2,p3,p4]:
    for x1,y1 in [p1,p2,p3,p4]:
        dis=abs(x0-x1) + abs(y0-y1)
        if dis > m:
            m = dis
print(m)

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]))
arr3 = sorted(arr , key = lambda x : abs(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())
z = []
zz = []
for _ in range(N):
    x, y = map(int, input().split())
    zz.append(x-y)
    z.append(x+y)
z.sort()
zz.sort()
ans = z[-1]-z[0]
ans = max(ans, zz[-1]+zz[0])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
N = int(readline())
A = []
B = []
for _ in range(N):
    x, y = map(int, readline().split())
    A.append(abs(x-y))
    B.append(abs(x+y))
print(max(max(A) - min(A), max(B) - min(B)))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = set([])
for i in range(n):
    x = tuple(map(int, input().split()))
    s.add(x)
s = list(s)
n = len(s)
t = sorted(s)
u = sorted(s, key=lambda x: x[1])
res = 0

for X in [t[0], u[0], t[-1], u[-1], t[n // 2], u[n // 2], t[-1 + n // 2], u[-1 + n // 2]]:
    for Y in [t[0], u[0], t[-1], u[-1], t[n // 2], u[n // 2], t[-1 + n // 2], u[-1 + n // 2]]:
        tmp = abs(X[0] - Y[0]) + abs(X[1] - Y[1])
        res = max(res, tmp)
print(res)

Submission status: Wrong Answer

Solution code:
def maxAbsValExpr(x, y):
    res = 0
    for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
        smallest = p * x[0] + q * y[0] + 0
        for i in range(len(x)):
            cur = p * x[i] + q * y[i] + i
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res

if __name__ == '__main__':

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

    for _ in range(N):
        x_, y_ = map(int, input().split())
        x.append(x_)
        y.append(y_)

    print(maxAbsValExpr(x, y) - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
table = [[int(i) for i in input().split()] for N in range(N)]

a = -1
b = 10**9 * 2 + 1
c = -1
d = 10**9 * 2 + 1
for i in range(N):
    p = table[i][0]
    q = table[i][1]
    if a < p+q:
        a = p+q
    if b > p+q:
        b = p+q
    if c < p-q:
        c = p-q
    if d > p-q:
        d = p-q

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

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [None]*n
y = [None]*n

for i in range(n):
    x[i],y[i] = map(int,input().split())
    
d_from0 = 0
p_far = 0
x_0 = x[0]
y_0 = y[0]

for i in range(n):
    d = abs(x[i]-x_0)+abs(y[i]-y_0)
    if d > d_from0:
        d_from0 = d

ps = [None,None]

for i in range(n):
    d = abs(x[i]-x_0)+abs(y[i]-y_0)
    if d == d_from0:
        if (x[i]-x_0)*(y[i]-y_0)>=0:
            ps[0] = i
        else:
            ps[1] = i

anses = []

for p in ps:
    if p == None:
        continue
    x_p = x[p]
    y_p = y[p]
    ans = 0
    for i in range(n):
        d = abs(x[i]-x_p)+abs(y[i]-y_p)
        if d > ans:
            ans = d
    anses.append(ans)
print(max(anses))