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 numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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


def det(p, q):
    return p[0] * q[1] - p[1] * q[0]


def sub(p, q):
    return (p[0] - q[0], p[1] - q[1])


def get_convex_hull(points):
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n - 2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]


X = get_convex_hull(X)
# print(X)

sx, sy = X[0]
si = 0
mdist = -1

# while 1:
used = [0] * len(X)
for index, start in enumerate(X):
    if used[index] == 1:
        continue
    sx, sy = start
    maxv = -1
    maxi = -1
    for i, xi in enumerate(X):
        if i == si:
            continue
        x, y = xi
        x, y = x - sx, y - sy
        xx, yy = x + y, x - y
        dist = max(abs(xx), abs(yy))
        # print("dist", dist)
        if maxv < dist:
            maxi = i
            maxv = dist
    # print("index, maxi", index, maxi)
    used[maxi] = 1
    mdist = max(mdist, maxv)

print(mdist)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
ll = []
for _ in range(n):
    x, y = map(int, input().split())
    l.append((x+y, x, y))
    ll.append((x-y, x, y))
l.sort()
ll.sort()
ans1 = 0
ans2 = 0

cnt = 0
while True:
    a = l[-cnt]
    b = l[cnt]
    if a[1] >= b[1] and a[2] >= b[2]:
        ans1 = abs(b[0]-a[0])
        break
    if cnt >= n-1:
        break
    cnt += 1

cnt = 0
while True:
    a = l[-cnt]
    b = l[cnt]
    if a[1] >= a[2] and b[2] >= b[1]:
        ans2 = abs(b[0]-a[0])
        break
    if cnt >= n-1:
        break
    cnt += 1

print(max(ans1, ans2))

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, 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)))
print(max(ans, ans_))

Submission status: Wrong Answer

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

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

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

ps = []

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

anses = []

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

Submission status: Wrong Answer

Solution code:
import sys
N=int(sys.stdin.readline().strip())
XY=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XY.sort(key=lambda x:(x[0],x[1]) )
a1=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
XY.sort(key=lambda x:(x[1],x[0]) )
a2=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
XY.sort(key=lambda x:(x[0],-x[1]) )
a3=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
XY.sort(key=lambda x:(x[1],-x[0]) )
a4=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
print max(a1,a2,a3,a4)

Submission status: Wrong Answer

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

B=[]
for i,j in A:
    B.append(i+j)

print(max(B)-min(B))

Submission status: Wrong Answer

Solution code:
N = int(input())
i = []
j = []
for k in range(N):
    x, y = map(int, input().split())
    i.append(x+y)
    j.append(-x-y)

p = max(i)

del j[i.index(max(i))]

m = max(j)

print(p+m)

Submission status: Wrong Answer

Solution code:
n = int (input())

xy = []

def dist(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
    
for i in range(n):
    x, y = map(int,input().split())
    xy.append([x, y])

xy.sort(key = lambda x: x[0]+x[1])

dist(xy[0], xy[-1])


ans = 0
l = int((n//2)**0.5)
for i in range(l):
    for j in range(l+1):
        ans = max(ans, dist(xy[i], xy[n-1-j]))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

min_x = 10**9
max_x = 1
min_y = 10**9
max_y = 1
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_x = min(x, min_x)
    max_x = max(x, max_x)
    min_y = min(y, min_y)
    max_y = max(y, max_y)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

cand_set = set()
for x,y in XY:
    if x in (min_x, max_x) or y in (min_y, max_y) or x+y in (min_sum, max_sum):
        cand_set.add((x, y))

dist = 0
for p1, p2 in combinations(cand_set, 2):
    print(p1, p2)
    dist = max(dist, abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]))
    
print(dist)

Submission status: Wrong Answer

Solution code:
def main():
    n, *xy = map(int, open(0).read().split())
    p = [(i, j) for i, j in zip(xy[::2], xy[1::2])]

    a = sorted(p, key=lambda x: x[0], reverse=True)
    b = sorted(p, key=lambda x: x[1], reverse=True)

    c = sorted(p, key=lambda x: (x[0], x[1]), reverse=True)
    d = sorted(p, key=lambda x: (x[0], -x[1]), reverse=True)
    e = sorted(p, key=lambda x: (-x[0], x[1]), reverse=True)

    f = sorted(p, key=lambda x: (x[1], x[0]), reverse=True)
    g = sorted(p, key=lambda x: (x[1], -x[0]), reverse=True)
    h = sorted(p, key=lambda x: (-x[1], x[0]), reverse=True)

    dist = lambda p, q: abs(p[0] - q[0]) + abs(p[1] - q[1])

    ans = max(dist(x[0], x[1]) for x in [a, b, c, d, e, f, g, h])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
x_numbers=[]
y_numbers=[]
for _ in range(N):
    x,y=map(int,input().split())
    x_numbers.append([x,y])
    y_numbers.append([y,x])
sort_x_numbers=sorted(x_numbers)
sort_y_numbers=sorted(y_numbers)
ans1=[]
ans2=[]
ans3=[]
ans4=[]
x3=sort_x_numbers[0]
x1=sort_x_numbers[-1]
for n in x_numbers:
    ans1.append(abs(n[0]-x1[0])+abs(n[1]-x1[1]))
for n in x_numbers:
    ans3.append(abs(n[0]-x3[0])+abs(n[1]-x3[1]))
ans11=max(ans1)
ans33=max(ans3)
x2=sort_y_numbers[-1]
x4=sort_y_numbers[0]
for n in x_numbers:
    ans2.append(abs(n[0]-x2[1])+abs(n[1]-x2[0]))
for n in x_numbers:
    ans4.append(abs(n[0]-x4[1])+abs(n[1]-x4[0]))
ans22=max(ans2)
ans44=max(ans4)
print(max(ans11,ans22,ans33,ans44))

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 = 0

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

Submission status: Wrong Answer

Solution code:
N = int(input())

x,y = map(int, input().split())
r = (x,y)
l = (x,y)
u = (x,y)
d = (x,y)

for i in range(N-1):
    x,y = map(int, input().split())
    if x < l[0]:
        l = (x,y)
    if x > r[0]:
        r = (x,y)
    if y > u[1]:
        u = (x,y)
    if y < d[1]:
        d = (x,y)

print(max(
    abs(l[0]-r[0])+abs(l[1]-r[1]),
    abs(l[0]-u[0])+abs(l[1]-u[1]),
    abs(l[0]-d[0])+abs(l[1]-d[1]),
    abs(r[0]-u[0])+abs(r[1]-u[1]),
    abs(r[0]-d[0])+abs(r[1]-d[1]),
    abs(u[0]-d[0])+abs(u[1]-d[1]),
))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
mx = - float("inf")
nums=[]

for _ in range(N):
  nums.append(list(map(int,input().split())))
mixmiy=nums[0]
maxmiy=nums[0]
mixmay=nums[0]
maxmay=nums[0]
for i in nums[1:]:
  if mixmiy[0] > i[0] or mixmiy[1] > i[1]:
    mixmiy = i if (abs(mixmiy[0])+abs(mixmiy[1])) < (abs(i[0])+abs(i[1])) else mixmiy
  if maxmiy[0] < i[0] or maxmiy[1] > i[1]:
    maxmiy = i if (abs(maxmiy[0])+abs(maxmiy[1])) < (abs(i[0])+abs(i[1])) else maxmiy
  if mixmay[0] > i[0] or mixmay[1] < i[1]:
    mixmay = i if (abs(mixmay[0])+abs(mixmay[1])) < (abs(i[0])+abs(i[1])) else mixmay
  if maxmay[0] < i[0] or maxmay[1] < i[1]:
    maxmay = i if (abs(maxmay[0])+abs(maxmay[1])) < (abs(i[0])+abs(i[1])) else maxmay

mx = max(
  abs(maxmay[0]-mixmiy[0])+abs(maxmay[1]-mixmiy[1]),
  abs(maxmay[0]-maxmiy[0])+abs(maxmay[1]-maxmiy[1]),
  abs(maxmay[0]-mixmay[0])+abs(maxmay[1]-mixmay[1]),

  abs(maxmiy[0]-mixmay[0])+abs(maxmiy[1]-mixmay[1]),
  abs(maxmiy[0]-mixmiy[0])+abs(maxmiy[1]-mixmiy[1]),

  abs(mixmiy[0]-mixmay[0])+abs(mixmiy[1]-mixmay[1])

)
print(mx)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
ll = []
for _ in range(n):
    x, y = map(int, input().split())
    l.append((x+y, x, y))
    ll.append((x-y, x, y))
l.sort()
ll.sort()
ans1 = 0
ans2 = 0

cnt = 0
while True:
    a = l[-cnt]
    b = l[cnt]
    if a[1] >= b[1] and a[2] >= b[2]:
        ans1 = b[0]-a[0]
        break
    if cnt >= n-1:
        break
    cnt += 1

cnt = 0
while True:
    a = l[-cnt]
    b = l[cnt]
    if a[1] >= a[2] and b[2] >= b[1]:
        ans2 = b[0]-a[0]
        break
    if cnt >= n-1:
        break
    cnt += 1

print(max(ans1, ans2))

Submission status: Wrong Answer

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


a1 = [a,b] #左下
a2 = [a,b] #左上
a3 = [a,b] #右上
a4 = [a,b] #右下


for i in range(n-1):
    a,b=map(int, input().split())
    data.append([a, b])
    if (a < a1[0] and b < a1[1]):
        a1 = [a,b]

    if (a < a2[0] and b > a2[1]):
        a2 = [a, b]

    if (a > a3[0] and b > a3[1]):
        a3 = [a, b]

    if (a > a4[0] and b < a4[1]):
        a4 = [a, b]

ans = -1
for i in data:

    a = i[0]
    b = i[1]

    ans = max(ans, abs(a1[0] - a) + abs(a1[1] - b))
    ans = max(ans, abs(a2[0] - a) + abs(a2[1] - b))
    ans = max(ans, abs(a3[0] - a) + abs(a3[1] - b))
    ans = max(ans, abs(a4[0] - a) + abs(a4[1] - b))


print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
import itertools

def resolve():
    N=int(input())
    X=[0]*N
    Y=[0]*N
    Max=0
    Min=10**10
    MaxI=0
    MinI=0
    for i in range(N):
        X[i],Y[i]=map(int,input().split())
        if(Max<X[i]+Y[i]):
            Max=X[i]+Y[i]
            MaxI=i
        if(Min>X[i]+Y[i]):
            Min=X[i]+Y[i]
            MinI=i
    
    print(abs(X[MaxI] - X[MinI])+abs(Y[MaxI] - Y[MinI]))


resolve()

Submission status: Wrong Answer

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


N = int(input().rstrip('\n'))
xys = []
for _ in range(N):
  x,y = (int(x) for x in input().rstrip('\n').split())
  if len(xys)==0:
    xys.append((x,y))
  elif all(a[0]>=x for a in xys) or all(a[0]<=x for a in xys):
    xys.append((x,y))
  elif all(a[1]>=y for a in xys) or all(a[1]<=y for a in xys):
    xys.append((x,y))
res = 0
for i in range(len(xys)-1):
  i1 = xys[i]
  for i2 in xys[i+1:]:
    a = abs(i1[1]-i2[1])+abs(i2[0]-i1[0])
    if a > res:
      res = a
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

x = []
y = []

"""
minX = 1100000000
minX_id = -1
maxX = 0
maxX_id = -1

minY = 1100000000
minY_id = -1
maxY = 0
maxY_id = -1
"""

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

minX = min(x)
maxX = max(x)
minY = min(y)
maxY = max(y)

minX_id = [i for i, v in enumerate(x) if v == minX]
maxX_id = [i for i, v in enumerate(x) if v == maxX]
minY_id = [i for i, v in enumerate(y) if v == minY]
maxY_id = [i for i, v in enumerate(y) if v == maxY]

"""
print(minX_id)
print(maxX_id)
print(minY_id)
print(maxY_id)
"""

cand = 0

for idx in minX_id:
    for IDX in maxX_id:

        cand = max(cand, maxX - minX + abs(y[IDX] - y[idx]))

for idy in minY_id:
    for IDY in maxY_id:

        cand = max(cand, abs(x[IDY] - x[idy]) + maxY - minY)

print(cand)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    _xmin, _xmax = float("inf"), 0
    _ymin, _ymax = float("inf"), 0
    for i in range(N):
        x, y = list(map(int, input().split()))
        _x, _y = x - y, x + y
        _xmin = min(_x, _xmin)
        _xmax = max(_x, _xmax)
        _ymin = min(_y, _ymin)
        _ymax = max(_y, _ymax)
    print(max(_xmax-_xmin, _ymax-_ymin))


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

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

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


def dist(x_1, y_1, x_2, y_2):
    return abs(x_1 - x_2) + abs(y_1 - y_2)


ans = 0

for i in range(1, N):
    tmp = dist(*x[i], *x[0])
    if tmp > ans:
        ans = tmp

x.sort(key=lambda x: x[1])

for i in range(1, N):
    tmp = dist(*x[i], *x[0])
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(sys.stdin.readline())

item_min = [None, None] # x_min, y_min
item_max = [None, None] # x_max, y_max
coord_min = [None, None] # x_minに相当する座標, y_minに相当する座標
coord_max = [None, None] # x_maxに相当する座標, y_maxに相当する座標
for _ in range(n):
    coord = list(map(int, sys.stdin.readline().split()))
    if item_min[0] is None:
        for i in range(2):
            item_min[i] = coord[i]
            item_max[i] = coord[i]
            coord_min[i] = coord
            coord_max[i] = coord
    else:
        for i in range(2):
            if coord[i] < item_min[i]:
                item_min[i] = coord[i]
                coord_min[i] = coord
            elif coord[i] > item_max[i]:
                item_max[i] = coord[i]
                coord_max[i] = coord

candidate = []
for i in range(2):
    # 最小
    for k in range(2):
        # 最大
        c_min = coord_min[i]
        c_max = coord_max[k]
        candidate.append(abs(c_max[0] - c_min[0]) + abs(c_max[1] - c_min[1]))
print(max(candidate))

Submission status: Wrong Answer

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

ans = []
B = sorted([x+y for x,y in A])
ans.append(B[-1] - B[0])

# min_y - max_x
ax = sorted(A, key=lambda a: a[0])[-1]
ay = sorted(A, key=lambda a: a[1])[0]
ans.append(abs(ax[0] - ay[0]) + abs(ax[1] - ay[1]))

print(max(ans))

Submission status: Wrong Answer

Solution code:
count = 0
count2 = 0
count3 = []
count4 = []
for _ in range(int(input())):
  x, y = list(map(int, input().split()))
  count = max(count, abs(x + y))
  count2 = max(count2, abs(x - y))
  count3.append((x + y))
  count4.append((x - y))
z = min(count3)
zz = min(count4)
print(max(count-z, count2-zz))

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))
            
print(int(max(abs(ans1+ans3), abs(ans2+ans4))))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    a,b = (map(int,input().split()))
    x.append(a+b)
ans = max(x) - min(x)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
point_sum = []
for i in range(n):
  a,b = map(int, input().split())
  point_sum.append(a+b)
print(max(point_sum) - min(point_sum))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, x: "List[int]", y: "List[int]"):
    tmp = list(map(lambda x: x[0] + x[0], zip(x, y)))
    print(abs(min(tmp) - max(tmp)))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


N = int(input().rstrip('\n'))
xys = []
for _ in range(N):
  x,y = (int(x) for x in input().rstrip('\n').split())
  if len(xys)==0:
    xys.append((x,y))
  elif all(a[0]>x for a in xys) or all(a[0]<x for a in xys):
    xys.append((x,y))
  elif all(a[1]>y for a in xys) or all(a[1]<y for a in xys):
    xys.append((x,y))
res = 0
for i in range(len(xys)-1):
  i1 = xys[i]
  for i2 in xys[i+1:]:
    a = abs(i1[1]-i2[1])+abs(i2[0]-i1[0])
    if a > res:
      res = a
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
ll = []
for _ in range(n):
    x, y = map(int, input().split())
    l.append((x+y, x, y))
    ll.append((x-y, x, y))
l.sort()
ll.sort()
ans1 = 0
ans2 = 0

cnt = 0
while True:
    a = l[-cnt]
    b = l[n-1-cnt]
    if a[1] >= b[1] and a[2] >= b[2]:
        ans1 = b[0]-a[0]
        break
    if cnt >= n-1:
        break
    cnt += 1

cnt = 0
while True:
    a = l[-cnt]
    b = l[n-1-cnt]
    if a[1] >= a[2] and b[2] >= b[1]:
        ans2 = b[0]-a[0]
        break
    if cnt >= n-1:
        break
    cnt += 1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=[map(int,input().split()) for i in range(0,N-1)]
x,y=[list(j) for j in zip(*xy)]

m=0
for k in range(0,len(x)-1):
  for l in range(k,len(y)):
  
      if abs(x[k]-x[l])+abs(y[k]-y[l])>m:
         m=abs(x[k]-x[l])+abs(y[k]-y[l])
    
print(m)

Submission status: Wrong Answer

Solution code:
import math

def dist(a,b):
  return math.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)

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):
    for j in range(1,n):
      ans.append(dist(l[i],l[j]))
  print(max(ans))

Submission status: Wrong Answer

Solution code:
import math
def dist(p1, p2):
    # return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def closest_split_pair(p_x, p_y, delta, best_pair):
    ln_x = len(p_x)  # store length - quicker
    mx_x = p_x[ln_x // 2][0]  # select midpoint on x-sorted array

    # Create a subarray of points not further than delta from midpoint on x-sorted array
    s_y = [x for x in p_y if mx_x - delta <= x[0] <= mx_x + delta]

    best = delta  # assign delta value to best
    ln_y = len(s_y)  # store length of subarray for quickness
    for i in range(ln_y - 1):
        for j in range(i+1, min(i + 5, ln_y)):    
            # We have to check only next 5 points; proof found in literature
            p, q = s_y[i], s_y[j]
            dst = dist(p, q)
            if dst > best:
                best_pair = p, q
                best = dst
    return best_pair[0], best_pair[1], best


def brute(ax):
    mi = dist(ax[0], ax[1])
    p1 = ax[0]
    p2 = ax[1]
    ln_ax = len(ax)
    if ln_ax == 2:
        return p1, p2, mi
    for i in range(ln_ax-1):
        for j in range(i + 1, ln_ax):
            if i != 0 and j != 1:
                d = dist(ax[i], ax[j])
                if d > mi:  # Update min_dist and points
                    mi = d
                    p1, p2 = ax[i], ax[j]
    return p1, p2, mi


def closest_pair(ax, ay):
    ln_ax = len(ax)  # It's quicker to assign variable
    if ln_ax <= 3:
        return brute(ax)  # A call to bruteforce comparison
    mid = ln_ax // 2  # Division without remainder, need int
    Qx = ax[:mid]  # Two-part split
    Rx = ax[mid:]

    midpoint = ax[mid][0]
    Qy = list()
    Ry = list()
    for x in ay:  # split ay into 2 arrays using midpoint
        if x[0] < midpoint:
           Qy.append(x)
        else:
           Ry.append(x)
    # Call recursively both arrays after split
    (p1, q1, mi1) = closest_pair(Qx, Qy)
    (p2, q2, mi2) = closest_pair(Rx, Ry)

    # Determine smaller distance between points of 2 arrays
    if mi1 >= mi2:
        d = mi1
        mn = (p1, q1)
    else:
        d = mi2
        mn = (p2, q2)

    # Call function to account for points on the boundary
    (p3, q3, mi3) = closest_split_pair(ax, ay, d, mn)
    # Determine smallest distance for the array
    if d >= mi3:
        return mn[0], mn[1], d
    else:
        return p3, q3, mi3


def solution(a):
    ax = sorted(a, key=lambda x: x[0])  # Presorting x-wise O(nlogn)
    ay = sorted(a, key=lambda x: (x[1], x[0]))  # Presorting y-wise then x-wise O(nlogn)
    p1, p2, mi = closest_pair(ax, ay)  # Recursive D&C function
    return mi


# Input
points = list()
n = int(input())
for i in range(n):
    points.append([int(i) for i in input().split()])

print(solution(points))

Submission status: Wrong Answer

Solution code:
N = int(input())

Xmax = 0
Ymax = 0
Xmin = 2*10**9
Ymin = 2*10**9
for i in range(N):
    x, y = map(int, input().split())
    if (x + y > Xmax):
        Xmax = x + y
    if (x + y < Xmin):
        Xmin = x + y
    if (x - y > Ymax):
        Ymax = x - y
    if (x - y < Ymin):
        Ymin = x - y

print(max(Xmax - Xmin, Ymax - Ymin))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
X = sorted(a, key=lambda x: x[0])
Y = sorted(a, key=lambda x: x[1])
dis = [0] * 6
dis[0] = abs(X[0][0] - X[n - 1][0]) + abs(X[0][1] - X[n - 1][1])
dis[1] = abs(X[0][0] - Y[n - 1][0]) + abs(X[0][1] - Y[n - 1][1])
dis[2] = abs(X[0][0] - Y[0][0]) + abs(X[0][1] - Y[0][1])
dis[3] = abs(X[n - 1][0] - Y[n - 1][0]) + abs(X[n - 1][1] - Y[n - 1][1])
dis[4] = abs(X[n - 1][0] - Y[0][0]) + abs(X[n - 1][1] - Y[0][1])
dis[5] = abs(Y[n - 1][0] - Y[0][0]) + abs(Y[n - 1][1] - Y[0][1])
print(max(dis))

Submission status: Wrong Answer

Solution code:
N,*f = map(int, open(0).read().split())
xy = [f[i*2:i*2+2] for i in range(N)]
s = [sum(z) for z in xy]
a = max(s) - min(s)
t = [abs(z[0]-z[1]) for z in xy]
b = max(t) - min(t)
print(max(a,b))

Submission status: Wrong Answer

Solution code:
import sys
N=int(sys.stdin.readline().strip())
XY=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XY.sort(key=lambda x:(x[0],x[1]) )
a1=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
XY.sort(key=lambda x:(x[1],x[0]) )
a2=abs(XY[0][0]-XY[-1][0])+abs(XY[0][1]-XY[-1][1])
print max(a1,a2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
a1=float('inf')
a2=0
a3=float('inf')
a4=0

for i in range(n):
    cnt=a[i][0]+a[i][1]
    cnt1=a[i][0]-a[i][1]
    a1=min(a1,cnt)
    a2=max(a2,cnt)
    a3=min(cnt1,a3)
    a4=max(cnt1,a4)


print(max(a2-a1,a4-a3))

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 = sum(xl)/n-1e-6, sum(yl)/n-1e-6
"""
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
"""
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))
            
print(int(max(abs(ans1+ans3), abs(ans2+ans4))))

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 i in range(2,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)
print(nowManhattan)

Submission status: Wrong Answer

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


N = int(input().rstrip('\n'))
xys = []
for _ in range(N):
  x,y = (int(x) for x in input().rstrip('\n').split())
  if len(xys)==0:
    xys.append((x,y))
  elif all(a[0]>x for a in xys) or all(a[0]<x for a in xys):
    xys.append((x,y))
  elif all(a[1]>y for a in xys) or all(a[1]>y for a in xys):
    xys.append((x,y))
res = 0
for i in range(len(xys)-1):
  i1 = xys[i]
  for i2 in xys[i+1:]:
    a = abs(i1[1]-i2[1])+abs(i2[0]-i1[0])
    if a > res:
      res = a
print(res)

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
for x, y in zip(X, Y):
    if chebyshev_0(x, y) > max_0:
        max_0 = chebyshev_0(x, y) 
min_0 = max_0
for x, y in zip(X, Y):
    if chebyshev_0(x, y) < min_0:
        min_0 = chebyshev_0(x, y) 
l0 = max_0 - min_0

max_1 = 0
for x, y in zip(X, Y):
    if chebyshev_1(x, y) > max_1:
        max_1 = chebyshev_1(x, y) 
min_1 = max_1
for x, y in zip(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())
xys = []
for _ in range(n):
    x, y = input().split(" ")
    xys.append([int(x), int(y)])


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


p_a = xys[0]
p_b = xys[1]
for _ in range(5):
    for p_c in xys:
        d_a_b = m(p_a, p_b)
        d_a_c = m(p_a, p_c)
        d_b_c = m(p_b, p_c)

        if d_a_b > max(d_a_c, d_b_c):
            pass
        else:
            if d_a_c > d_b_c:
                p_b = p_c
            else:
                p_a = p_c
print(m(p_a, p_b))

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(N):
  x, y = map(int, input().split())
  if i==0:
    x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6 = x, y, x, y, x, y, x, y, x, y, x, y
    tmax, tmin = x+y, x+y
  else:
    if x<x1 and y<y1:
      x1, y1 = x, y
    elif x<x2 and y>y2:
      x2, y2 = x, y
    elif x>x3 and y>y3:
      x3, y3 = x, y
    elif x>x4 and y<y4:
      x4, y4 = x, y
    elif x+y < tmin:
      x5, y5 = x, y
      tmin = x + y
    elif x+y > tmax:
      x6, y6 = x, y
      tmax = x + y
print(max(abs(x1-x3)+abs(y1-y3),abs(x2-x4)+abs(y2-y4),abs(x5-x6)+abs(y5-y6)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
from itertools import accumulate
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def floor(a, b): return -(-a // b)


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


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


def C(line): return [sys.stdin.readline() for _ in range(line)]


N = z()
X, Y = [], []
dist = [0]*(N)  # 原点からの距離
for i in range(N):
    x, y = zz()
    dist[i] = (x+y)

    X.append(x)
    Y.append(y)
dist = sorted(dist)
print(dist[-1] - dist[0])

Submission status: Wrong Answer

Solution code:
count = 0
count2 = 0
count3 = []
count4 = []
for _ in range(int(input())):
  x, y = list(map(int, input().split()))
  count = max(count, abs(x + y))
  count2 = max(count2, abs(x - y))
  count3.append(abs(x + y))
  count4.append(abs(x - y))
z = min(count3)
zz = min(count4)
print(max(count-z, count2-zz))

Submission status: Wrong Answer

Solution code:
N=int(input())
migisita=[0,10^9+1]
migiue=[0,0]
hidarisita=[10^9+1,10^9+1]
hidariue=[10^9+1,0]
for i in range(0,N):
    a,b=list(map(int,input().split()))
    if migiue[0]<a and migiue[1]<b:
        migiue=[a,b]
    if migisita[0]<a and migisita[1]>b:
        migisita=[a,b]
    if hidariue[0]>a and hidariue[1]<b:
        hidariue=[a,b]
    if hidarisita[0]>a and hidarisita[1]>b:
        hidarisita=[a,b]

one=abs(migiue[0]-hidarisita[0])+abs(migiue[1]-hidarisita[1])
two=abs(hidariue[0]-migisita[0])+abs(hidariue[1]-hidarisita[1])
three=abs(migiue[0]-migisita[0])+abs(migiue[1]-migisita[1])
four=abs(hidariue[0]-hidarisita[0])+abs(hidariue[1]-hidarisita[1])
print(max(one,two,three,four))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans_max = 0
ans_min = 2*10**9+1

for i in range(N):
    ans_min = min(ans_min, x_list[i] + y_list[i])
    ans_max = max(ans_max, x_list[i] + y_list[i])

ans = ans_max - ans_min
print(ans)