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())
A=[list(map(int, input().split()))  for _ in range(N)]
maxd=0
for i in range(N-1):
    for j in range(i,N-1):
        maxd=max(maxd,abs(A[i][0]-A[j][0])+abs(A[i][1]-A[j][1]))

print(maxd)

Submission status: Wrong Answer

Solution code:
N = int(input())
x, y = map(int, input().split())
d = [x - y, x - y, x + y, x + y]
for i in range(1,N):
  x, y = map(int, input().split())
  d[0] = max(d[0], x-y)
  d[1] = min(d[1], x-y)
  d[2] = max(d[2], x+y)
  d[3] = min(d[3], x+y)
print(d)
print(max(d[0]-d[1], d[2]-d[3]))

Submission status: Wrong Answer

Solution code:
def md(x1, y1, x2, y2):
  return abs(x1 - x2) + abs(y1 - y2)

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

maxd = 0
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    else:
      d = md(Coordinates[i][0], Coordinates[i][1], Coordinates[j][1], Coordinates[j][1])
      if d > maxd:
        maxd = d
print(maxd)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(i+1,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)

print(distance)
max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)

print(distance)
max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Wrong Answer

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

N = int(input())

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

ans = 0
tmp = 0
ind1 = 0
ind2 = 0
for i in range(N):
  for j in range(N): 
    if dist((x[ind1], y[ind1]), (x[j], y[j])) >tmp:
      tmp = dist((x[ind1], y[ind1]), (x[j], y[j])) 
      ind2 = j
  if ans == tmp:
    break
  else:
    ans = tmp
    ind1 = ind2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)-1):
  temp = abs(x[i] - x[1+i]) + abs(y[i] - y[1+i])
  distance.append(temp)

max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(i+1,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)
print(distance)

max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(i,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)
print(distance)

max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())

x = []
y = []
distance = []


for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)

for i in range(len(x)):
  for j in range(i+1,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)

max = 0

for i in range(len(distance)-1):
  if distance[i] > distance[i+1]:
    max = distance[i]

print(max)

Submission status: Wrong Answer

Solution code:
n=int(input())

x=[]
y=[]

for i in range(n):
  s,t=map(int,input().split())
  x.append(s+t)
  y.append(abs(s-t))

print(max(max(x)-min(x),max(y)-min(y)))

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [[None] for i in range(N)]

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

p.sort()
#print(p)

INFINITE = 5 * 10**9
maxUp = {}
minDown = {}

for i in range(1, N):
    maxUp[i] = max(maxUp.get(i-1, -INFINITE), p[i-1][1] - p[i-1][0])
for i in range(1, N):
    minDown[i] = min(minDown.get(i-1, INFINITE), - p[i-1][0] - p[i-1][1])

#print(maxUp)
#print(minDown)

ans = -INFINITE
for i in range(1, N):
    ans = max(ans, 
        p[i][0] - p[i][1] + maxUp.get(i, -INFINITE)
    )
    ans = max(ans, 
        p[i][0] + p[i][1] + minDown.get(i, -INFINITE)
    )
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [[None] for i in range(N)]

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

p.sort()
#print(p)

INFINITE = 5 * 10**9
maxUp = {}
minDown = {}

for i in range(1, N):
    maxUp[i] = max(maxUp.get(i-1, -INFINITE), p[i-1][1] - p[i-1][0])
for i in range(1, N):
    minDown[i] = min(minDown.get(i-1, INFINITE), - p[i-1][0] - p[i-1][1])

#print(maxUp)
#print(minDown)

ans = -INFINITE
for i in range(1, N):
    ans = max(ans, 
        p[i][0] - p[i][1] + maxUp.get(i, -INFINITE)
    )
    ans = max(ans, 
        p[i][0] + p[i][1] + minDown.get(i, INFINITE)
    )
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    coordinates=[]
    for _ in range(N):
        coordinates.append(list(map(int,input().split())))
    maxx=-10**20
    minn=10**20
    posMax,posMin=-1,-1
    for i in range(N):
        if maxx<(coordinates[i][0]+coordinates[i][1]):
            maxx=coordinates[i][0]+coordinates[i][1]
            posMax=i
        if minn>(coordinates[i][0]+coordinates[i][1]):
            minn=coordinates[i][0]+coordinates[i][1]
            posMin=i
    print(abs(coordinates[posMax][0]-coordinates[posMin][0])+abs(coordinates[posMax][1]-coordinates[posMin][1]))
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())

maxx = 1
minx = 10**9
maxy = 1
miny = 10**9
maxx_l = []
minx_l = []
maxy_l = []
miny_l = []

for i in range(N):
    x, y = map(int, input().split())
    if x == maxx:
        maxx_l.append([x,y])
    elif x > maxx:
        maxx = x
        maxx_l = [[x,y],]

    if x == minx:
        minx_l.append([x,y])
    elif x < minx:
        minx = x
        minx_l = [[x,y],]

    if y == maxy:
        maxy_l.append([x,y])
    elif y > maxy:
        maxy = y
        maxy_l = [[x,y],]

    if y == miny:
        miny_l.append([x,y])
    elif y < miny:
        miny = y
        miny_l = [[x,y],]

xy = maxx_l
xy.extend(minx_l)
xy.extend(maxy_l)
xy.extend(miny_l)

def md(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

s = set()
for i,j in itertools.product(xy, xy):
    s.add(md(i[0], i[1],j[0], j[1]))

print(max(s))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

max = 0
for i in range(N):
    for j in range(i+1,N):
        dist = abs(dots[i][0]-dots[j][0])+abs(dots[i][0]-dots[j][0])
        if dist > max:
            max = dist

print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
q = [[x+y, x-y] for x, y in p]
print(max(max(q)[0] - min(q)[0], max(q, key=lambda x: x[1])[0] - min(q, key=lambda x: x[1])[0]))

Submission status: Wrong Answer

Solution code:
x = int(input())

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

print(max(l)-min(l))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    points = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        points[i] = (x, y)
    ans = 0
    topright = points[0][0] + points[0][1]
    bottomright = points[0][0] - points[0][1]
    for i in range(N):
        tr = points[i][0] + points[i][1]
        br = points[i][0] - points[i][1]
        ans = max([ans, abs(topright - tr), abs(bottomright - br)])
        topright = max(topright, tr)
        bottomright = max(bottomright, br)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def man(x , y):
    return abs(x[0]-y[0]) + abs(x[1]-y[1])

from collections import deque
n = int(input())
ten = [tuple(map(int,input().split())) for i in range(n)]
ten.sort()
a = ten[0]
b = ten[1]
ans = abs(a[0]-b[0]) + abs(a[1]-b[1])

if n == 2:
    print(ans)
    exit()

for i in range(2,n):
    now = ten[i]
    nowa = man(a,now)
    nowb = man(b,now)
    
    if ans >= max(nowa,nowb):
        continue
    elif nowa == nowb:
        b = now
        ans = nowa
    elif nowa > nowb:
        b = now
        ans = nowa
    elif nowa < nowb:
        a = now
        ans = nowb
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(min(a1 - a2, b1 - b2))

main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b1, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()

Submission status: Wrong Answer

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

for i in range(n):
  x, y = map(int, input().split())
  d = abs(x) + abs(y)
  list1.append(d)
ans = max(list1) - min(list1)
print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
ll = []
x_test = []
y_test = []
xx = []
yy = []
val = []
for i in range(num):
    x,y = list(map(int,input().split()))
    ll.append([x,y])
for j in ll:
    x_test.append(j[0])
for k in ll:
    y_test.append(k[1])
for m in range(len(x_test)-1):
    test = abs(x_test[m]-x_test[m+1])
    xx.append(test)
for n in range(len(y_test)-1):
    tests = abs(y_test[n] - y_test[n + 1])
    yy.append(tests)
for o in range(len(xx)):
    vals = xx[o] + yy[o]
    val.append(vals)
print(max(val))

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10 ** 9
y_min_pos = [INF, []]
x_min_pos = [INF, []]
y_max_pos = [0, []]
x_max_pos = [0, []]
for _ in range(N):
    # print(x_min_pos, y_min_pos, y_max_pos, x_max_pos)
    x, y = map(int, input().split())
    if y <= y_min_pos[0]:
        if y == y_min_pos[0]:
            y_min_pos[1].append(x)
        else:
            y_min_pos = [y, [x]]
    if y >= y_max_pos[0]:
        if y == y_max_pos[0]:
            y_max_pos[1].append(x)
        else:
            y_max_pos = [y, [x]]

    if x <= x_min_pos[0]:
        if x == x_min_pos[0]:
            x_min_pos[1].append(y)
        else:
            x_min_pos = [x, [y]]
    if x >= x_max_pos[0]:
        if x == x_max_pos[0]:
            x_max_pos[1].append(y)
        else:
            x_max_pos = [x, [y]]
# print(x_max_pos[1])
x_min_ymax = max(x_min_pos[1])
x_max_ymax = max(x_max_pos[1])
y_min_xmax = max(y_min_pos[1])
y_max_xmax = max(y_max_pos[1])
x_min_ymin = min(x_min_pos[1])
x_max_ymin = min(x_max_pos[1])
y_min_xmin = min(y_min_pos[1])
y_max_xmin = min(y_max_pos[1])

y_min_max = max(
    abs(y_min_xmax - x_min_pos[0]) + abs(y_min_pos[0] - x_min_ymax),
    abs(y_min_xmax - y_max_xmin) + abs(y_min_pos[0] - y_max_pos[0]),
    abs(y_min_xmin - x_max_pos[0]) + abs(y_min_pos[0] - x_max_ymax),
    abs(y_min_xmin - y_max_xmax) + abs(y_min_pos[0] - y_max_pos[0]),
)
y_max_max = max(
    abs(y_max_xmax - x_min_pos[0]) + abs(y_max_pos[0] - x_min_ymin),
    abs(y_max_xmax - y_min_xmin) + abs(y_max_pos[0] - y_min_pos[0]),
    abs(y_max_xmin - x_max_pos[0]) + abs(y_max_pos[0] - x_max_ymin),
    abs(y_max_xmin - y_max_xmax) + abs(y_max_pos[0] - y_min_pos[0]),
)
x_min_max = max(
    abs(x_min_ymax - y_min_pos[0]) + abs(x_min_pos[0] - y_min_xmax),
    abs(x_min_ymax - x_max_ymin) + abs(x_min_pos[0] - x_max_pos[0]),
    abs(x_min_ymin - y_max_pos[0]) + abs(x_min_pos[0] - y_max_xmax),
    abs(x_min_ymin - x_max_ymax) + abs(x_min_pos[0] - x_max_pos[0]),
)
x_max_max = max(
    abs(x_max_ymax - y_min_pos[0]) + abs(x_max_pos[0] - y_min_xmin),
    abs(x_max_ymax - x_min_ymin) + abs(x_max_pos[0] - x_min_pos[0]),
    abs(x_max_ymin - y_max_pos[0]) + abs(x_max_pos[0] - y_max_xmin),
    abs(x_max_ymin - x_min_ymax) + abs(x_max_pos[0] - x_min_pos[0]),
)
print(max(y_min_max, y_max_max, x_min_max, x_max_max))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    pt = []
    for _ in range(n):
        x,y = map(int,input().split())
        pt.append([y/x,x,y])
    pt.sort()
    ans = 0
    d = 0
    for i in range(n):
        if abs(pt[0][1]-pt[i][1]) + abs(pt[0][2]-pt[i][2]) > ans:
            ans = abs(pt[0][1]-pt[i][1]) + abs(pt[0][2]-pt[i][2])
            d = i
    for i in range(1,n):
        m = 0
        for j in range(d,n):
            if m < abs(pt[i][1]-pt[j][1]) + abs(pt[i][2]-pt[j][2]):
                m = abs(pt[i][1]-pt[j][1]) + abs(pt[i][2]-pt[j][2])
            else:
                break
            if m>ans:
                ans = m
                d = i
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
  x,y = map(int, input().split())
  a.append(x+y)
  b.append(abs(x-y))
a.sort()
b.sort()

ans = a[-1]-a[0]
c = b[-1]-b[0]
print (max(ans,c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
  x,y = map(int, input().split())
  a.append(x+y)
  b.append(abs(x-y))
a.sort()
b.sort()

ans = a[-1]-a[0]
c = b[-1]+b[0]
print (max(ans,c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
  x,y = map(int, input().split())
  a.append(x+y)
a.sort()

ans = a[-1]-a[0]
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 = -th
left_down_min = th
left_up_max = -th
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:
n = int(input())
xy_array = [list(map(int, input().split())) for _ in range(n)]

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

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:
n=int(input())
a=[]
j=k=0
def s(a):
    return a[0]+a[1]
for i in range(n):
    f=list(map(int,input().split()))
    a.append(f)
print(max(map(s,a))-min(map(s,a)))

Submission status: Wrong Answer

Solution code:
def solve(n, x, y):
    x_min, x_max = min(x), max(x)
    y_min, y_max = min(y), max(y)
    S = set([
        min(filter(lambda p: p[1]==y_min, zip(x,y))),
        min(filter(lambda p: p[1]==y_max, zip(x,y))),
        max(filter(lambda p: p[1]==y_min, zip(x,y))),
        max(filter(lambda p: p[1]==y_max, zip(x,y))),
        min(filter(lambda p: p[0]==x_min, zip(x,y))),
        min(filter(lambda p: p[0]==x_max, zip(x,y))),
        max(filter(lambda p: p[0]==x_min, zip(x,y))),
        max(filter(lambda p: p[0]==x_max, zip(x,y)))
    ])
    best = 0
    for x1, y1 in S:
        for x2, y2 in S:
            best = max(best, abs(x1-x2) + abs(y1-y2))
    return best

n = int(input())
x, y = zip(*[map(int, input().split()) for i in range(n)])
print(solve(n, x, y))

Submission status: Wrong Answer

Solution code:
N =  int(input())
A =  [list(map(int, (input().split(' ')))) for i in range(N)]

hoge = [sum(a) for a in A]
print(max(hoge) - min(hoge))

Submission status: Wrong Answer

Solution code:
arr = []; arr2 = []
for i in range(int(input())):
    a, b = list(map(int, input().split(" ")))
    arr.append([a, b])
    arr2.append([b, a])
# print(arr)
m1, m2 = min(arr), max(arr)
n1, n2 = min(arr2), max(arr2)
print(max(abs(m1[0]-m2[0]) + abs(m1[1] - m2[1]), abs(n1[0]-n2[0]) + abs(n1[1] - n2[1])))

Submission status: Wrong Answer

Solution code:
"""AtCoder Beginner Contest 178.

E
"""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


def calc(p1: list, p2: list) -> int:
    """Calc Manhattan Distance."""
    return abs(p2[1] - p1[1]) + abs(p2[0] - p1[0])


def main():
    """Run."""
    n = int(input())

    p1 = p2 = None
    for _ in range(n):
        p = list(map(int, input().split(' ')))
        if not p1:
            p1 = p
        elif not p2:
            p2 = p
        else:
            p_max = calc(p1, p2)
            p1_max = calc(p1, p)
            p2_max = calc(p1, p)

            if p1_max >= p_max and p1_max >= p2_max:
                p2 = p
            elif p2_max >= p_max and p2_max >= p1_max:
                p1 = p

    print(calc(p1, p2))
    """
    patterns = {
        'lt': (1, 1),
        'rt': (-1, 1),
        'lb': (-1, -1),
        'rb': (1, -1),
    }

    points: dict = {k: None for k in patterns.keys()}

    for _ in range(n):
        p = list(map(int, input().split(' ')))

        for k, (x, y) in patterns.items():
            max_p = points[k]

            if max_p:
                max_p_pos = (max_p[0] * x) + (max_p[1] * y)
                p_pos = (p[0] * x) + (p[1] * y)
                if max_p_pos < p_pos:
                    points[k] = p
            else:
                points[k] = p

    ans = 0
    for i, p1 in enumerate(points.values()):
        for p2 in list(points.values())[i + 1:]:
            ans = max(ans, calc(p1, p2))

    print(ans)
    """


main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []



def main():
	N = i_input()

	x_y_list = []

	for i in range(0,N):
		tmpx,tmpy = i_map()
		x_y_list.append((tmpx,tmpy))

	z_list = []
	w_list = []
	for i in range(0,N):
		tmpz = x_y_list[i][0] + x_y_list[i][1]
		tmpw = x_y_list[i][0] - x_y_list[i][1]
		z_list.append(tmpz)
		w_list.append(tmpw)

	print(max(max(map(lambda x : abs(x),z_list))-min(map(lambda x: abs(x), z_list)),max(map(lambda x : abs(x),w_list))-min(map(lambda x: abs(x),w_list))))
	
	return


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
"""AtCoder Beginner Contest 178.

E
"""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


def calc(p1: list, p2: list) -> int:
    """Calc Manhattan Distance."""
    return abs(p2[1] - p1[1]) + abs(p2[0] - p1[0])


def main():
    """Run."""
    n = int(input())

    p1 = p2 = None
    for _ in range(n):
        p = list(map(int, input().split(' ')))
        if not p1:
            p1 = p
        elif not p2:
            p2 = p
        else:
            p1_max = calc(p1, p)
            p2_max = calc(p1, p)

            if p1_max >= p2_max:
                p2 = p
            else:
                p1 = p

    print(calc(p1, p2))
    """
    patterns = {
        'lt': (1, 1),
        'rt': (-1, 1),
        'lb': (-1, -1),
        'rb': (1, -1),
    }

    points: dict = {k: None for k in patterns.keys()}

    for _ in range(n):
        p = list(map(int, input().split(' ')))

        for k, (x, y) in patterns.items():
            max_p = points[k]

            if max_p:
                max_p_pos = (max_p[0] * x) + (max_p[1] * y)
                p_pos = (p[0] * x) + (p[1] * y)
                if max_p_pos < p_pos:
                    points[k] = p
            else:
                points[k] = p

    ans = 0
    for i, p1 in enumerate(points.values()):
        for p2 in list(points.values())[i + 1:]:
            ans = max(ans, calc(p1, p2))

    print(ans)
    """


main()

Submission status: Wrong Answer

Solution code:
"""AtCoder Beginner Contest 178.

E
"""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


def calc(p1: list, p2: list) -> int:
    """Calc Manhattan Distance."""
    return abs(p2[1] - p1[1]) + abs(p2[0] - p1[0])


def main():
    """Run."""
    n = int(input())

    patterns = {
        'lt': (1, 1),
        'rt': (1, 1),
        'lb': (-1, -1),
        'rb': (1, -1),
    }

    points: dict = {k: None for k in patterns.keys()}

    for _ in range(n):
        p = list(map(int, input().split(' ')))

        for k, (x, y) in patterns.items():
            max_p = points[k]

            if max_p:
                max_p_pos = (max_p[0] * x) + (max_p[1] * y)
                p_pos = (p[0] * x) + (p[1] * y)
                if max_p_pos < p_pos:
                    points[k] = p
            else:
                points[k] = p

    ans = 0
    for i, p1 in enumerate(points.values()):
        for p2 in list(points.values())[i + 1:]:
            ans = max(ans, calc(p1, p2))

    print(ans)


main()

Submission status: Wrong Answer

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

sum_xy = sorted([x+y for x, y in xy])
print(sum_xy[-1] - sum_xy[0])

Submission status: Wrong Answer

Solution code:
from math import inf
from operator import itemgetter
N=int(input())
points=[]
for _ in range(N):
  a,b=map(int,input().split( ))
  points.append([a,b])
points.sort(key=itemgetter(0))
m1=-inf
m2=inf
m3=-inf
m4=inf
for x,y in points:
  m1=max(m1,x+y)
  m2=min(m2,x+y)
  m3=max(m3,abs(x-y))
  m4=min(m4,abs(x-y))
print(max(m1-m2,m3-m4))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
xys = []
for i in range(N):
    x, y = LI()
    xys.append((x,y))

# 左下，左上，右上，右下

ans = 0
max_point = [0,0]
min_point = [mod, mod]

for i in range(N):
    x, y = xys[i]
    
    if sum(max_point) < (x + y):
        max_point = [x,y]
    if sum(min_point) > x + y:
        min_point = [x, y]

ans = abs(max_point[0] - min_point[0]) + abs(max_point[1] - min_point[1])

# print(ans)

max_point = [0,0]
min_point = [mod, mod]

for i in range(N):
    x, y = xys[i]
    
    if sum(max_point) <= (-x + y):
        max_point = [x,y]
    if sum(min_point) >= -x +y:
        min_point = [x, y]


ans_2 = abs(max_point[0] - min_point[0]) + abs(max_point[1] - min_point[1])
# print(ans, ans_2)
print(max(ans, ans_2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
xys = []
for i in range(N):
    x, y = LI()
    xys.append((x,y))

# 左下，左上，右上，右下

ans = 0
max_point = [0,0]
min_point = [mod, mod]

for i in range(N):
    x, y = xys[i]
    
    if sum(max_point) < (x + y):
        max_point = [x,y]
    if sum(min_point) > x + y:
        min_point = [x, y]

ans = abs(max_point[0] - min_point[0]) + abs(max_point[1] - min_point[1])

print(ans)

# ans = 0
# max_point = [0,0]
# min_point = [mod, mod]

# for i in range(N):
#     x, y = xys[i]
    
#     if sum(max_point) < (-x + y):
#         max_point = [-x,y]
#     if sum(min_point) > x - y:
#         min_point = [x, -y]

# ans_2 = abs(max_point[0] - min_point[0]) + abs(max_point[1] - min_point[1])

# print(max(ans, ans_2))

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()	
	pp_min=mod*mod
	pp_max=0
	pm_max=0
	mp_max=0
	for _ in range(n):
		a, b = tin()
		pp_min = min(pp_min, a+b)
		pp_max = max(pp_max, a+b)
		pm_max = max(pm_max, a-b)
		mp_max = max(mp_max, -a + b)
	return max((pp_max- pp_min), (mp_max+pm_max))
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a = []
for i in range(n):
    x,y = rl()
    a.append((x,y, x+y))
a = sorted(a, key=lambda x: x[2])
print(abs(a[-1][0]- a[0][0]) + abs(a[-1][1]-a[0][1]))

Submission status: Wrong Answer

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

za,wa=0,0
zi,wi=10**10,10**10
for i in range(N):
    z=arr[i][0]+arr[i][1]
    w=arr[i][0]-arr[i][1]
    
    za=max(z,za)
    zi=min(z,zi)
    
    wa=max(w,wa)
    wi=min(w,wi)

print(max(za-zi,wa-wi))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> int:
    """
    標準入力を取得する.

    Returns:\n
        int: 標準入力
    """
    S = int(input())

    return S


def combinations_count(n: int, r: int) -> int:
    """
    組み合わせの総数を取得する.

    Args:\n
        n (int): 整数
        r (int): 整数(r <= n)

    Returns:\n
        int: 組み合わせの総数
    """
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main(S: int) -> None:
    """
    メイン処理.

    Args:\n
        S (int): 整数(1 <= S <= 2000)
    """
    # 求解処理
    a = S // 3
    b = S % 3
    ans = 0
    while a > 0:
        ans += combinations_count(b + a - 1, b)
        a -= 1
        b += 3
    ans %= 10**9 + 7

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    S = get_input()

    # メイン処理
    main(S)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
max_z = 0
min_z = np.inf
max_w = 0
min_w = np.inf
for _ in range(N):
    x, y = map(int, input().split())
    z = x + y
    w = x - y
    max_z = max(max_z, z)
    min_z = min(min_z, z)
    max_w = max(max_w, w)
    min_w = min(min_w, w)
print(max(max_z-min_z, max_w-min_w))

Submission status: Wrong Answer

Solution code:
#E_Manhattan
n = int(input())
g = []
for i in range(n):
    x_, y_ = map(int, input().split())
    g.append([x_- y_, x_+y_])
min_x=-1; max_x=-1
min_y=-1; max_y=-1
mi_x = 10**9+7; ma_x = -1
mi_y = 10**9+7; ma_y = -1
for i in range(n):
    if g[i][0]<mi_x:
        mi_x = g[i][0]
        min_x = i
    if g[i][0]>ma_x:
        ma_x = g[i][0]
        max_x = i
    if g[i][1]<mi_y:
        mi_y = g[i][1]
        min_y = i
    if g[i][1]>ma_y:
        ma_y = g[i][1]
        max_y = i
if (ma_x - mi_x) < (ma_y-mi_y):
    x_ = abs((g[max_y][0]+g[max_y][1])/2 - (g[min_y][0]+g[min_y][1])/2)
    y_ = abs((g[max_y][1]-g[max_y][0])/2 - (g[min_y][1]-g[min_y][0])/2)
    print(int(x_+y_))
else:
    x_ = abs((g[max_x][0]+g[max_x][1])/2 - (g[min_x][0]+g[min_x][1])/2)
    y_ = abs((g[max_x][1]-g[max_y][0])/2 - (g[min_x][1]-g[min_x][0])/2)
    print(int(x_+y_))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
max_z = 0
min_z = np.inf
max_w = 0
min_w = np.inf
for _ in range(N):
    x, y = map(int, input().split())
    z = x + y
    w = abs(x - y)
    max_z = max(max_z, z)
    min_z = min(min_z, z)
    max_w = max(max_w, w)
    min_w = min(min_w, w)
print(max(max_z-min_z, max_w-min_w))