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,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:
    XY01 = abs(XY0[0]-XY1[0])+abs(XY0[1]-XY1[1])
except:
    XY01=0
    
try:
    XY02 = abs(XY0[0]-XY2[0])+abs(XY0[1]-XY2[1])
except:
    XY02=0
try:
    XY03 = abs(XY0[0]-XY3[0])+abs(XY0[1]-XY3[1])
except:
    XY03=0
try:
    XY12 = abs(XY1[0]-XY2[0])+abs(XY1[1]-XY2[1])
except:
    XY12 = 0
try:
    XY13 = abs(XY1[0]-XY3[0])+abs(XY1[1]-XY3[1])
except:
    XY13 = 0
try:
    XY23 = abs(XY2[0]-XY3[0])+abs(XY2[1]-XY3[1])
except:
    XY23 = 0
print(max([XY01,XY02,XY03,XY12,XY13,XY23]))

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 (x,y) not in xys:
    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:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

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

N = I()
x1, y1 = I()
x2, y2 = I()

x = D(list)
y = D(list)

x[x1].append((x1, y1))
y[y1].append((x1, y1))
x[x2].append((x2, y2))
y[y2].append((x2, y2))

for _ in range(2, N):
    x3, y3 = I()
    x[x3].append((x3, y3))
    y[y3].append((x3, y3))


right = max(x.keys())
left = min(x.keys())
top = max(y.keys())
bottom = min(y.keys())

tops = y[top]
lefts = x[left]
rights = x[right]
bottoms = y[bottom]

extremes = tops + lefts + rights + bottoms

ans = 0
for test in [tops, lefts, rights, bottoms]:
    for p1 in test:
        for p2 in extremes:
            m = manhattan(p1[0], p1[1], p2[0], p2[1])
            if m > ans:
                ans = m

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list()
for i in range(n):
  x,y=map(int,input().split())
  l.append((x,y))

minx = sorted(l, key=lambda x: x[0])
maxx = sorted(l, key=lambda x: x[0], reverse=True)
miny = sorted(l, key=lambda x: x[1])
maxy = sorted(l, key=lambda x: x[1], reverse=True)

ans=0
c=0
for imaxx in maxx:
  for iminx in minx:
    dist=(abs(imaxx[0]-iminx[0]) + abs(imaxx[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==5:
      c=0
      break

  else:
    continue
  break

for imaxx in maxx:
  for iminy in miny:
    dist=(abs(imaxx[0]-iminy[0]) + abs(imaxx[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==5:
      c=0
      break

  else:
    continue
  break

for imaxy in maxy:
  for iminy in miny:
    dist=(abs(imaxy[0]-iminy[0]) + abs(imaxy[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==5:
      c=0
      break

  else:
    continue
  break


for imaxy in maxy:
  for iminx in minx:
    dist=(abs(imaxy[0]-iminx[0]) + abs(imaxy[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==5:
      c=0
      break

  else:
    continue
  break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

xg = sum([p[0] for p in ps]) / len(ps)
yg = sum([p[1] for p in ps]) / len(ps)

maxd = 0
maxp = ps[0]
for p in ps:
    d = abs(xg - p[0]) + abs(yg - 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())
i = 0
x = [0]
y = [0]
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)
    ma = max(x[i+1]*y[i+1], x[i]*y[i])
    mi = min(x[i+1]*y[i+1], x[i]*y[i])
    if ma == x[i+1]*y[i+1]:
        cma = i
    if mi == x[i+1]*y[i+1]:
        cmi = i
    i += 1
print(abs(x[cma] - x[cmi]) + abs(y[cma] - y[cmi]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def main():
    N = int(input())

    max_x = (float("-inf"), 0)
    min_x = (float("inf"), 0)

    max_y = (0, float("-inf"))
    min_y = (0, float("inf"))

    max_xy = (float("-inf"), 0)
    min_xy = (float("inf"), 0)

    max_yx = (0, float("-inf"))
    min_yx = (0, float("inf"))

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

        if x > max_x[0]:
            max_x = (x, y)
        if x < min_x[0]:
            min_x = (x, y)
        if y > max_y[1]:
            max_y = (x, y)
        if y < min_y[1]:
            min_y = (x, y)
        if x - y > max_xy[0] - max_xy[1]:
            max_xy = (x, y)
        if x - y < min_xy[0] - min_xy[1]:
            min_xy = (x, y)
        if y - x > max_yx[1] - max_yx[0]:
            max_yx = (x, y)
        if y - x < min_yx[1] - min_yx[0]:
            min_yx = (x, y)

    ans = 0
    for a, b in combinations(
        (max_x, min_x, max_y, min_y, max_xy, min_xy, max_yx, min_yx), 2):
        ans = max(ans, abs(a[0] - b[0]) + abs(a[1] - b[1]))

    print(ans)


main()

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])
print(max(d1, d2, d3, d4))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n)]

a = 10**9+5
b = 0
c = 10**9+5
d = 0

for i in range(n):
    a = min(a, C[i][0]+C[i][1])
    b = max(b, C[i][0]+C[i][1])
    c = min(c, C[i][0]-C[i][1])
    d = max(d, C[i][0]-C[i][1])

print(max(b-a,d-c))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import 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 = -10**10
ymin = xmin = 10**10
xmax_i = ymax_i = 0
xmin_i = ymin_i = 1

X = []
for i in range(N):
    x, y = acinput()
    X.append([x, y])
    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]
res = 0

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

for i in range(3):
    for j in range(i+1, 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:
N = int(input())
z = []
for _ in range(N):
  x, y = list(map(int, input().split()))
  z.append([x, y])

z.sort()
mdct = 0
lx, ly = z[0]
rx, ry = z[N-1]
z.sort(key=lambda x: x[1])
sx, sy = z[0]
ux, uy = z[N-1]
for xa, ya in [[lx, ly], [rx, ry]]:
  for xb, yb in [[sx, sy], [ux, uy]]:
    mdct = max(mdct, abs(xa - xb) + abs(ya - yb))

print(mdct)

Submission status: Wrong Answer

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

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

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

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

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


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

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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))
print(res)

Submission status: Wrong Answer

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

sumxy = [x+y for x,y in zip(X,Y)]
maxidx = sumxy.index(max(sumxy))
minidx = sumxy.index(min(sumxy))

ans = abs(X[maxidx] - X[minidx]) + abs(Y[maxidx] - Y[minidx])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[input().split() for _ in range(n)]
dp=[0]*n*2
dp1=[0]*n*2
for i in range(n):
    for j in range(1,n):
        dp[i+j] = max(abs(int(l[i][0]) - int(l[j][0])), dp[i+j-1])
        dp1[i+j] = max(abs(int(l[i][1]) - int(l[j][1])), dp[i+j-1])
dp=sorted(dp)
dp1=sorted(dp1)
print(int(dp[-1])+int(dp1[-1]))

Submission status: Wrong Answer

Solution code:
from sys import stdin

readline = stdin.readline

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

xy = list(set(xy))

xy.sort()

c = set(xy[:1000])
c = c | set(xy[-1000:])

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

c = c | set(xy[:1000])
c = c | set(xy[-1000:])

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

c = c | set(xy[:1000])
c = c | set(xy[-1000:])

c = list(c)
result = 0
for i in range(len(c)):
    for j in range(i + 1, len(c)):
        result = max(result, abs(c[i][0] - c[j][0]) + abs(c[i][1] - c[j][1]))
print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
XY = list(tuple(int(x) for x in input().split()) for _ in range(n))

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

x0, y0 = XY[0]
x1, y1 = XY[0]
x2, y2 = XY[0]
mdist = -1
for x, y in XY:
    if dist((x, y), (x0, y0)) > mdist:
        mdist = dist((x, y), (x0, y0))
        x1, y1 = x, y
for x, y in XY:
    if dist((x, y), (x1, y1)) > mdist:
        mdist = dist((x, y), (x1, y1))
        x2, y2 = x, y

print(dist((x1, y1), (x2, y2)))

Submission status: Wrong Answer

Solution code:
#create date: 2020-09-13 22:30

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    amax = 0
    amin = 10**20
    for _ in range(n):
        x, y = na()
        amin = min(amin, x+y)
        amax = max(amax, x+y)
    print(amax-amin)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list()
for i in range(n):
  x,y=map(int,input().split())
  l.append((x,y))

minx = sorted(l, key=lambda x: x[0])
maxx = sorted(l, key=lambda x: x[0], reverse=True)
miny = sorted(l, key=lambda x: x[1])
maxy = sorted(l, key=lambda x: x[1], reverse=True)

ans=0
c=0
for imaxx in maxx:
  for iminx in minx:
    dist=(abs(imaxx[0]-iminx[0]) + abs(imaxx[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==2:
      c=0
      break

  else:
    continue
  break

for imaxx in maxx:
  for iminy in miny:
    dist=(abs(imaxx[0]-iminy[0]) + abs(imaxx[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==2:
      c=0
      break

  else:
    continue
  break

for imaxy in maxy:
  for iminy in miny:
    dist=(abs(imaxy[0]-iminy[0]) + abs(imaxy[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==2:
      c=0
      break

  else:
    continue
  break


for imaxy in maxy:
  for iminx in minx:
    dist=(abs(imaxy[0]-iminx[0]) + abs(imaxy[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==2:
      c=0
      break

  else:
    continue
  break

print(ans)

Submission status: Wrong Answer

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

ax = 0
ay = 0

bx = float('inf')
by = float('inf')

def a(x, y):
  return abs(x) + abs(y)

for x, y in SS:
  if a(x, y) < a(bx, by):
    bx = x
    by = y
  if a(x, y) > a(ax, ay):
    ax = x
    ay = y


print(abs(bx - ax) + abs(by - ay))

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 x, y in Maxx:
        for xx,yy in place:
            ans = max(ans,abs(x-xx)+abs(y-yy))
    for x, y in Minx:
        for xx,yy in place:
            ans = max(ans,abs(x-xx)+abs(y-yy))
    for x, y in Maxy:
        for xx,yy in place:
            ans = max(ans,abs(x-xx)+abs(y-yy))
    for x, y in Miny:
        for xx,yy in place:
            ans = max(ans,abs(x-xx)+abs(y-yy))
    
    print(ans)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    XY[i][0], XY[i][1] = XY[i][0]-XY[i][1], XY[i][0]+XY[i][1]

ans = 0
for i in range(2):
    tmp_1 = 0
    tmp_2 = float("inf")
    for j in range(N):
        tmp_1 = max(tmp_1, XY[j][i])
        tmp_2 = min(tmp_2, XY[j][i])
    ans = max(ans, tmp_1-tmp_2)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for i in range(n):
    x = list(map(int, input().split()))
    s.append(x)
t = sorted(s)
u = sorted(s, key=lambda x: x[1])
res = 0

for X in [t[0], u[0], t[-1], u[-1]]:
    for Y in [t[n // 2], u[n // 2]]:
        tmp = abs(X[0] - Y[0]) + abs(X[1] - Y[1])
        res = max(res, tmp)
print(res)

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	p = []
	for i in range(N):
		x, y = [int(a) for a in input().split(" ")]
		p.append({"x" : x, "y" : y})
	aveX = 0
	aveY = 0
	for i in range(N):
		aveX += p[i]["x"]
		aveY += p[i]["y"]
	aveX /= N
	aveY /= N
	for i in range(N):
		p[i]["d"] = abs(aveX - p[i]["x"]) + abs(aveY - p[i]["y"])
	p.sort(key=lambda z: z["d"])
	D = []
	P = [p[-1]]
	k = 1
	while k < min([len(p), 20]) and abs(p[-k-1]["d"] - P[0]["d"]) < 4:
		P.append(p[-k-1])
		k += 1
	for i in range(N):
		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=[tuple(map(int,input().split())) for _ in range(N)]
t=[]
for x,y in xy:
    t.append((x*y,x,y))
t=sorted(t)
xy1=t[0]
xy2=t[-1]
ans=abs(xy1[1]-xy2[1])+abs(xy1[2]-xy2[2])

t=sorted(t,key=lambda x:x[1])
xy1=t[0]
xy2=t[-1]
ans=max(ans,abs(xy1[1]-xy2[1])+abs(xy1[2]-xy2[2]))

t=sorted(t,key=lambda x:x[2])
xy1=t[0]
xy2=t[-1]
ans=max(ans,abs(xy1[1]-xy2[1])+abs(xy1[2]-xy2[2]))

print(ans)

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)
ans=max(ans11,ans22,ans33,ans44)



sort_x_numbers=sorted(x_numbers,reverse=True)
sort_y_numbers=sorted(y_numbers,reverse=True)
ans1=[]
ans2=[]
ans3=[]
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]))
ans22=max(ans2)
print(max(ans,ans11,ans22,ans33))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

# xとyの最小と最大を求めることで、一致すると、基準となり得る
# XとYを足せば良い
# 最大値は関係ない
# Xmax+Ymax-|Xmin|-|Ymin|
# 何かの数字を利用して候補を減らす


# XmaxとXmin, YmaxとYmin, (X+Y)max, (X+Y)minの４点を調べる
# XmaxとXmin, YmaxとYminの４点で最大と最小を求める

def manhattan(p1, p2):
    return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])
n4 = []
n4.append(pos[np.argmax(x)])
n4.append(pos[np.argmax(y)])
n4.append(pos[np.argmin(x)])
n4.append(pos[np.argmin(y)])

# 上記４点間でmanhattan最大値を求める
d = []
for i in range(4):
    for j in range(i+1, 3):
        d.append(manhattan(n4[i], n4[j]))
print(max(d))

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] #右下

a5 = [a,b]
a6 = [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]

    if(a+b < a5[0]+a5[1]):
        a5 = [a,b]

    if(a+b > a6[0]+a6[1]):
        a6 = [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))
    ans = max(ans, abs(a5[0] - a) + abs(a5[1] - b))
    ans = max(ans, abs(a6[0] - a) + abs(a6[1] - b))

print(ans)

Submission status: Wrong Answer

Solution code:
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 > (hw[i][0] + hw[i][1])):
        minD = hw[i][0] + hw[i][1]
        min = i
    if (maxD < hw[i][0] + hw[i][1]):
        maxD = hw[i][0] + hw[i][1]
        max = i

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

Submission status: Wrong Answer

Solution code:
import os
import heapq

import sys
import bisect
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase
from functools import reduce


def convex_hull_graham(coordinates):
    def change(a, b, c):
        return ((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) < 0

    def left(h, r):
        while len(h) > 1 and change(h[-2], h[-1], r):
            h.pop()
        h.append(r)
        return h

    coordinates.sort()
    lower = reduce(left, coordinates, [])
    upper = reduce(left, reversed(coordinates), [])


    return lower.extend(upper[1:len(upper) - 1]) or lower
def d(one,t):
    return abs(one[0]-t[0])+abs(one[1]-t[1])
def find_max_dist_graham_c1(L):
    H = convex_hull_graham(L)  # Get ordered list of convex hull points

    H.sort()
    max_dist = d(H[0], H[1])  # Get a fist idea what the longest distance might be

    i = 0
    p1 = H[i]  # Grab a random point
    loop_max_dist = 0
    for j in range(1, len(H)):
        curr_dist = d(H[i], H[j])
        if curr_dist < loop_max_dist:
            break
        loop_max_dist = curr_dist
        max_dist = max(loop_max_dist, max_dist)
    # Every diagonal that is longer than the best one found with L[0]
    # has to have points in both of the following two sets (correct?):
    # [1...j] and [j+1...len(L)]

    # Try to find a neighboring diagonal that is longer.
    change = True
    while change:
        change = False
        if i-1<0 and j+1<len(H) and  d(H[i-1], H[j+1]) > max_dist:
            max_dist = d(H[i-1], H[j+1])
            i -= 1
            j += 1
            change = True
        elif i+1<len(H) and j-1>0 and d(H[i+1], H[j-1]) > max_dist:
            max_dist = d(H[i+1], H[j-1])
            i += 1
            j -= 1
            change = True
    return max_dist

def main():
    n=int(input())
    arr = []
    for i in range(n):
        x, y = map(int, input().split())
        arr.append([x, y])
    print(find_max_dist_graham_c1(arr))
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(abs(xy[i][0])+abs(xy[i][1]))
d = abs(xy[l.index(max(l))][0]-xy[l.index(min(l))][0])+abs(xy[l.index(max(l))][1]-xy[l.index(min(l))][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), 20]) and abs(p[-k-1]["d"] - P[0]["d"]) < 4:
		P.append(p[-k-1])
		k += 1
	for i in range(N - 1):
		for j in range(len(P)):
			D.append(abs(P[j]["x"] - p[i]["x"]) + abs(P[j]["y"] - p[i]["y"]))
	print(max(D))

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
tab = []
rtab = []
for i in range(n):
	a, b = map(int, input().split())
	tab.append([a, b])
	rtab.append([b, a])
tab.sort()
rtab.sort()
m = 0

j = n - 1
for i in range(n):
	m = max(m, abs(tab[i][0] - tab[j][0]) + abs(tab[i][1] - tab[j][1]))
	m = max(m, abs(rtab[i][0] - rtab[j][0]) + abs(rtab[i][1] - rtab[j][1]))
	j -= 1

print(m)

Submission status: Wrong Answer

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

def s(points, k, l):
    np = list(map(lambda arg:  k*arg[0] + l*arg[0], points))
    return abs(max(np)-min(np))

def solve(N: int, x: "List[int]", y: "List[int]"):
    points = list(zip(x, y))
    print(max([
            s(points, +1, +1),
            s(points, -1, -1),
            s(points, +1, -1),            
            s(points, -1, +1),            
    ]))
    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:
n = int(input())
xy = [list(map(int, input().split())) for _i in range(n)]

x = [[i+j, i, j] for i, j in xy]
x.sort()
r = []
r.append(abs(x[0][1]-x[-1][1])+abs(x[1][2]-x[-1][2]))
x = [[i-j, i, -j] for i, j in xy]
x.sort()
r.append(abs(x[0][1]-x[-1][1])+abs(x[1][2]-x[-1][2]))
x = [[-i+j, -i, j] for i, j in xy]
x.sort()
r.append(abs(x[0][1]-x[-1][1])+abs(x[1][2]-x[-1][2]))

x = [[-i-j, -i, -j] for i, j in xy]
r.append(abs(x[0][1]-x[-1][1])+abs(x[1][2]-x[-1][2]))

print(max(r))

Submission status: Wrong Answer

Solution code:
N = int(input())
ma = 0
mi = 10**18

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

for i in range(N):
    ma=max(ma,xy[i][0]+xy[i][1])
    mi=min(mi,xy[i][0]+xy[i][1])
print(ma-mi)

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), 5]) and abs(p[-k-1]["d"] - P[0]["d"]) < 4:
		P.append(p[-k-1])
		k += 1
	for i in range(N - 1):
		for j in range(len(P)):
			D.append(abs(P[j]["x"] - p[i]["x"]) + abs(P[j]["y"] - p[i]["y"]))
	print(max(D))

main()

Submission status: Wrong Answer

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

N = int(input())

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

for i in range(N):
    xy[i].append(sum(xy[i]))

xy.sort(key=lambda x: x[2])

x, y, tmp = xy[0]
ans = 0

for i in range(1, N):
    ans = max(ans, abs(x - xy[i][0]) + abs(y - xy[i][1]))

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_diff = 10**9
max_diff = 1
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

cand_set = set()
for x,y in XY:
    if x-y in (min_diff, max_diff) 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:
N = int(input())
min_dist_o = 10**10
max_dist_o = 0
min_dist_edge = 10**10
max_dist_edge = 0
for i in range(N):
    x,y = map(int,input().split())
    dist_o = x+y
    dist_edge = 10**9+1-x+y
    if dist_o > max_dist_o:
        max_dist_o=dist_o
    if dist_o < min_dist_o:
        min_dist_o=dist_o
    if dist_edge > max_dist_edge:
        max_dist_edge=dist_edge
    if dist_o < min_dist_o:
        min_dist_edge=dist_edge
print(max(max_dist_o-min_dist_o,max_dist_edge-min_dist_edge))