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:
import sys
import random

random.seed(50)

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
pairs = [map(int, input().split(" ")) for i in range(n)]

for i, (x, y) in enumerate(pairs):
    xy = x+y
    if i == 0:
        min_x = max_x = x
        min_y = max_y = y
        min_xi = [0]
        max_xi = [0]
        min_yi = [0]
        max_yi = [0]

        min_xyi = [0]
        max_xyi = [0]
        min_xy = max_xy = xy 
    else:
        if x < min_x:
            min_xi = [i]
            min_x = x
        elif x == min_x:
            min_xi.append(i)

        if y < min_y:
            min_yi = [i]
            min_y = y
        elif y == min_y:
            min_yi.append(i)

        if xy < min_xy:
            min_xyi = [i]
            min_xy = xy
        elif xy == min_xy:
            min_xyi.append(i)

        if x > max_x:
            max_xi = [i]
            max_x = x
        elif x == min_x:
            max_xi.append(i)

        if y > max_y:
            max_yi = [i]
            max_y = y
        elif y == min_y:
            max_yi.append(i)

        if xy > max_xy:
            max_xyi = [i]
            max_xy = xy
        elif xy == min_xy:
            max_xyi.append(i)



max_iter = 100

fmax_dist = -2

final_out = 0

#print("min_xi", min_xi, "min_yi", min_yi, "max_xi", max_xi, "max_yi", max_yi, "min_xyi", min_xyi, "max_xyi", max_xyi)

first_jibuns = set([random.randint(0, n-1) for i in range(130)])
#first_jibuns = set(min_xi + max_xi + min_yi + max_yi + min_xyi + max_xyi + randoms)

True
for first_jibun in first_jibuns:
    jibun = first_jibun
    #for iter_i in range(max_iter):
    max_dist = -1
    while True:
        jx, jy = pairs[jibun]
        for cur_aite in range(n):
            if jibun == cur_aite:
                continue
            ax, ay = pairs[cur_aite]
            cdist = abs(jx-ax) + abs(jy-ay)
            
            if cdist > max_dist:
                next_jibun = cur_aite
                max_dist = cdist

        if fmax_dist == max_dist:
            out = max_dist
            break
        else:
            jibun = next_jibun 
            fmax_dist = max_dist

    final_out = max(final_out, out)
    
    
print(final_out)

Submission status: Wrong Answer

Solution code:
n=int(input())

x=[]
y=[]
for _ in range(n):
    xx,yy=map(int,input().split())
    x.append(xx)
    y.append(yy)

def maxAbsValExpr(arr1, arr2):
    minX, maxX = min(arr1), max(arr1)
    minY, maxY = min(arr2), max(arr2)
    
    ans = 0
    # For all four corners, calculate the max distance differences
    for point in [(minX, minY), (maxX, minY), (minX, maxY), (maxX, maxY)]:
        minD = float('inf')
        maxD = float('-inf')
        for i in range(0, len(arr1)):
            distance = abs(arr1[i]-point[0]) + abs(arr2[i]-point[1]) + i
            minD = min(minD, distance)
            maxD = max(maxD, distance)
            ans = max(ans, maxD - minD)
    return ans


print(maxAbsValExpr(x, y))

Submission status: Wrong Answer

Solution code:
N = int(input())
tmp1 = []

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

if len(tmp1) > 0:
    tmp = []
    for i in range(len(tmp1)):
        tmp.append(tmp1[i][2])
    ans = max(tmp)-min(tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xlis = [0]
ylis = [0]
for _ in range(n):
    x, y = map(int, input().split())
    xlis.append(x)
    ylis.append(y)
 
if (xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) >= 0:
    defa1 = 1
    defa2 = 2
elif (xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) <= 0:
    defa1 = 2
    defa2 = 1
 
for i in range(1, n+1):
    new1 = i
    defa1p = (xlis[defa1], ylis[defa1])
    defa2p = (xlis[defa2], ylis[defa2])
    new1p = (xlis[new1], ylis[new1])
 
    if (new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) >= 0:
        defa2 = new1
    elif (new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) <= 0 <= (new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]):
        pass
    elif (new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]) <= 0:
        defa1 = new1

max1 = (xlis[defa2]-xlis[defa1]) + (ylis[defa2]-ylis[defa1])
if -(xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) >= 0:
    defa1 = 1
    defa2 = 2
elif -(xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) <= 0:
    defa1 = 2
    defa2 = 1
 
for i in range(1, n+1):
    new1 = i
    defa1p = (xlis[defa1], ylis[defa1])
    defa2p = (xlis[defa2], ylis[defa2])
    new1p = (xlis[new1], ylis[new1])
 
    if -(new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) >= 0:
        defa2 = new1
    elif -(new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) <= 0 <= (new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]):
        pass
    elif -(new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]) <= 0:
        defa1 = new1
max2 = -(xlis[defa2]-xlis[defa1]) + (ylis[defa2]-ylis[defa1])

print(max(max1, max2))

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


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


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


def search(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())

xmax = ymax = 1
ymin = xmin = 10**9
xmax_i = ymax_i = 0
xmin_i = ymin_i = 0

X = []
for i in range(N):

    x, y = acinput()
    X.append([x, y])
    if i == 0:
        continue
    if x > xmax:
        xmax = x
        xmax_i = i
    if y > ymax:
        ymax = y
        ymax_i = i
    if x < xmin:
        xmin = x
        xmin_i = i
    if y < ymin:
        ymin = y
        ymin_i = i

s = [xmax_i, xmin_i, ymax_i, ymin_i]

# print(s)
# print(X)
S = []
for i in s:
    S.append(X[i])

res = 0
for i in range(2):
    for j in range(2, 4):
        tmp = abs(S[j][0]-S[i][0])+abs(S[j][1]-S[i][1])
        res = max(res, tmp)

print(res)

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(n-1,0,-1):
    x,y=xy[i]
    if y<=m:
        mi=i
        m=y
    if y>=M:
        Mi=i
        M=y
    res.append([mi,Mi])
for i in range(n-1):
    x,y=xy[i]
    rm,rM=res[n-2-i]
    xm,ym=xy[rm]
    xM,yM=xy[rM]
    xs,ys=xy[-1]
    c=max((abs(x-xm)+abs(y-ym)),(abs(x-xM)+abs(y-yM)),(abs(x-xs)+abs(y-ys)))
    ans=max(c,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ps = list({
    tuple(map(int, input().split()))
    for _ in range(n)
})

g0 = sum([p[0] for p in ps]) / len(ps)
g1 = sum([p[1] for p in ps]) / len(ps)

maxd = 0
maxp = ps[0]
for p in ps:
    d = p[0] + p[1]
    if d > maxd:
        maxp = p
        maxd = d

maxd = 0
for p in ps:
    maxd = max(maxd, abs(maxp[0] - p[0]) + abs(maxp[1] - p[1]))
print(maxd)

Submission status: Wrong Answer

Solution code:
n = int(input())



mi, ma = 0, 0
for i in range(n):
    x, y = map(int, input().split())
    x, y = abs(x), abs(y)
    mi = min(mi, x + y)
    ma = max(ma, x + y)

print(ma - mi)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
data = []
for i in range(n):
	x,y = readInts()
	data.append([x+y,x,y])

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

print(abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))

Submission status: Wrong Answer

Solution code:
n=input()
maxa=-1
mina=10000000000
maxb=-1
minb=10000000000

for i in range(int(n)):
    x,y=map(int,input().split())
    maxa=max(maxa,x+y)
    mina=min(mina,x+y)
    maxb=max(maxb,x-y)
    minb=min(minb,x-y)

print(max(abs(maxa-mina),abs(maxb-minb)))

Submission status: Wrong Answer

Solution code:
N = int(input())
p1, p2, p3, p4 = [[10**9, 10**9], [0, 0], [0, 10**9], [10**9, 0]]
ans = 0
for i in range(N):
    x, y = map(int, input().split())
    if p1[0] >= x and p1[1] >= y:
        p1 = [x, y]
    if p2[0] <= x and p2[1] <= y:
        p2 = [x, y]
    if p3[0] <= x and p3[1] >= y:
        p3 = [x, y]
    if p4[0] >= x and p4[1] <= y:
        p4 = [x, y]
P = [p1, p2, p3, p4]
for x1, y1 in P:
    for x2, y2 in P:
        ans = max(ans, abs(x1-x2)+abs(y1-y2))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
point_ls = [[0]*2 for _ in range(N)]
for i in range(N):
    point_ls[i] = list(map(int, input().split()))
xmin = float('inf')
xmax = 0
ymin = float('inf')
ymax = 0
xmin_ymax = [0,0]
xmin_ymin = [0,0]
xmax_ymax = [0,0]
xmax_ymin = [0,0]
ymax_xmin = [0,0]
ymin_xmin = [0,0]
ymax_xmax = [0,0]
ymin_xmax = [0,0]

for i in range(N):
    x,y = point_ls[i]
    if x == xmin:
        if y > xmin_ymax[1]:
            xmin_ymax[1] = y
            xmin_ymin[0] = x
        if y < xmin_ymin[0]:
            xmin_ymin[1] = y
            xmin_ymin[0] = x
    if x < xmin:
        xmin_ymax = [x,y]
        xmin_ymin = [x,y]
        xmin = x
    if x == xmax:
        if y > xmax_ymax[1]:
            xmax_ymax[1] = y
            xmax_ymin[0] = x
        if y < xmax_ymin[0]:
            xmax_ymin[1] = y
            xmax_ymin[0] = x
    if x > xmax:
        xmax_ymax = [x,y]
        xmax_ymin = [x,y]
        xmax = x
    if y == ymax:
        if x > ymax_xmax[0]:
            ymax_xmax[0] = x
        if x < ymax_xmin[0]:
            ymax_xmin[0] = x
    if y > ymax:
        ymax_xmax = [x,y]
        ymax_xmin = [x,y]
        ymax = y 
    if y == ymin:
        if x > ymin_xmax[0]:
            ymin_xmax[0] = x
        if x < ymin_xmin[0]:
            ymin_xmin[0] = x
    if y < ymin:
        ymin_xmax = [x,y]
        ymin_xmin = [x,y]
        ymin = y

cand = [xmax_ymax,xmax_ymin,xmin_ymax,xmin_ymin,ymax_xmax,ymax_xmin,ymin_xmax,ymin_xmin]
ans = 0
#print(cand)
for i,j in combinations(cand,2):
    ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random

random.seed(40)

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
pairs = [map(int, input().split(" ")) for i in range(n)]

for i, (x, y) in enumerate(pairs):
    xy = x+y
    if i == 0:
        min_x = max_x = x
        min_y = max_y = y
        min_xi = [0]
        max_xi = [0]
        min_yi = [0]
        max_yi = [0]

        min_xyi = [0]
        max_xyi = [0]
        min_xy = max_xy = xy 
    else:
        if x < min_x:
            min_xi = [i]
            min_x = x
        elif x == min_x:
            min_xi.append(i)

        if y < min_y:
            min_yi = [i]
            min_y = y
        elif y == min_y:
            min_yi.append(i)

        if xy < min_xy:
            min_xyi = [i]
            min_xy = xy
        elif xy == min_xy:
            min_xyi.append(i)

        if x > max_x:
            max_xi = [i]
            max_x = x
        elif x == min_x:
            max_xi.append(i)

        if y > max_y:
            max_yi = [i]
            max_y = y
        elif y == min_y:
            max_yi.append(i)

        if xy > max_xy:
            max_xyi = [i]
            max_xy = xy
        elif xy == min_xy:
            max_xyi.append(i)



max_iter = 100

fmax_dist = -2

final_out = 0

#print("min_xi", min_xi, "min_yi", min_yi, "max_xi", max_xi, "max_yi", max_yi, "min_xyi", min_xyi, "max_xyi", max_xyi)

first_jibuns = set([random.randint(0, n-1) for i in range(130)])
#first_jibuns = set(min_xi + max_xi + min_yi + max_yi + min_xyi + max_xyi + randoms)

True
for first_jibun in first_jibuns:
    jibun = first_jibun
    #for iter_i in range(max_iter):
    max_dist = -1
    while True:
        jx, jy = pairs[jibun]
        for cur_aite in range(n):
            if jibun == cur_aite:
                continue
            ax, ay = pairs[cur_aite]
            cdist = abs(jx-ax) + abs(jy-ay)
            
            if cdist > max_dist:
                next_jibun = cur_aite
                max_dist = cdist

        if fmax_dist == max_dist:
            out = max_dist
            break
        else:
            jibun = next_jibun 
            fmax_dist = max_dist

    final_out = max(final_out, out)
    
    
print(final_out)

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    x =  [0]*n
    y = [0]*n
    inf = int(1e9)
    for i in range(n):
        x[i],y[i] = map(int, input().split(" "))
    xh = max(x)
    xl = min(x)
    yh = max(y)
    yl = min(x)
    xhh = 0
    xhl = inf
    xlh = 0
    xll = inf
    yhh = 0
    yhl = inf
    ylh = 0
    yll = inf
    for i in range(n):
        if x[i] == xh:
            if y[i] > xhh:
                xhh = y[i]
            if y [i] < xhl:
                xhl = y[i]
        if x[i] == xl:
            if y[i] > xlh:
                xlh = y[i]
            if y[i] < xll:
                xll = y[i]
        if y[i] == yh:
            if x[i] > yhh:
                yhh = x[i]
            if x[i] < yhl:
                yhl = x[i]
        if y [i] == yl:
            if x[i] > ylh:
                ylh = x[i]
            if x[i] < yll:
                yll = x[i]
    print(max((abs(xhh-xll)+abs(yhh-yll)),(abs(xhl-xlh)+abs(yhl-ylh))))
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for num in range(n):
  l += [list(map(int,input().split()))]
maxn = -1
maxx = -1
maxy = -1
miny = 2*10**10
minx = 2*10**10
for num in range(n):
  if maxx < l[num][0]:
    maxx = l[num][0]
  if maxy < l[num][1]:
    maxy = l[num][1]
  if minx > l[num][0]:
    minx = l[num][0]
  if miny > l[num][1]:
    miny = l[num][1]   
for num in range(n):
  if maxx == l[num][0] or maxy == l[num][1] or minx == l[num][0] or miny == l[num][1]:
    for j in range(n):
      if (num != j):
        if abs(l[num][0]-l[j][0])+abs(l[num][1]-l[j][1]) > maxn:
          maxn = abs(l[num][0]-l[j][0])+abs(l[num][1]-l[j][1])
print(maxn)

Submission status: Wrong Answer

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

x_ = sorted(x_y, key=lambda x: x[0])

#print(x_)
ans = 0
for l in range(n):
	for r in range(n-1,l,-1):
#		print(l,r)
		kyori = (x_[r][0] - x_[l][0]) + (x_[r][1] - x_[l][1])
		if kyori < 0:
			kyori = -kyori
		print(kyori)
		if kyori > ans:
			ans = kyori
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    P = []
    for _ in range(N):
        x, y = input().split()
        P.append((int(x), int(y)))
    lb = min(P, key=lambda t: t[0] + t[1])
    rt = max(P, key=lambda t: t[0] + t[1])
    P.sort(key=lambda t: t[1])
    P.sort(key=lambda t: t[0])
    lt = P[-1]
    P.sort(key=lambda t: t[1])
    rb = P[-1]

    ans1 = rt[0] - lb[0] + rt[1] - lb[1]
    ans2  = rb[0] - lt[0] + lt[1] - rb[1]
    print(max(ans1, ans2))

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


X=int(input())

x,y=map(int,input().split())
E=(x,y)
W=(x,y)
S=(x,y)
N=(x,y)
for i in range(1,X):
    x,y=map(int,input().split())
    if E[0]<x:E=(x,y)
    if W[0]>x:W=(x,y)
    if S[1]>y:S=(x,y)
    if N[1]<y:N=(x,y)

ans=abs(E[0]-S[0])+abs(E[1]-S[1])

ans2=abs(E[0]-N[0])+abs(E[1]-N[1])
if ans2>ans: ans=ans2

ans2=abs(W[0]-S[0])+abs(W[1]-S[1])
if ans2>ans: ans=ans2

ans2=abs(W[0]-N[0])+abs(W[1]-N[1])
if ans2>ans: ans=ans2

#print(E,W,S,N)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
x = list(sorted(l,key=lambda x: x[0]))
y = list(sorted(l,key=lambda x: x[1]))
ans = 0
for i in range(1,n):
    ans = max(ans,abs(x[0][0]-x[i][0])+abs(x[0][1]-x[i][-1]))
for i in range(n-1):
    ans = max(ans,abs(x[-1][0]-x[i][0])+abs(x[-1][1]-x[i][-1]))
for i in range(1,n):
    ans = max(ans,abs(y[0][0]-y[i][0])+abs(y[0][1]-y[i][-1]))
for i in range(n-1):
    ans = max(ans,abs(y[-1][0]-y[i][0])+abs(y[-1][1]-y[i][-1]))
print(ans)

Submission status: Wrong Answer

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

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

for i in range(N):
    if (minD > math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])):
        minD = math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])
        min = i
    if (maxD < math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])):
        maxD = math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*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:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=0
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):#右上
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):#左上
    local=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=local
for i in range(0,n):#右下
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

Submission status: Wrong Answer

Solution code:
#E - Dist Max
N = int(input())
x =[list(map(int, input().split())) for i in range(N)]
max_x = 0
max_x_i = 0
min_x = 0
min_x_i = 0
for i in range(N):
    if max_x <= x[i][0]+x[i][1]:
        max_x = x[i][0]+x[i][1]
        max_x_i = i
    else:
        pass
    if min_x >= x[i][0]+x[i][1]:
        min_x = x[i][0]+x[i][1]
        min_x_i = i

ans = abs(x[max_x_i][0]-x[min_x_i][0])+abs(x[max_x_i][1]-x[min_x_i][1])
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**1000
max_xy_1=0
min_xy_1=10**1000

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:
from sys import stdin
input = stdin.readline
xmin1, xmax1 = None, None
ymin1, ymax1 = None, None
xmin2, xmax2 = None, None
ymin2, ymax2 = None, None
for _ in range(int(input())):
    x, y = map(int,input().split())
    if xmin1 == None:
        xmin1 = xmax1 = ymin1 = ymax1 = (x,y)
        xmin2 = xmax2 = ymin2 = ymax2 = (x,y)
    else:
        if xmin1[0]>x:
            xmin1 = x,y
            xmin2 = x,y
        elif xmin1[0]==x:
            if xmin1[1]<y:
                xmin1=x,y
            if xmin2[1]>y:
                xmin2=x,y
        if xmax1[0]<x:
            xmax1 = x,y
            xmax2 = x,y
        elif xmax1[0]==x:
            if xmax1[1]<y:
                xmax1=x,y
            if xmax2[1]>y:
                xmax2=x,y
        if ymin1[1]>y:
            ymin1 = x,y
            ymin2 = x,y
        elif ymin1[1]==y:
            if ymin1[0]>x:
                ymin1 = x,y
            if ymin2[0]<x:
                ymin2 = x,y
        if ymax1[1]<y:
            ymax1 = x,y
            ymax2 = x,y
        elif ymax1[1]==y:
            if ymax1[0]>x:
                ymax1 = x,y
            if ymax2[0]<x:
                ymax2 = x,y
arr =  [xmin1, xmin2, xmax1, xmax2, ymin1, ymin2, ymax1, ymax2]
man = 0
for i,j in arr:
    for i1,j1 in arr:
        man = max(man, abs(i-i1)+abs(j-j1))
print(man)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = set()
for i in range(n):
    x, y = map(int, input().split())
    p.add((x, y))

min_x = (pow(10, 9), pow(10, 9))
min_y = (pow(10, 9), pow(10, 9))
max_x = (0, 0)
max_y = (0, 0)
for x, y in p:
    if min_x[0] > x:
        min_x = (x, y)
    if min_y[1] > y:
        min_y = (x, y)
    if max_x[0] < x:
        max_x = (x, y)
    if max_y[1] < y:
        max_y = (x, y)

d1 = abs(min_x[0]-max_x[0])+abs(min_x[1]-max_x[1])
d2 = abs(min_x[0]-max_y[0])+abs(min_x[1]-max_y[1])
d3 = abs(min_y[0]-max_x[0])+abs(min_y[1]-max_x[1])
d4 = abs(min_y[0]-max_y[0])+abs(min_y[1]-max_y[1])
d5 = abs(min_x[0]-min_y[0])+abs(min_x[1]-min_y[1])
d6 = abs(max_x[0]-max_y[0])+abs(max_x[1]-max_y[1])
print(max(d1, d2, d3, d4, d5, d6))

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 = xl_[n//2-1]
ans = 0
for k in range(min(n, 100)):
    ym = yl[k]
    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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
K = []
for i in range(N):
    x, y = map(int,input().split())
    t = x + y
    if x <= 0:
        t -= 4*abs(x)
    if y <= 0:
        t -= 4*abs(y)
    K.append([t, x, y])

K.sort()
ans = abs(K[0][0] - K[-1][0])
A = [K[0][1]]
for i in range(N-1):
    if K[i][0] == K[i+1][0]:
        A.append(K[i+1][1])
    else:
        ans = max(ans, max(A) - min(A))
        A = [K[i][1]]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x_y = [[] for _ in range(n)]

for i in range(n):
    _x, _y = map(int, input().split())
    x_y[i] = [_x, _y]

ans = 0

x_y.sort(key=lambda x:x[0])
for i in range(n):
    max_dist_x = abs(x_y[-1][0] - x_y[i][0])
    max_dist_y = abs(x_y[-1][1] - x_y[i][1])
    ans = max(ans, max_dist_x + max_dist_y)

x_y.sort(key=lambda x:x[1])
for i in range(n):
    max_dist_x = abs(x_y[-1][0] - x_y[i][0])
    max_dist_y = abs(x_y[-1][1] - x_y[i][1])
    ans = max(ans, max_dist_x + max_dist_y)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
L.sort(key = lambda x: abs(x[0] + x[1]), reverse = True)

base_x = L[0][0] 
base_y = L[0][1]
ans = 0
for l in L:
    ans = max(ans, abs(l[0] - base_x) + abs(l[1] - base_y))

print(ans)

Submission status: Wrong Answer

Solution code:
Row=int(input())
X=[]
Y=[]
for i in range(Row):
    n,a=input().split()
    X.append(int(n))
    Y.append(int(a))
A=[]
B=[]
for i in range(len(X)):
    A.append(X[i]-Y[i])
    B.append(X[i]+Y[i])
maxmax1=0
maxmax2=0
minmin1=10**10
minmin2=10**12
for i in range(len(A)):
    maxmax1=max(maxmax1,A[i])
    minmin1=min(minmin1,A[i])
for i in range(len(B)):
    maxmax2=max(maxmax2,B[i])
    minmin2=min(minmin2,B[i])
print(max((maxmax1-minmin1),(maxmax2-minmin2)))

Submission status: Wrong Answer

Solution code:
n = int(input())

points = set()
for i in range(n):
    l = tuple(int(each) for each in input().split())
    points.add(l)
x, y = zip(*points)

# print(x, y)

x_max = max(x)
y_max = max(y)
x_min = min(x)
y_min = min(y)

x_max_points = [each for each in points if each[0] == x_max]
x_min_points = [each for each in points if each[0] == x_min]
y_max_points = [each for each in points if each[1] == y_max]
y_min_points = [each for each in points if each[1] == y_min]
len_candidate = []
for i in range(len(x_max_points)):
    for j in range(len(x_min_points)):
        len_candidate.append(abs(x_max_points[i][0]-x_min_points[j][0]) + abs(x_max_points[i][1]-x_min_points[j][1]))

for i in range(len(y_max_points)):
    for j in range(len(y_min_points)):
        len_candidate.append(abs(y_max_points[i][0]-y_min_points[j][0]) + abs(y_max_points[i][1]-y_min_points[j][1]))

print(max(len_candidate))

Submission status: Wrong Answer

Solution code:
#import random
n=int(input())

pnt=[]
for i in range(n):
  pnt.append(list(map(int,input().split())))
  #pnt.append([random.randint(int(-1e9),int(1e9)),random.randint(int(-1e9),int(1e9))])
pnt.sort(key=lambda x:abs(x[0])+abs(x[1]),reverse=True)
mn=list(reversed(pnt))
mx=0

for i in range(min(n,6000)):
  for j in range(i+1,min(n,6000)):
    mx=max(abs(pnt[i][0]-pnt[j][0])+abs(pnt[i][1]-pnt[j][1]),mx)
    mx=max(abs(pnt[i][0]-mn[j][0])+abs(pnt[i][1]-mn[j][1]),mx)
print(mx)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    P = []
    for _ in range(N):
        x, y = input().split()
        P.append((int(x), int(y)))
    lb = min(P, key=lambda t: t[0] + t[1])
    rt = max(P, key=lambda t: t[0] + t[1])
    P.sort(key=lambda t: t[1])
    P.sort(key=lambda t: t[0])
    lt = P[-1]
    P.sort(key=lambda t: t[1])
    rb = P[-1]

    print(rt, lt, lb, rb)
    ans1 = rt[0] - lb[0] + rt[1] - lb[1]
    ans2  = rb[0] - lt[0] + lt[1] - rb[1]
    print(max(ans1, ans2))

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
r = [0,0]
t = [0,0]
l = [10**9+1,10**9+1]
bot = [10**9+1,10**9+1]
for _ in range(n):
    a, b = map(int, input().split())
    if a >= r[0] and b > r[1]:
        r = [a, b]
    if a <= l[0] and b < l[1]:
        l = [a, b]
    if b >= t[1] and a > t[0]:
        t = [a, b]
    if b <= bot[1] and a < bot[0]:
        bot = [a, b]

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

res = max(manhat(l,r), manhat(bot,r), manhat(l,t), manhat(bot,t), manhat(t,r), manhat(l,bot))
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import random

random.seed(3)

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
pairs = [map(int, input().split(" ")) for i in range(n)]

for i, (x, y) in enumerate(pairs):
    xy = x+y
    if i == 0:
        min_x = max_x = x
        min_y = max_y = y
        min_xi = [0]
        max_xi = [0]
        min_yi = [0]
        max_yi = [0]

        min_xyi = [0]
        max_xyi = [0]
        min_xy = max_xy = xy 
    else:
        if x < min_x:
            min_xi = [i]
            min_x = x
        elif x == min_x:
            min_xi.append(i)

        if y < min_y:
            min_yi = [i]
            min_y = y
        elif y == min_y:
            min_yi.append(i)

        if xy < min_xy:
            min_xyi = [i]
            min_xy = xy
        elif xy == min_xy:
            min_xyi.append(i)

        if x > max_x:
            max_xi = [i]
            max_x = x
        elif x == min_x:
            max_xi.append(i)

        if y > max_y:
            max_yi = [i]
            max_y = y
        elif y == min_y:
            max_yi.append(i)

        if xy > max_xy:
            max_xyi = [i]
            max_xy = xy
        elif xy == min_xy:
            max_xyi.append(i)



max_iter = 100

fmax_dist = -2

final_out = 0

#print("min_xi", min_xi, "min_yi", min_yi, "max_xi", max_xi, "max_yi", max_yi, "min_xyi", min_xyi, "max_xyi", max_xyi)

first_jibuns = set([random.randint(0, n-1) for i in range(150)])
#first_jibuns = set(min_xi + max_xi + min_yi + max_yi + min_xyi + max_xyi + randoms)

True
for first_jibun in first_jibuns:
    jibun = first_jibun
    #for iter_i in range(max_iter):
    max_dist = -1
    while True:
        jx, jy = pairs[jibun]
        for cur_aite in range(n):
            if jibun == cur_aite:
                continue
            ax, ay = pairs[cur_aite]
            cdist = abs(jx-ax) + abs(jy-ay)
            
            if cdist > max_dist:
                next_jibun = cur_aite
                max_dist = cdist

        if fmax_dist == max_dist:
            out = max_dist
            break
        else:
            jibun = next_jibun 
            fmax_dist = max_dist

    final_out = max(final_out, out)
    
    
print(final_out)

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 = xl_[n//2-1]
ans = 0
for k in range(min(n, 100)):
    ym = yl[k]
    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(ans)

Submission status: Wrong Answer

Solution code:
Row = int(input())
List = []
for i in range (Row):
  List.append(list(map(int, input().split())))
xList = sorted(List, reverse=True, key=lambda x: x[0])  #[0]に注目してソート
yList = sorted(List, reverse=True, key=lambda x: x[1])  #[1]に注目してソート
distx =abs(xList[Row-1][0]-xList[0][0])+abs(xList[Row-1][1]-xList[0][1])
disty =abs(yList[Row-1][0]-yList[0][0])+abs(yList[Row-1][1]-yList[0][1])
distxy =abs(xList[Row-1][0]-yList[0][0])+abs(xList[Row-1][1]-yList[0][1])
distyx =abs(yList[Row-1][0]-xList[0][0])+abs(yList[Row-1][1]-xList[0][1])
res = max(distx,disty,distxy,distyx)
print(res)