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:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
xy = [readInts() for _ in range(n)]
max_xplusy = -1
min_xplusy = INF
for i in range(n):
    x,y = xy[i]
    max_xplusy = max(max_xplusy, x+y)
    min_xplusy = min(min_xplusy, x+y)
a = abs(max_xplusy - min_xplusy)
max_xminusy = -1
min_xminusy = INF
for i in range(n):
    x,y = xy[i]
    max_xminusy = max(max_xminusy, x-y)
    min_xminusy = min(min_xminusy, x-y)
b = abs(max_xminusy - min_xminusy)
print(max(a,b))

Submission status: Wrong Answer

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def in2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    x, y = in2(N)
    mx = max(x)
    my = max(y)
    c = [(x[i]+y[i], i) for i in range(N)]
    d = [(mx-x[i]+my-y[i], i) for i in range(N)]
    c.sort()
    d.sort()
    i1 = c[0][1]
    j1 = c[-1][1]
    i2 = d[0][1]
    j2 = d[-1][1]

    ans = max(
        abs(x[i1]-x[j1])+abs(y[i1]-y[j1]),
        abs(x[i2]-x[j2])+abs(y[i2]-y[j2])
    )
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=set(tuple([lnii() for i in range(n)]))

if len(l)==1:
  print(0)
  exit()

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

ans=0
for x,y in l:
#  s=abs(x-y)
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

#  t=abs(x+y)
  t=x+y
  y_max=max(y_max,t)
  y_mim=min(y_min,t)


  ans=max(s,y)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ru = [0, 0]
rb = [0, 10 ** 9 + 1]
lu = [10 ** 9 + 1, 0]
lb = [10 ** 9 + 1, 10 ** 9 + 1]
for i in range(n):
  x, y  = [int(x) for x in input().split()]
  if x >= ru[0] and y >= ru[1]:
    ru[0] = x
    ru[1] = y
  if x >= rb[0] and y <= rb[1]:
    rb[0] = x
    rb[1] = y
  if x <= lu[0] and y >= lu[1]:
    lu[0] = x
    lu[1] = y
  if x <= lb[0] and y <= lb[1]:
    lb[0] = x
    lb[1] = y
print(max(ru[0] - lb[0] + ru[1] - lb[1], rb[0] - lu[0] + lu[1] - rb[1], ))

Submission status: Wrong Answer

Solution code:
n = int(input())
n_list = []
# dist_max = 0

for i in range(n):
    x, y = map(int, input().split())
    n_list.append(x+y)

print(max(n_list) - min(n_list))

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
a,c,b,d=0,10**10,0,10**10
for i in range(n):
    x,y=r[i]
    a=max(a,abs(x+y))
    c=min(c,abs(x+y))
    b=max(b,abs(x-y))
    d=min(d,abs(x-y))
print(max(a-c,b-d))

Submission status: Wrong Answer

Solution code:
import math
#N = map(int,input().split())
#AB=[]
N = int(input())
#C = input()
#D, T, S=map(int,input().split())
C = []
D = []
for i in range(N):
    al = list(map(int,input().split()))
    if al not in C:
        C.append(al)
        D.append([al[0]-al[1],al[0]+al[1]])
min0 = 1000000000
max0 = 0
min1 = 1000000000
max1 = 0
for i in D:
    if max0 <= i[0]:
        max0 = i[0]
    if min0 >= i[0]:
        min0 = i[0]
    if max1 <= i[1]:
        max1 = i[1]
    if min1 >= i[1]:
        min1 = i[1]

print(max(max0-min0, max1-min1))

Submission status: Wrong Answer

Solution code:
from sys import *
N = int(stdin.readline())
a = []

sumBig = [0,0]
sumSmall = [10**10, 10**10]
difBig = [0,0]
difSmall = [10**10, 10**10]

for i in range(N):
    tmp = list(map(int, stdin.readline().split()))
    if tmp[0] + tmp[1] > sumBig[0] + sumBig[1]:
        sumBig = tmp
    if tmp[0] + tmp[1] < sumSmall[0] + sumSmall[1]:
        sumSmall = tmp
    if abs(tmp[0] + tmp[1]) > abs(difBig[0] + difBig[1]):
        difBig = tmp
    if abs(tmp[0] + tmp[1]) < abs(difSmall[0] + difSmall[1]):
        difSmall = tmp


    a.append(tmp)
things = [sumBig, sumSmall, difBig, difSmall]
best = 0
for i in range(N):
    for j in range(4):
        best = max(best, abs(a[i][0] - things[j][0]) + abs(a[i][1] - things[j][1]))

print(best)

Submission status: Wrong Answer

Solution code:

def mh(p1, p2):
  return abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])

N = int(input())
points = set()
for i in range(N):
  x, y = [int(i) for i in input().split()]
  points.add(tuple([x, y]))

points_x = sorted(points, key=lambda x: x[0])
points_y = sorted(points_x, key=lambda x: x[1])


max_x = points_x[-1]
max_y = points_y[-1]
min_x = points_x[0]
min_y = points_y[0]

l = []
l.append(mh(max_x, min_x))
l.append(mh(max_y, min_y))
print(max(l))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
for i in range(n):
  x, y = map(int, input().split())
  p.append([x, y])
  
p.sort(key=lambda x: (x[0]**2 + x[1]**2))

print(p[n-1][0] - p[0][0] + p[n-1][1] - p[0][1])

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

Solution code:

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

cand = []

X.sort(key=lambda x: x[0])
cand.append(abs(X[0][0] - X[-1][0]) + abs(X[0][1] - X[-1][1]))

X.sort(key=lambda x: x[1])
cand.append(abs(X[0][0] - X[-1][0]) + abs(X[0][1] - X[-1][1]))

print(max(cand))

Submission status: Wrong Answer

Solution code:

def mh(p1, p2):
  return abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])

N = int(input())
points = set()
for i in range(N):
  x, y = [int(i) for i in input().split()]
  points.add(tuple([x, y]))
print(points)

points_x = sorted(points, key=lambda x: x[0])
points_y = sorted(points_x, key=lambda x: x[1])

print(points_x)
print(points_y)

max_x = points_x[-1]
max_y = points_y[-1]
min_x = points_x[0]
min_y = points_y[0]

l = []
l.append(mh(max_x, min_x))
l.append(mh(max_y, min_y))
print(max(l))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
ar=[]
for i in range(n):
  l.append(list(map(int,input().split())))
  ar.append(l[-1][0]+l[-1][1])
ar.sort()
an=abs(ar[-1]-ar[0])
print(an)

Submission status: Wrong Answer

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

num=[i[0]+i[1] for i in l]

mi=num.index(min(num))
ma=num.index(max(num))
a=abs(l[ma][0]-l[mi][0])
b=abs(l[ma][1]-l[mi][1])

print(a+b)

Submission status: Wrong Answer

Solution code:
n=int(input())
minman=(10**9)*2
maxman=0
for i in range(n):
  x,y=map(int, input().split())
  ab=x+y
  if ab< minman:
    minman=ab
  if maxman<ab:
    maxman=ab
print(maxman-minman)

Submission status: Wrong Answer

Solution code:
def chebyshev_0(a, b):
    return a - b
def chebyshev_1(a, b):
    return a + b
 
N = int(input())
X = [0] * N
Y = [0] * N
 
for i in range(N):
    X[i], Y[i] = map(int, input().split())
 
max_0 = 0
min_0 = 2 * (10 ** 9 - 1)
for x, y in zip(X, Y):
    if chebyshev_0(x, y) > max_0:
        max_0 = chebyshev_0(x, y) 
    if chebyshev_0(x, y) < min_0:
        min_0 = chebyshev_0(x, y) 
l0 = abs(max_0 - min_0)
 
max_1 = 0
min_1 = 2 * (10 ** 9 - 1)
for x, y in zip(X, Y):
    if chebyshev_1(x, y) > max_1:
        max_1 = chebyshev_1(x, y) 
    if chebyshev_1(x, y) < min_1:
        min_1 = chebyshev_1(x, y) 
l1 = abs(max_1 - min_1)
 
print(max([l0, l1]))

Submission status: Wrong Answer

Solution code:
p=[]
for i in range(int(input())):
    m,n=map(int,input().split())
    p.append([m,n])
g=p
p.sort(key=lambda x:x[0])
d=-99999999
for i in range(1,len(p)):
    d=max(d,abs(p[i][1]-p[i-1][1])+abs(p[i][0]-p[i-1][0]))
p=g
p.sort(key=lambda x:x[1])
d1=-99999999
for i in range(1,len(p)):
    d1=max(d1,abs(p[i][1]-p[i-1][1])+abs(p[i][0]-p[i-1][0]))
print(max(d,d1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def li():  return list(mi())

def main():
    n = ii()
    d = dict()
    
    for i in range(n):
        d[i] = li()
    # print(d)

    for i in range(n):
        temp = d[i]
        var = abs(temp[0]*temp[1])
        d[i] = (var,temp)


    # d = {k: v for k, v in sorted(d.items(), key=lambda item: item[1], reverse=True)}
    # print(d)
    # res = abs(d[0][1][0] - d[-1][1][0]) - abs(d[0][1][1] - d[-1][1][1])
    mk = max(d, key=d.get)
    my = min(d, key=d.get)
    # print(mk,my)
    x = d[mk][1]
    y = d[my][1]
    res = abs(x[0]-y[0]) + abs(x[1]-y[1])

    print(res)
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = []
x1 = [0,0,0,0]
y1 = [0,0,0,0]
for _ in range(N):
    x, y = map(int, input().split())
    xy.append([x, y])
    if x > 0 and y > 0:
        if abs(x) + abs(y) > abs(x1[0]) + abs(y1[0]):
            x1[0] = x
            y1[0] = y
    elif x <= 0 and y > 0:
        if abs(x) + abs(y) > abs(x1[1]) + abs(y1[1]):
            x1[1] = x
            y1[1] = y
    elif x <= 0 and y <= 0:
        if abs(x) + abs(y) > abs(x1[2]) + abs(y1[2]):
            x1[2] = x
            y1[2] = y
    else:
        if abs(x) + abs(y) > abs(x1[3]) + abs(y1[3]):
            x1[3] = x
            y1[3] = y

ans = 0
for x, y in xy:
    for i in range(4):
        if x1[i] and y1[i]:
            ans = max(ans, abs(x1[i] - x) + abs(y1[i] - y))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

max1 = -100
min1 = 10 ** 10
max0 = -100
min0 = 10 ** 10

for i in range(n):
    x,y = list(map(int,input().split()))
    k0 = x - y
    k1 = x + y
    if k0 > max0:
        max0 = k0
    if k0 < min0:
        min0 = k0
    if k1 > max1:
        max1 = k1
    if k1 < min1:
        min1 = k1


ans = int(max(max1-min1,max0-min0))

print(ans)

Submission status: Wrong Answer

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

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

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

MAX = 0
MIN = 10 ** 10
x_min = MIN
y_min = MIN
x_max = MAX
y_max = MAX

x_min_p = None
y_min_p = None
x_max_p = None
y_max_p = None

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

    if tmp_x <= x_min:
        x_min_p = (tmp_x, tmp_y)
        x_min = tmp_x

    if x_max <= tmp_x:
        x_max_p = (tmp_x, tmp_y)
        x_max = tmp_x

    if tmp_y <= y_min:
        y_min_p = (tmp_x, tmp_y)
        y_min = tmp_y

    if y_max <= tmp_y:
        y_max_p = (tmp_x, tmp_y)
        y_max = tmp_y

result = max(manha(x_min_p, y_min_p), manha(x_min_p, x_max_p), manha(x_min_p, y_max_p), manha(y_min_p, y_max_p), manha(y_min_p, x_max_p), manha(y_max_p, x_max_p))
print(result)

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

Solution code:
def dist(a,b):
  d = a - b
  if d < 0:
    return -(d)
  else:
    return d
def max_dist_set(a_set,b_set):
  max_d = 0
  for a in a_set:
    for b in b_set:
      d = dist(a,b)
      if d > max_d:
        max_d = d
  return max_d
N = int(input())
dict = {}
x_list = [0 for i in range(N)]
y_list = [0 for i in range(N)]
for i in range(N):
  x,y = map(int,input().split())
  x_list[i] = x
  y_list[i] = y
  if x not in dict:
    dict[x] = [y]
  else:
    dict[x].append(y)
if len(dict) == 1:
  y = dict[x]
  y = set(y)
  if len(y) == 1:
    print(0)
  else:
    y = dict[x]
    y.sort()
    result = dist(y[0], y[-1])
    print(result)
else:
  result = dist(x_list[0],dict[x][0])
  for i in range(N):
    xi = x_list[i]
    yi_list = dict[xi]
    yi_list.sort()
    for j in range(N-i):
      xj = x_list[i+j]
      yj_list = dict[xj]
      yj_list.sort()
      max_i = dist(yi_list[0], yi_list[-1])
      max_j = dist(yj_list[0], yj_list[-1])
      if max_i > result:
        result = max_i
      if max_j > result:
        result = max_j
      yi_set = set(yi_list)
      yj_set = set(yj_list)
      max_ij = dist(xi,xj) + max_dist_set(yi_set, yj_set)
      if max_ij > result:
         result = max_ij
  print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
x_1 = [0,0]
x_2 = [0,0]
x_3 = [0,0]
x_4 = [0,0]

for i in range(n):
    c,d = (map(int,input().split()))
    a = abs(c)
    b = abs(d)
    if c >= 0 and d >= 0:
        if x_1[0] + x_1[1] < a+b:
            x_1[0] = c
            x_1[1] = d
    elif c >= 0 and d < 0:
        if x_3[0] + abs(x_3[1]) < a+b:
            x_3[0] = c
            x_3[1] = d
    elif c < 0 and d >= 0:
        if abs(x_2[0]) + x_2[1] < a+b:
            x_2[0] = c
            x_2[1] = d
    elif c < 0 and d < 0:
        if abs(x_4[0]) + abs(x_4[1]) < a+b:
            x_4[0] = c
            x_4[1] = d

e_1 = abs(x_1[0] - x_2[0]) + abs(x_1[1] - x_2[1])
e_2 = abs(x_1[0] - x_3[0]) + abs(x_1[1] - x_3[1])
e_3 = abs(x_1[0] - x_4[0]) + abs(x_1[1] - x_4[1])
e_4 = abs(x_2[0] - x_3[0]) + abs(x_2[1] - x_3[1])
e_5 = abs(x_2[0] - x_4[0]) + abs(x_2[1] - x_4[1])
e_6 = abs(x_3[0] - x_4[0]) + abs(x_3[1] - x_4[1])

print(max(e_1,e_2,e_3,e_4,e_5,e_6))

Submission status: Wrong Answer

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

mi = 10**9
ma = 0

for i in range(n):
    tmp = xy[i][0] + xy[i][1]
    if tmp > ma:
        ma = tmp
    #print(tmp,mi)
    if tmp < mi:
        mi = tmp
        
print(ma-mi)
#print(ma,mi)

Submission status: Wrong Answer

Solution code:
def main():
    point_count = int(input())
    inf = 10 ** 9 * 2 + 1
    max_sum, min_sum, max_diff, min_diff = 0, inf, 0, inf
    for _ in range(point_count):
        x, y = [int(x) for x in input().split()]
        max_sum = max(x + y, max_sum)
        min_sum = min(x + y, min_sum)
        max_diff = max(x - y, max_diff)
        min_diff = min(x - y, min_diff)
    return max(max_sum - min_sum, max_diff - min_diff)


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
for _ in range(N):
    x, y = map(int, input().split())
    L.append([x, y])

# print(L)
L.sort()
min_x_L = L[:]
L.sort(key=lambda x: x[1])
min_y_L = L[:]
L.sort(key=lambda x: x[0], reverse=True)
max_x_L = L[:]
L.sort(key=lambda x: x[1], reverse=True)
max_y_L = L[:]

# print(min_x_L, max_x_L, min_y_L, max_y_L)

ans = []
ans.append(abs(min_x_L[0][0] - max_x_L[0][0]) +
           abs(min_x_L[0][1] - max_x_L[0][1]))
ans.append(abs(min_x_L[0][0] - max_y_L[0][0]) +
           abs(min_x_L[0][1] - max_y_L[0][1]))
ans.append(abs(min_y_L[0][0] - max_x_L[0][0]) +
           abs(min_y_L[0][1] - max_x_L[0][1]))
ans.append(abs(min_y_L[0][0] - max_y_L[0][0]) +
           abs(min_y_L[0][1] - max_y_L[0][1]))

print(max(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
Y_MAX = 0
X_MAX = 0
Y_MIN = 10000000
X_MIN = 10000000

for i in range(N):
    x, y = map(int, input().split())
    if abs(0 - x) + abs(y - 100000) > Y_MAX:
        Y_MAX = abs(0 - x) + abs(y - 100000)
    if abs(0 - x) + abs(y - 100000) < Y_MIN:
        Y_MIN = abs(0 - x) + abs(y - 100000)
    if abs(0 - x) + abs(0 - y) > X_MAX:
        X_MAX = abs(0 - x) + abs(0 - y)
    if abs(0 - x) + abs(0 - y) < X_MIN:
        X_MIN = abs(0 - x) + abs(0 - y)

print(max(Y_MAX - Y_MIN, X_MAX - X_MIN))

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

minD = 10**9
min = 0
maxD = 0
max = 0

for i in range(N):
    if (minD > (hw[i][0] + hw[i][1])):
        minD = hw[i][0] + hw[i][1]
        min = i
    if (maxD < hw[i][0] + hw[i][1]):
        maxD = hw[i][0] + hw[i][1]
        max = i

print(abs(hw[max][0] - hw[min][0]) + abs(hw[max][1] - hw[min][1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.spatial import distance
def main():
    n = int(input())
    try:
        lis = []
        for i in range(n):
            x,y = map(int, input().split())
            lis.append([x,y])
        M = np.array(lis)
        dist_M = distance.cdist(M, M, metric='cityblock')
        print(int(np.max(dist_M)))
    except:
        print(0)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
xl, yl = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xl.append(x)
    yl.append(y)
xl_ = xl.copy()
yl_ = yl.copy()
xl_.sort()
yl_.sort()

xm, ym = xl_[n//2-1], yl_[n//2-1]
ans1, ans2, ans3, ans4 = 0, 0, 0, 0
for i in range(n):
    if xl[i] > xm:
        if yl[i] > ym:
            ans1 = max(ans1, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            ans4 = max(ans4, abs(xl[i]-xm)+abs(yl[i]-ym))
    else:
        if yl[i] > ym:
            ans2 = max(ans2, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            ans3 = max(ans3, abs(xl[i]-xm)+abs(yl[i]-ym))
ans = int(max(abs(ans1+ans3), abs(ans2+ans4)))

xm, ym = xl_[n//2], yl_[n//2]
ans1, ans2, ans3, ans4 = 0, 0, 0, 0
for i in range(n):
    if xl[i] > xm:
        if yl[i] > ym:
            ans1 = max(ans1, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            ans4 = max(ans4, abs(xl[i]-xm)+abs(yl[i]-ym))
    else:
        if yl[i] > ym:
            ans2 = max(ans2, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            ans3 = max(ans3, abs(xl[i]-xm)+abs(yl[i]-ym)) 
ans_ = int(max(abs(ans1+ans3), abs(ans2+ans4)))

print(max(ans, ans_))

Submission status: Wrong Answer

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    x, y = MI()
    x1 = x
    x2 = x
    x3 = x
    x4 = x
    y1 = y
    y2 = y
    y3 = y
    y4 = y
    for _ in range(n-1):
        x, y = MI()
        if x+y > x1+y1:
            x1 = x
            y1 = y
        if -x+y > -x2+y2:
            x2 = x
            y2 = y
        if -x-y > -x3-y3:
            x3 = x
            y3 = y
        if x-y > x4-y4:
            x4 = x
            y4 = y
        temp = [abs(x1-x2)+abs(y1-y2), abs(x1-x3)+abs(y1-y3), abs(x1-x4)+abs(y1-y4), abs(x2-x3)+abs(y2-y3), abs(x2-x4)+abs(y2-y4), abs(x3-x4)+abs(y3-y4)]
        ans = max(temp)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

s_max,s_min=0,10**10
t_max,t_min=0,10**10

for i in range(N):
    a,b=map(int,input().split())
    
    s,t=a+b,a-b
    if s>=s_max and s-s_min>=s_max-s_min:
        s_max=s
    if s<=s_min and s_max-s>=s_max-s_min:
        s_min=s
    if t>=t_max and t-t_min>=t_max-t_min:
        t_max=t
    if t<=t_min and t_max-t>=t_max-t_min:
        t_min=t
    
    #s_max,s_min=max(s_max,s),min(s_min,s)
    #t_max,t_min=max(t_max,t),min(t_min,t)
    
print(max(s_max-s_min,t_max-t_min,s_max-t_min,t_max-s_min))

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = map(int, input().split())
data = [[a,b]]

xmin = [[a,b]]
xmax = [[a,b]]
ymin = [[a,b]]
ymax = [[a,b]]

for i in range(n-1):
    a,b=map(int, input().split())

    data.append([a, b])
    if (xmin[0][0] == a):
        xmin.append([a,b])
    if (xmin[0][0] >  a):
        xmin = []
        xmin.append([a,b])


    if (xmax[0][0] == a):
        xmax.append([a,b])
    if (xmax[0][0] <  a):
        xmax = []
        xmax.append([a,b])


    if (ymin[0][1] == b):
        ymin.append([a,b])
    if (ymin[0][1] >  b):
        ymin = []
        ymin.append([a,b])


    if (ymax[0][1] == b):
        ymax.append([a,b])
    if (ymax[0][1] <  b):
        ymax = []
        ymax.append([a,b])

ans = -1
#print(xmin, xmax, ymin, ymax)
for i in data:
    x1 = i[0]
    y1 = i[1]


    for j in xmin:
        x2 = j[0]
        y2 = j[1]
        ans = max(ans, abs(x1-x2) + abs(y1-y2))

    for j in xmax:
        x2 = j[0]
        y2 = j[1]
        ans = max(ans, abs(x1 - x2) + abs(y1 - y2))

    for j in ymin:
        x2 = j[0]
        y2 = j[1]
        ans = max(ans, abs(x1 - x2) + abs(y1 - y2))

    for j in ymax:
        x2 = j[0]
        y2 = j[1]
        ans = max(ans, abs(x1 - x2) + abs(y1 - y2))

print(ans)

Submission status: Wrong Answer

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

max_xy_0=0
min_xy_0=10**9
max_xy_1=0
min_xy_1=10**9

for i in range(N):
  x[i], y[i] = list(map(int, input().split()))
  if x[i]+y[i]>max_xy_0:
    max_xy_0=x[i]+y[i]
  if x[i]+y[i]<min_xy_0:
    min_xy_0=x[i]+y[i]
  if x[i]-y[i]>max_xy_1:
    max_xy_1=x[i]-y[i]
  if x[i]-y[i]>max_xy_1:
    min_xy_1=x[i]-y[i]  
print(max([max_xy_0-min_xy_0,max_xy_1-min_xy_1]))

Submission status: Wrong Answer

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

ans = 0
tmp = [xy[0], xy[-1], yx[0], yx[-1]]
for x, y in tmp:
    for x1, y1 in tmp:
        ans = max(ans, abs(x - x1) + abs(y - y1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xys = set([tuple(map(int, input().split())) for _ in range(N)])

#print(xys)

xys = list(xys)
#print(xys)

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

max_list = []
max_dis = 0
for xy in xys:
    dist = abs(xy[0]) + abs(xy[1])

    if(dist > max_dis):
        max_list = []
        max_list.append(xy)
        max_dis = dist

    elif(dist == max_dis):
        max_list.append(xy)

#print(max_list)

ans = 0

for siten in max_list:
    for syuten in xys:
        dist = abs(siten[0] - syuten[0]) + abs(siten[1] - syuten[1])
        ans = max(ans, dist)

print(ans)

Submission status: Wrong Answer

Solution code:
p=[]
for i in range(int(input())):
    m,n=map(int,input().split())
    p.append([m,n])
p.sort(key=lambda x:x[0])
d=-99999999
for i in range(1,len(p)):
    d=max(d,abs(p[i][1]-p[i-1][1])+abs(p[i][0]-p[i-1][0]))
print(d)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
Y = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)

    
sumxy = [x+y for x,y in zip(X,Y)]
sumxy = sorted(sumxy,reverse = False)

ans = sumxy[-1] - sumxy[0]
print(ans)

Submission status: Wrong Answer

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

main()

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())
    
def manhattan(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

x1 = x[0]
y1 = y[0]
x2 = x[1]
y2 = y[1]
ans = manhattan(x1, y1, x2, y2)

for i in range(2, N):
    x3 = x[i]
    y3 = y[i]
    if manhattan(x1, y1, x3, y3) >= ans or manhattan(x2, y2, x3, y3) >= ans:
        if manhattan(x1, y1, x3, y3) >= manhattan(x2, y2, x3, y3):
            ans = manhattan(x1, y1, x3, y3)
            x2, y2 = x3, y3
        else:
            ans = manhattan(x2, y2, x3, y3)
            x1, y1 = x3, y3
    else:
        continue

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
min_dis = 10 ** 10
max_dis = 0
for i in range(n):
    x, y = map(int, input().split())
    tmp = x + y
    min_dis = min(tmp, min_dis)
    max_dis = max(tmp, max_dis)

print(max_dis - min_dis)

Submission status: Wrong Answer

Solution code:
N = int(input())
i, j, k = 0, 0, 0
x = [0]
y = [0]
while i < N:
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)
    ma = max(x[i+1]*y[i+1], x[i]*y[i])
    mi = min(x[i+1]*y[i+1], x[i]*y[i])
    if ma == x[i+1]*y[i+1]:
        cma = i
    if mi == x[i+1]*y[i+1]:
        cmi = i
    i += 1
print(abs(x[cma] - x[cmi]) + abs(y[cma] - y[cmi]))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    Max = 0
    for i in range(N):
        x, y = map(int, input().split())
        if i == 0:
            x0, y0 = x, y
        elif i == 1:
            x1, y1 = x, y
            Max = abs(x1-x0) + abs(y1-y0)
        else:
            d0 = abs(x-x0) + abs(y-y0)
            d1 = abs(x-x1) + abs(y-y1)
            if d0 > d1:
                if d0 > Max:
                    x1, y1 = x, y
                    Max = d0
            else:
                if d1 > Max:
                    x0, y0 = x, y
                    Max = d1
    print(Max)
    
resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
tmp_M0 = 0
tmp_m0 = 3000000000
tmp_M1 = 0
tmp_m1 = 3000000000
for i in range(N):
    x,y =map(int, input().split())
    if x-y > tmp_M0:
        tmp_M0 = x-y
    if x-y < tmp_m0:
        tmp_m0 = x-y
    if x+y > tmp_M1:
        tmp_M1 = x+y
    if x+y < tmp_m1:
        tmp_m1 = x+y
    
    if max(tmp_M0-tmp_m0, tmp_M1-tmp_m1) > ans:
        ans = max(tmp_M0-tmp_m0, tmp_M1-tmp_m1)
        
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=0
t1,t2=map(int,input().split())
for i in range(n-1):
    x,y=map(int,input().split())
    xn=(x-t1)
    yn=(y-t2)
    
    if xn<0:
        xn=-xn
    
    if yn<0:
        yn=-yn
    
    l=xn+yn
    if l>=m:
        m=l
    t1=x
    t2=y
print(m)

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
a,c,b,d=0,10**10,0,10**10
for i in range(n):
    x,y=r[i]
    a=max(a,x+y)
    c=min(c,x+y)
    b=max(b,x-y)
    d=min(d,x-y)
print(max(a-c,b-d))

Submission status: Wrong Answer

Solution code:
N=int(input())

listA=[]

while True:
    try:
      a,b=map(int, input().split())
      listA.append(a+b)

    except:
        break;
listB=set(listA)
print(max(listB)-min(listB))