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:
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), 7]) 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())
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]]
print(yx)
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())
coordinates = []
for i in range(N):
    coordinate = list(map(int, input().split()))
    coordinates.append(coordinate)
max_dist = 0
coordinates = sorted(coordinates)
for i in range(1, N):
    dist = abs(coordinates[0][0] - coordinates[i][0]) + abs(coordinates[0][1] - coordinates[i][1])
    if max_dist < dist:
        max_dist = dist
print(max_dist)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p = sorted(p, key=lambda i: i[0] + i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
if (x1 <= x2 and y1 <= y2) or (x1 >= x2 and y1 >= y2):
    print(abs((x1 + y1) - (x2 + y2)))
else:
    print(max(abs((x1 - y1) - (x2 + y2)), abs((x1 + y1) - (x2 - y2))))

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 i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    x, y = i2(N)
    c = [(x[i]+y[i], i) for i in range(N)]
    c.sort()
    i = c[0][1]
    j = c[-1][1]
    print(abs(x[i]-x[j])+abs(y[i]-y[j]))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

l = [None] * N

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

minX = min([e[0] for e in l])
maxX = max([e[0] for e in l])
minY = min([e[1] for e in l])
maxY = max([e[1] for e in l])

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

s0 = min([d([minX,minY], e) for e in l])
s1 = min([d([maxX,maxY], e) for e in l])

t0 = min([d([maxX,minY], e) for e in l])
t1 = min([d([maxX,minY], e) for e in l])

print(d([minX,minY], [maxX,maxY]) - min(s0+s1, t0+t1))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
XY = []
xAve = 0
yAve = 0
for _ in range(N):
    x,y=map(int,input().split())
    XY.append([x,y])
    xAve += x
    yAve += y
xAve = xAve/N
yAve = yAve/N
XYnorm = [0]*4

for x,y in XY:
    nX = x-xAve
    nY = y-yAve
    if nX>=0 and nY>=0:#第1象限
        if XYnorm[0]<= nX+nY:
            XYnorm[0] = nX+nY
            XY0 =[x,y]

    if nX <=0 and nY >=0:#第2象限
        if XYnorm[1]<= -nX+nY:
            XYnorm[1] = -nX+nY
            XY1 =[x,y]
            
    if nX <=0 and nY <=0:#第3象限
        if XYnorm[2]<= -nX-nY:
            XYnorm[2] = -nX-nY
            XY2 =[x,y]
            
    if nX >=0 and nY <=0:#第4象限
        if XYnorm[3]<= nX-nY:
            XYnorm[3] = nX-nY
            XY3 =[x,y]
try:
    XY02 = abs(XY0[0]-XY2[0])+abs(XY0[1]-XY2[1])
except:
    XY02=0
try:
    XY13 = abs(XY1[0]-XY3[0])+abs(XY1[1]-XY3[1])
except:
    XY13 = 0
print(max(XY02,XY13))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for i in range(n):
    xy.append(tuple(map(int,input().split())))
ans = -1

x,y = float("INF"),float("INF")
mxy = min(xy)
for xi,yi in xy:
    ans = max(ans,abs(xi-mxy[0])+abs(yi-mxy[1]))

print(ans)

Submission status: Wrong Answer

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

for i, pos in enumerate(p):
    a.append((sum(pos), i))

a.sort(key=lambda x:x[0])

xi, yi = p[a[0][1]]
xj, yj = p[a[-1][1]]

print(abs(xi - xj) + abs(yi - yj))

Submission status: Wrong Answer

Solution code:
n = int(input())

max1 = 0
min1 = 10 ** 10
max0 = 0
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:
N = int(input())
A = 0
Xmin = Ymin = 1e9 + 5
Xmax = Ymax = 0
for _ in range(N):
    x, y = map(int, input().split())
    X = x + y
    Y = x - y
    Xmin = min(Xmin, X)
    Xmax = max(Xmax, X)
    Ymin = min(Ymin, Y)
    Ymax = max(Ymax, Y)
if Xmin == 1e9 + 5:
    Xmin = Xmax
if Ymin == 1e9 + 5:
    Ymin = Ymax
Z = max(Xmax - Xmin, Ymax - Ymin)
print(Z)

Submission status: Wrong Answer

Solution code:
from collections import deque
def dist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

N=int(input())
P=[0]*N

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

Old_Old_=0
Old_I=-1
I=0
Flag=False
while True:
    M=-1
    Old_Old_I=Old_I
    Old_I=I
    for i in range(N):
        if M<dist(P[I],P[i]):
            J=i
            M=dist(P[I],P[i])

    if J==Old_Old_I and Flag:
        break
    I=J
    Flag=True

print(dist(P[Old_I],P[J]))

Submission status: Wrong Answer

Solution code:
N = int(input())
Array1 = []
Array2 = []

for i in range(N):
    next_x, next_y = map(int, input().split())
    s = next_x + next_y
    t = next_x - next_y
    Array1.append(s)
    Array2.append(t)

print(max(max(Array1)-min(Array2),max(Array2)-min(Array1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
v = [list(map(int, input().split())) for i in range(N)]
minx = min([v[i][0] for i in range(N)])
miny = min([v[i][1] for i in range(N)])
v.sort(key = lambda x:x[0] - minx + x[1] - miny)
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(d)

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), 4]) 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())
xy = list(list(map(int,input().split())) for _ in range(n))
l = []
for i in range(n):
    l.append(xy[i][0]+xy[i][1])
d = abs(abs(xy[l.index(max(l))][0])-abs(xy[l.index(min(l))][0]))+abs(abs(xy[l.index(max(l))][1])-abs(xy[l.index(min(l))][1]))
print(d)

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

if n%2:
    xm, ym = xl_[n//2], yl_[n//2]
else:
    xm, ym = (xl_[n//2-1]+xl_[n//2])/2, (yl_[n//2-1]+yl_[n//2])/2

xm, ym = xm-1e-6, ym-1e-6
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 = xm+1e-6+1e-6, ym+1e-6+1e-6
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:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

# main

N = int(input())
xy = int_mtx(N)

x = xy[:,0]
y = xy[:,1]

xmin_p = list(*np.where(x == np.min(x)))
xmax_p = list(*np.where(x == np.max(x)))
ymin_p = list(*np.where(y == np.min(y)))
ymax_p = list(*np.where(y == np.max(y)))

ans = 0

for xmin in xmin_p:
    for xmax in xmax_p:
        ans = max(ans,abs(xy[xmin,0]-xy[xmax,0])+abs(xy[xmin,1]-xy[xmax,1]))

for ymin in ymin_p:
    for ymax in ymax_p:
        ans = max(ans,abs(xy[ymin,0]-xy[ymax,0])+abs(xy[ymin,1]-xy[ymax,1]))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
maxx = -10 ** 10
maxy = -10 ** 10

result = [0]
for i in range(n):
  if maxx <= x[i] and maxy <= y[i]:
    for j in range(n):
      result.append(abs(x[i] - x[j]) + abs(y[i] - y[j]))
      maxx = x[i]
      maxy = y[i]
print(max(result))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    def calc_dist(px, py):
        ret = -1
        retx, rety = -1, -1
        for x, y in P:
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                retx, rety = x, y
        return ret, retx, rety

    prev = -2
    ans = -1
    px, py = P[0]
    while True:
        ans, px, py = calc_dist(px, py)
        if ans == prev:
            print(ans)
            return
        if prev < ans:
            prev = ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Array1 = []
Array2 = []

for i in range(N):
    next_x, next_y = map(int, input().split())
    s = next_x + next_y
    t = next_x - next_y
    Array1.append(s)
    Array2.append(t)

print(max(max(Array1)-min(Array1),max(Array2)-min(Array1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
for i in range(N):
    x,y=[int(i) for i in input().split()]
    A.append(x)
    B.append(y)

mm = (10**9)*2
mmn = 0

pm = 10**9
pmn = 0

mp = 10**9
mpn = 0

pp = 0
ppn = 0

for j in range (N):
    if (A[j]+B[j])>pp:

        pp = A[j]+B[j]
        ppn = j
    if (A[j]-B[j])>pm:

        pm = A[j]-B[j]
        pmn = j
    if (B[j]-A[j])>mp:

        mp = B[j]-A[j]
        mpn = j
    if (A[j]+B[j])<mm:

        mm = A[j]+B[j]
        mmn = j
ans1 = abs(A[ppn] - A[mmn]) + abs(B[ppn] - B[mmn])
ans2 = abs(A[pmn] - A[mpn]) + abs(B[mpn] - B[pmn])
ans3 = abs(A[ppn] - A[pmn]) + abs(B[ppn] - B[pmn])
ans4 = abs(A[mmn] - A[mpn]) + abs(B[mmn] - B[mpn])
ans5 = abs(A[ppn] - A[mpn]) + abs(B[ppn] - B[mpn])
ans6 = abs(A[mmn] - A[pmn]) + abs(B[mmn] - B[pmn])
ans = max(ans1,ans2,ans3,ans4,ans5,ans6)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]


N = int(input())
A = []
B = []
C = []
D = []
for i in range(N):
    x, y = li()
    A.append(x + y)
    B.append(abs(x - y))
    C.append(abs(-x + y))
    D.append(abs(-x - y))

maxA = max(A)
minA = min(A)
maxB = max(B)
minB = min(B)
maxC = max(C)
minC = min(C)
maxD = max(D)
minD = min(D)
maxN = max(maxA, maxB, maxC, maxD)
minN = max(minA, minB, minC, minD)
# ans = max(maxA - minA, maxB - minB, maxC - minC, maxD - minD)
ans = maxN - minN
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
x, y = map(int,input().split())
min_x = x
max_x = x
min_y = y
max_y = y
L = x ** 2 + y ** 2
min_L = L
max_L = L
for i in range(N-1):
  x, y = map(int, input().split())
  L = x ** 2 + y ** 2
  if min_L > L:
    min_x = x
    min_y = y
    min_L = L
  elif max_L < L:
    max_x = x
    max_y = y
    max_L = L
ans = max_x - min_x + max_y - min_y
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def main(args):
    n = int(input())
    
    minx = float('inf')
    maxx = 0
    miny = float('inf')
    maxy = 0
    
    place = []
    for i in range(n):
        x, y = map(int,input().split())
        minx = min(minx,x)
        maxx = max(maxx,x)
        miny = min(miny,y)
        maxy = max(maxy,y)
        place.append((x,y))
    
    Minx = []
    Maxx = []
    Miny = []
    Maxy = []
    
    for x, y in place:
        if x == minx:
            Minx.append((x,y))
        elif x == maxx:
            Maxx.append((x,y))
        if y == miny:
            Miny.append((x,y))
        elif y == maxy:
            Maxy.append((x,y))
    
    if not Maxx:
        print(maxy-miny)
        exit()
    if not Maxy:
        print(maxx-minx)
        exit()
    
    ans = 0
    for i in range(len(Maxx)):
        xi, yi = Maxx[i]
        for j in range(len(Minx)):
            xj, yj = Minx[j]
            tmp = abs(xi-xj)+abs(yi-yj)
            ans = max(tmp,ans)
            
    for i in range(len(Maxx)):
        xi, yi = Maxx[i]
        for j in range(len(Miny)):
            xj, yj = Miny[j]
            tmp = abs(xi-xj)+abs(yi-yj)
            ans = max(tmp,ans)
    
    for i in range(len(Maxy)):
        xi, yi = Maxy[i]
        for j in range(len(Miny)):
            xj, yj = Miny[j]
            tmp = abs(xi-xj) + abs(yi-yj)
            ans = max(ans,tmp)
    
    for i in range(len(Maxy)):
        xi, yi = Maxy[i]
        for j in range(len(Minx)):
            xj, yj = Minx[j]
            tmp = abs(xi-xj) + abs(yi-yj)
            ans = max(ans,tmp)
    
    for i in range(len(Maxx)):
        xi, yi = Maxx[i]
        for j in range(len(Maxy)):
            xj, yj = Maxy[j]
            tmp = abs(xi-xj)+abs(yi-yj)
            ans = max(tmp,ans)
            
    for i in range(len(Minx)):
        xi, yi = Minx[i]
        for j in range(len(Miny)):
            xj, yj = Miny[j]
            tmp = abs(xi-xj)+abs(yi-yj)
            ans = max(tmp,ans)
    
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p = sorted(p, key=lambda i: i[0] + i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
if (x1 <= x2 and y1 <= y2) or (x1 >= x2 and y1 >= y2):
    print(abs((x1 + y1) - (x2 + y2)))
else:
    print(abs((x1 - y1) - (x2 + y2)))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            tmp = abs(list_x[i] - list_x[j]) + abs(list_x[i] - list_y[j])
            if tmp > ans:
                ans = tmp

print(ans)

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 = 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 = max_1 - min_1

print(max([l0, l1]))

Submission status: Wrong Answer

Solution code:
n = int(input())

max1 = 0
min1 = 10 ** 10
max0 = 0
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 = max(max1-min1,max0-min0)

print(ans)

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

if n%2:
    xm_, ym_ = xl_[n//2], yl_[n//2]
else:
    xm_, ym_ = (xl_[n//2-1]+xl_[n//2])/2, (yl_[n//2-1]+yl_[n//2])/2

xm, ym = xm_-1e-6, ym_-1e-6
ans1, ans2, ans3, ans4 = -1, -1, -1, -1
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 = xm_+1e-6, ym_-1e-6
ans1, ans2, ans3, ans4 = -1, -1, -1, -1
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))

xm, ym = xm_-1e-6, ym_+1e-6
ans1, ans2, ans3, ans4 = -1, -1, -1, -1
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))

xm, ym = xm_+1e-6, ym_+1e-6
ans1, ans2, ans3, ans4 = -1, -1, -1, -1
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)) 

xm, ym = xm_, ym_
ans1, ans2, ans3, ans4 = -1, -1, -1, -1
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = 0
Xmin = Ymin = 1e9 + 5
Xmax = Ymax = 0
for _ in range(N):
    x, y = map(int, input().split())
    X = x + y
    Y = abs(x - y)
    Xmin = min(Xmin, X)
    Xmax = max(Xmax, X)
    Ymin = min(Ymin, Y)
    Ymax = max(Ymax, Y)
if Xmin == 1e9 + 5:
    Xmin = Xmax
if Ymin == 1e9 + 5:
    Ymin = Ymax
Z = max(Xmax - Xmin, Ymax - Ymin)
print(Z)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
y = []
xy = []
ans = 0
for i in range(n):
    x1, y1 = map(int, input().split())
    x.append(x1)
    y.append(y1)
    xy.append(x1+y1)
m1 = max(*xy)
m2 = min(*xy)
for i in range(n):
    if xy[i] == m1:
        ma = i
    if xy[i] == m2:
        mi = i
ans = abs(x[ma]-x[mi]) + abs(y[ma]-y[mi])
#for i in range(n-1):
#    for j in range(i,n):
#        m = abs(x[i]-x[j]) + abs(y[i]-y[j])
#        ans = max(ans, m)
print(ans)

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,x-y)
  q=max(q,x-y)
  
print(max(t-s,q-p))

Submission status: Wrong Answer

Solution code:
def Manhattan(ans):
    return abs(ans[0][0]-ans[1][0])+abs(ans[0][1]-ans[1][1])
N=int(input())
xy=[]
for i in range(N):
    xy.append(list(map(int,input().split())))
nowans=[[xy[0][0],xy[0][1]],[xy[1][0],xy[1][1]]]
nowManhattan=Manhattan(nowans)
for j in range(3):
    for i in range(0,N-1):
        nowxy=xy[i]
        if (Manhattan([nowxy,nowans[1]])>nowManhattan):
            nowans=[nowxy,nowans[1]]
            nowManhattan=Manhattan(nowans)
        if (Manhattan([nowans[0],nowxy])>nowManhattan):
            nowans=[nowans[0],nowxy]
            nowManhattan=Manhattan(nowans)
        if (Manhattan([nowxy,nowans[1]])>nowManhattan):
            nowans=[nowxy,nowans[1]]
            nowManhattan=Manhattan(nowans)
        if (Manhattan([nowans[0],nowxy])>nowManhattan):
            nowans=[nowans[0],nowxy]
            nowManhattan=Manhattan(nowans)
print(nowManhattan)

Submission status: Wrong Answer

Solution code:
def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])
 
if __name__=="__main__":
  n=int(input())
  l=[]
  for _ in range(n):
    x=[int(i) for i in input().split()]
    l.append(x)
  if len(l)==1:
    print(0)
    exit
  n=len(l)
  ans=[]
  for i in range(n-1):
    le=i+1
    r=len(l)-1
    ma=-1
    while(i<r):
      mid=le+(r-le)//2
      if dist(l[i],l[mid])>ma:
        ma=dist(l[i],l[mid])
        le=mid+1
      else:
        break
    ans.append(ma)
  print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
num = 10*9 + 5
maxmax = 0
minmin = num
_min = num
_max = 0
for x, y in xy:
    if x + y > maxmax:
        maxmax = x + y
    if x - y > _max:
        _max = x - y
    if x + y < minmin:
        minmin = x + y
    if y - x < _min:
        _min = y - x
result = maxmax - minmin if maxmax - minmin > _max - _min else _max - _min
print(result)

Submission status: Wrong Answer

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

ans = max(points) - min(points)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
    
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:
MOD = 10 ** 9 + 7

N = int(input())
x = 10**N + 8**N - 2*9**N
print(x%MOD)

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

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=list(set(tuple([lnii() for i in range(n)])))
l.sort()
#rint(l)

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

max_v=0
min_v=10**10
for x,y in l:
  max_v=max(max_v,abs(x)+abs(y))
  min_x=max(max_v,abs(x)+abs(y))

print(max_v-min_v)

Submission status: Wrong Answer

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

# main

N = int(input())
xy = int_mtx(N)

x = xy[:,0]
y = xy[:,1]

xmin_p = list(*np.where(x == np.min(x)))
xmax_p = list(*np.where(x == np.max(x)))
ymin_p = list(*np.where(y == np.min(y)))
ymax_p = list(*np.where(y == np.max(y)))

ans = 0

for xmin in xmin_p:
    for xmax in xmax_p:
        ans = max(ans,abs(xy[xmin,0]-xy[xmax,0])+abs(xy[xmin,1]-xy[xmax,1]))
    for ymin in ymin_p:
        ans = max(ans,abs(xy[xmin,0]-xy[ymin,0])+abs(xy[xmin,1]-xy[ymin,1]))
    for ymax in ymax_p:
        ans = max(ans,abs(xy[xmin,0]-xy[ymax,0])+abs(xy[xmin,1]-xy[ymax,1]))

for xmax in xmax_p:
    for ymin in ymin_p:
        ans = max(ans,abs(xy[xmax,0]-xy[ymin,0])+abs(xy[xmax,1]-xy[ymin,1]))
    for ymax in ymax_p:
        ans = max(ans,abs(xy[xmax,0]-xy[ymax,0])+abs(xy[xmax,1]-xy[ymax,1]))

for ymin in ymin_p:
    for ymax in ymax_p:
        ans = max(ans,abs(xy[ymin,0]-xy[ymax,0])+abs(xy[ymin,1]-xy[ymax,1]))

print(ans)

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

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:
X = []
Y = []
maxX = 0
minX = 10**9
maxY = 0
minY = 10**9

N = int(input())
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  maxX, minX = max(maxX, x), min(minX, x)
  maxY, minY = max(maxY, y), min(minY, y)
maxXmaxY = 0
maxXminY = 10**9
minXmaxY = 0
minXminY = 10**9
maxYmaxX = 0
maxYminX = 10**9
minYmaxX = 0
minYminX = 10**9
for i in range(N):
  if X[i]==maxX:
    maxXmaxY = max(maxXmaxY, Y[i])
    maxXminY = min(maxXminY, Y[i])
  if X[i]==minX:
    minXmaxY = max(minXmaxY, Y[i])
    minXminY = min(minXminY, Y[i])
  if Y[i]==maxY:
    maxYmaxX = max(maxYmaxX, X[i])
    maxYminX = min(maxYminX, X[i])
  if Y[i]==minY:
    minYmaxX = max(minYmaxX, X[i])
    minYminX = min(minYminX, X[i])
ans = maxX - minX  + max(abs(maxXmaxY-minXminY),abs(maxXminY-minXmaxY))
ans = max(ans, maxY - minY  + max(abs(maxYmaxX-minYminX),abs(maxYminX-minYmaxX)))
ans = max(ans, maxYmaxX - minX + maxY - minXminY)
ans = max(ans, maxX - maxYminX + maxY - minXminY)
ans = max(ans, minYmaxX - minX + minXmaxY - minY)
ans = max(ans, maxX - minYminX + maxXmaxY - minY)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
maxPlus, minPlus, maxMinus, minMinus = 0, 10**9 , 0, 10**9
for _ in range(n):
    x, y = map(int, input().split())
    maxPlus = max(x + y, maxPlus)
    minPlus = min(x + y, minPlus)
    maxMinus = max(abs(x - y), maxMinus)
    minMinus = min(abs(x - y), minMinus)
print(max(abs(maxPlus - minPlus), abs(maxMinus - minMinus)))

Submission status: Wrong Answer

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

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

    def calc_dist(px, py):
        ret = -1
        retx, rety = -1, -1
        for x, y in P:
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                retx, rety = x, y
        return ret, retx, rety

    prev = -2
    ans = -1
    px, py = P[0]
    while True:
        ans, px, py = calc_dist(px, py)
        if ans == prev:
            print(ans)
            return
        prev = ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a, b = map(int, input().split())
cnt = 0
cnt_min = a+b
cnt_max = a+b


for i in range(N-1):
    x, y = map(int, input().split())
    cnt = x+y
    if cnt < cnt_min:
        cnt_min = cnt
    if cnt > cnt_max:
        cnt_max = cnt

ans = cnt_max - cnt_min
print (ans)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy=sorted(xy, key=lambda x:x[0])
m=10**9+7
mi=-1
Mi=-1
M=0
res=[]
ans=0
for i in range(1,n):
    x,y=xy[i]
    if y<=m:
        mi=i
    if y>=M:
        Mi=i
    res.append([mi,Mi])
for i in range(n-1):
    x,y=xy[i]
    rm,rM=res[i]
    xm,ym=xy[rm]
    xM,yM=xy[rM]
    c=max((abs(x-xm)+abs(y-ym)),(abs(x-xM)+abs(y-yM)))
    ans=max(c,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

d1 = []
d2 = []
for x, y in xy :
  d1.append(x + y)
  d2.append(x - y)

d1.sort(reverse=True)
d2.sort(reverse=True)

print(max(
  d1[0] - d1[-1],
  d1[-1] - d1[0],
  d2[0] + d2[-1],
  d2[-1] - d2[0])
)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]


N = int(input())
A = []
B = []
C = []
D = []
for i in range(N):
    x, y = li()
    A.append(x + y)
    B.append(abs(x - y))
    C.append(abs(-x + y))
    D.append(abs(-x - y))

maxA = max(A)
minA = min(A)
maxB = max(B)
minB = min(B)
maxC = max(C)
minC = min(C)
maxD = max(D)
minD = min(D)
ans = max(maxA - minA, maxB - minB, maxC - minC, maxD - minD)
print(ans)