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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    fx, fy = mat[0]
    cur = 0
    idx = -1

    for i in range(1, N):
        sx, sy = mat[i]
        score = abs(fx - sx) + abs(fy - sy)
        if score > cur:
            idx = i
            cur = score

    ans = 0
    fx, fy = mat[idx]

    for i in range(N):
        sx, sy = mat[i]
        score = abs(fx - sx) + abs(fy - sy)
        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import random

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

S = set()
for i in range(N):
  S.add((x[i], y[i]))
S = list(S)

ans = 0
for i in range(8):
  o = random.randint(0, len(S)-1)
  m = 0
  mp = 0
  for i in range(N):
    d = abs(x[i]-S[o][0])+abs(y[i]-S[o][1])
    if d>m:
      m = d
      mp = i
  for i in range(N):
    ans = max(ans, abs(x[i]-x[mp])+abs(y[i]-y[mp]))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
point_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    point_dict[(x, y)] = x + y
print(max(point_dict.values()) - min(point_dict.values()))

Submission status: Wrong Answer

Solution code:
def f(n, m):
  return(abs(n[0]-m[0]) + abs(n[1]-m[1]))

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

XY.sort(key=lambda i: i[0])
p1 = XY[0]
p2 = XY[-1]
XY.sort(key=lambda i: i[1])
p3 = XY[0]
p4 = XY[-1]

ans = max(f(p1,p2),f(p1,p3),f(p1,p4),f(p2,p3),f(p2,p4),f(p3,p4))
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
xy = [tuple(map(int, input().split())) for i in range(n)]
xy.sort()
a = xy[0]
xy.sort(key=lambda x: -x[0])
b = xy[0]
xy.sort(key=lambda x: x[1])
c = xy[0]
xy.sort(key=lambda x: -x[1])
d = xy[0]

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

ans = 0
ans = max(ans, man(a, b))
ans = max(ans, man(a, c))
ans = max(ans, man(a, d))
ans = max(ans, man(b, c))
ans = max(ans, man(b, d))
ans = max(ans, man(d, d))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst, result = [], []

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

for i in range(n - 1):
    a = lst[i][0] - lst[i + 1][0]
    b = lst[i][1] - lst[i + 1][1]
    result.append(abs(a) + abs(b))

print(max(result))

Submission status: Wrong Answer

Solution code:
import functools
def d(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
def convex_hull_graham(points):
    '''
    Returns points on convex hull in CCW order according to Graham's scan algorithm. 
    By Tom Switzer <thomas.switzer@gmail.com>.
    '''
    TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

    def cmp(a, b):
        return (a > b) - (a < b)

    def turn(p, q, r):
        return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)

    def _keep_left(hull, r):
        while len(hull) > 1 and turn(hull[-2], hull[-1], r) != TURN_LEFT:
            hull.pop()
        if not len(hull) or hull[-1] != r:
            hull.append(r)
        return hull

    points = sorted(points)
    l = functools.reduce(_keep_left, points, [])
    u = functools.reduce(_keep_left, reversed(points), [])
    return l.extend(u[i] for i in range(1, len(u) - 1)) or l
def find_max_dist_graham_c1(L):
    H = convex_hull_graham(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])  # Get a fist idea what the longest distance might be

    i = 0
    p1 = L[i]  # Grab a random point
    loop_max_dist = 0
    for j in range(1, len(L)):
        curr_dist = d(L[i], L[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 j + 1 < len(L) and i - 1 >= 0 and d(L[i-1], L[j+1]) > max_dist:
            max_dist = d(L[i-1], L[j+1])
            i -= 1
            j += 1
            change = True
        elif i + 1 < len(L) and j - 1 >= 0 and d(L[i+1], L[j-1]) > max_dist:
            max_dist = d(L[i+1], L[j-1])
            i += 1
            j -= 1
            change = True
    return max_dist
t = int(input())
#print(t)
L = []
while t > 0:
    t -= 1
    a = input()
    a = a.split(" ")
    a = list(map(int, a))
    L.append(a)
print(find_max_dist_graham_c1(L))

Submission status: Wrong Answer

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

X=[]
for i in range(N):
    X.append(x[i][0]+x[i][1])
X.sort()
print(X[-1]-X[0])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
lan=[]
for i in range(n):
  ll=list(map(int,input().split()))
  l.append(ll)
  ll1=[ll[1],ll[0]]
  lan.append(ll1)

l.sort()
lan.sort()
we=abs(l[0][0]-l[-1][0])+abs(l[0][1]-l[-1][1])
we1=abs(lan[0][0]-lan[-1][0])+abs(lan[0][1]-lan[-1][1])
print(max(we,we1))

Submission status: Wrong Answer

Solution code:
import sys
import random

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

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

max_iter = 100

fmax_dist = -2
max_dist = -1

final_out = 0
for tryi in range(10):
    jibun = random.randint(0, n-1)
    #for iter_i in range(max_iter):
    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

        jibun = next_jibun 
        fmax_dist = max_dist
    final_out = max(final_out, out)
    
    
print(out)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())

AM, Am, BM, Bm = 0, 10**18, 0, 10**18
for _ in range(N):
    x, y = map(int, input().split())
    AM = max(AM, x+y)
    Am = min(Am, x+y)
    BM = max(BM, x-y)
    Bm = min(Bm, x-y)


print(max(AM-Am, BM-Bm))

Submission status: Wrong Answer

Solution code:
N = int(input())
x,y = map(int,input().split(" "))
papb = [x,y]
pamb = [x,y]
mapb = [x,y]
mamb = [x,y]
for i in range(N - 1):
    x,y = map(int,input().split(" "))
    if x + y > papb[0] + papb[1]:papb = [x,y]
    if x - y > pamb[0] + pamb[1]:pamb = [x,y]
    if 0 - x + y > mapb[0] + mapb[1]:mapb = [x,y]
    if 0 - x - y > mamb[0] + mamb[1]:papb = [x,y]
print(max(abs(papb[0] - mamb[0]) + abs(papb[1] - mamb[1]),abs(pamb[0] - mapb[0]) + abs(pamb[1] - mapb[1])))

Submission status: Wrong Answer

Solution code:
import sys
import math
#from queue import *
#import random
#sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline
 
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input()))
def inara():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
################################################################
############ ---- THE ACTUAL CODE STARTS BELOW ---- ############

n=inp()

ara=[]

for i in range(n):
	x,y=invr()
	ara.append([x,y])
	

minXY=ara[0][0]+ara[0][1]
maxXY=ara[0][0]+ara[0][1]

for i in range(n):
	minXY=min(minXY,ara[i][0]+ara[i][1])
	maxXY=max(maxXY,ara[i][0]+ara[i][1])

ans=minXY-maxXY
if ans<0:
	ans=-ans

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

dists = []
while N:
    x, y = map(int, input().split())
    dists.append((x, y, x+y))
    N -= 1

dists.sort(key=lambda x: x[2])
print(abs(dists[0][0] - dists[-1][0] + dists[0][1] - dists[-1][1]))

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
xy = [LI() for _ in range(n)]
lst = [x+y for x, y in xy]
lst.sort(reverse=True)
print(lst[0] - lst[-1])

Submission status: Wrong Answer

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

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

n = int(input())
point = []
u = []
for i in range(n):
    a,b = mp()
    point.append((a,b))
    u.append(a+b)
print(max(u)-min(u))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

inf = 10**15
axis_p_max = -1 * inf
axis_p_min = inf
axis_m_max = -1 * inf
axis_m_min = inf

it = iter(data)
for x,y in zip(it,it):
    axis_p_max = max(axis_p_max, x+y)
    axis_p_min = min(axis_p_min, x+y)
    axis_m_max = max(axis_m_max, x-y)
    axis_m_min = min(axis_m_max, x-y)

ans = max(axis_p_max-axis_p_min, axis_m_max,axis_m_min)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

ma = -float("inf")
mi = float("inf")
for i in range(N):
    x,y = list(map(int,input().split()))
    ma = max(ma,x+y)
    mi = min(mi,x+y)
print(ma-mi)

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]))
ax = abs(x[0][0]-x[-1][0])+abs(x[0][1]-x[-1][1])
ay = abs(y[0][0]-y[-1][0])+abs(y[0][1]-y[-1][1])
print(max(ax,ay))

Submission status: Wrong Answer

Solution code:
N = int(input())
xs = []
ys = []
for _ in range(N):
    x,y = map(int,input().split())
    xs.append(x)
    ys.append(y)
fxys = []
for i in range(N):
    x = xs[i]
    y = ys[i]
    fxys.append((x-y, x+y))
m = 0
for d in [0, 1]:
    mx = 0
    mi = float("inf")
    for i in range(N):
        mx = max(fxys[i][d], mx)
    for i in range(N):
        mi = min(fxys[i][d], mi)
    m = max(mx-mi, m)
print(m)

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
points = set()
for _ in xrange(n):
    x,y = (int(x) for x in input().split())
    points.add((x,y))

if len(points) <= 1:
    print(0)
else:
    srt = sorted(points, key=lambda x: x[0] + x[1])
    print(max(srt[0] + srt[-1]))

Submission status: Wrong Answer

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


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


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


n = ii()

xmin = (1e9, 0)
xmax = (-1e9, 0)
ymin = (0, 1e9)
ymax = (0, -1e9)

for _ in range(n):
    x, y = mi()

    if xmin[0] > x:
        xmin = (x, y)
    if xmax[0] < x:
        xmax = (x, y)
    if ymin[1] > y:
        ymin = (x, y)
    if ymax[1] < y:
        ymax = (x, y)


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


print(max(
    d(xmin, xmax),
    d(xmin, ymin),
    d(xmin, ymax),
    d(xmax, ymin),
    d(xmax, ymax),
    d(ymin, ymax),
))

Submission status: Wrong Answer

Solution code:
def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

n = int(input())
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort()
ans = dist(P[0], P[1])
P.sort(key=lambda p: (p[0], -p[1]))
ans = max(ans, dist(P[0], P[-1]))
P.sort(key=lambda p: (p[1], p[0]))
ans = max(ans, dist(P[0], P[-1]))
P.sort(key=lambda p: (p[1], -p[0]))
ans = max(ans, dist(P[0], P[-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random

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

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

max_iter = 100

fmax_dist = -2
max_dist = -1

final_out = 0
for tryi in range(4):
    jibun = random.randint(0, n-1)
    #for iter_i in range(max_iter):
    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

        jibun = next_jibun 
        fmax_dist = max_dist
    final_out = max(final_out, out)
    
    
print(out)

Submission status: Wrong Answer

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N = int(input())
    R = [tuple(map(int, input().split())) for i in range(N)]
    A = sorted(R, key = lambda x: x[0] + x[1])
    print(abs(A[-1][0] - A[0][0]) + abs(A[-1][1] - A[0][1]))
    
    
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=set()
for _ in range(n):
    x,y=map(int,input().split())
    l.add(x+y)
l=list(l)
print(l[len(l)-1]-l[0])

Submission status: Wrong Answer

Solution code:
n = int(input())

a, b = map(int, input().split())
mini = a+b
maxi = a+b

for i in range(n-1):
    a, b = map(int, input().split())
    
    mini = min(a+b, mini)
    maxi = max(a+b, maxi)
    
print(abs(maxi-mini))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n = int(readline())

p = [list(map(int,readline().split())) for i in range(n)]

xmin = INF
ymin = INF

for (x,y) in p:
    xmin = min(x,xmin)
    ymin = min(y,ymin)

for i in range(n):
    p[i][0] -= xmin
    p[i][1] -= ymin

dmax = -INF
dmin = INF

for (x,y) in p:
    dmax = max(dmax, x+y)
    dmin = min(dmin, x+y)

print(dmax-dmin)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MAX_P = 0
MIN_P = 10 ** 10
MAX_M = 0
MIN_M = 10 ** 10

for x, y in XY:
    P = x + y
    M = x - y

    MAX_P = max(MAX_P, P)
    MIN_P = min(MIN_P, P)

    MAX_M = max(MAX_M, M)
    MIN_M = min(MIN_M, M)

ans = max(MAX_P - MIN_P, MAX_M - MIN_M)

print(ans)

Submission status: Wrong Answer

Solution code:
# by the authority of GOD
import os,sys
from io import BytesIO, IOBase
def maxAbsValExpr( x, y):
    res, n = 0, len(x)
    for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
        smallest = p * x[0] + q * y[0] + 0
        for i in range(n):
            cur = p * x[i] + q * y[i] + i
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res
def main():
    x=[]
    y=[]
    for i in range(int(input())):

        a,b =map(int,input().split())
        x.append(a)
        y.append(b)
    print(maxAbsValExpr(x,y)-1)
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
flush = lambda: sys.stdout.flush()


# ===CODE===
def main():
    max_num = -INF
    min_num = INF

    n = ni()
    for _ in range(n):
        x, y = ns()
        max_num = max(max_num, x + y)
        min_num = min(min_num, x + y)

    ans = max_num - min_num
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [0] * n
for i in range(n):
    x, y = [int(i) for i in input().split()]
    d[i] = x + y
print(max(d) - min(d))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
for i, v in enumerate(p):
    x, y = v
    p[i] = x-y, x+y

xm, ym = 0, 0
xw, yw = 10**9, 10**9
for x, y in p:
    xm = max(xm, x)
    xw = min(xw, x)
    ym = max(ym, y)
    yw = min(yw, y)

ans = max(abs(xm - xw), abs(ym - yw))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n = int(readline())

p = [list(map(int,readline().split())) for i in range(n)]

xmin = INF
ymin = INF

for (x,y) in p:
    xmin = min(x,xmin)
    ymin = min(y,ymin)

for i in range(n):
    p[i][0] -= xmin
    p[i][1] -= ymin

dmax = 0
dmin = INF

for (x,y) in p:
    dmax = max(dmax, x+y)
    dmin = min(dmin, x+y)

print(dmax-dmin)

Submission status: Wrong Answer

Solution code:
n = int(input())

top= 0
bot= 10**10

for _ in range(n):
	
	x,y = map(int, input().split(' '))
	tot= x+y
	if tot> top:
		top= tot
	if tot< bot:
		bot= tot

print(top-bot)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = []
for i in range(N):
    a = tuple(map(int, input().split()))
    t.append(a[0] + a[1])
t.sort()
print(t[-1] - t[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x * 2, y * 2))
X = sorted(X, key = lambda x: -x[1])
x0, y0 = X[0]
ans = 0
for x, y in X[1:]:
    ans = max(ans, y0 - y + abs(x - x0))
    if abs(x0 - x) > y0 - y:
        a = abs(x - x0) - (y - y0)
        if x0 > x:
            x0 += a
        else:
            x0 -= a
        y0 += a
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a,b=0,0
minp,maxp=0,0
k,j=0,0
for i in range(n):
    x,y=map(int,input().split())
    a=x+y
    b=math.fabs(x-y)
    maxp=max(maxp,a)
    if i==0:
        minp=a
    else:
        minp=min(minp,a)
    j=max(math.fabs(x-y),k)
    k=math.fabs(x-y)
print(int(max(j+k,-minp+maxp)))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
for i, v in enumerate(p):
    x, y = v
    p[i] = x-y, x+y

xm, ym = 0, 0
xw, yw = 10**9, 10**9
for x, y in p:
    xm = max(xm, x)
    xw = min(xw, x)
    ym = max(ym, y)
    yw = min(yw, y)

ans = max(xm - xw, ym - yw)
print(ans)

Submission status: Wrong Answer

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

maxXidx = X.index(max(X))
maxYidx = Y.index(max(Y))
minXidx = X.index(min(X))
minYidx = Y.index(min(Y))

ans = max(abs(X[maxXidx] - X[minXidx]) + abs(Y[maxXidx] - Y[minXidx]),abs(X[maxYidx] - X[minYidx]) + abs(Y[maxYidx] - Y[minYidx]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

max_iter = 100

fmax_dist = -2
max_dist = -1
jibun = 0
#for iter_i in range(max_iter):
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

    jibun = next_jibun 
    fmax_dist = max_dist

    
    
print(out)

Submission status: Wrong Answer

Solution code:
n=int(input())

ans=[]

for _ in range(n):
  a,b=map(int,input().split())
  c=a+b
  ans.append(c)
  
m=min(ans)
M=max(ans)

print(M-m)

Submission status: Wrong Answer

Solution code:
N = int(input())

max_p1 = tuple(map(int, input().split()))
max_p2 = tuple(map(int, input().split()))

max_d = abs(max_p1[0] - max_p2[0]) + abs(max_p1[1] - max_p2[1])

for _ in range(N-2):
  tmp = tuple(map(int, input().split()))
  tmp1 = abs(max_p1[0] - tmp[0]) + abs(max_p1[1] - tmp[1])
  tmp2 = abs(tmp[0] - max_p2[0]) + abs(tmp[1] - max_p2[1])
  
  if tmp1 >= tmp2 > max_d:
    max_d = tmp1
    max_p2 = tmp
  
  if tmp2 > tmp1 > max_d:
    max_d = tmp2
    max_p1 = tmp

print(max_d)

Submission status: Wrong Answer

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

xy.sort()

ans = 0

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

xy = xy[::-1]

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

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

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

xy = xy[::-1]

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

print(ans)

Submission status: Wrong Answer

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

res = 0
for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
    smallest = p * x[0] + q * y[0] + 0
    for i in range(n):
        cur = p * x[i] + q * y[i] + i
        res = max(res, cur - smallest)
        smallest = min(smallest, cur)
print(res-1)

Submission status: Wrong Answer

Solution code:
def sep():
    return map(int,input().strip().split(" "))
import sys
sys.setrecursionlimit(2*10**5)
from random import randint
def lis():
    return list(sep())

def maxAbsValExpr(x, y):
    res, n = 0, len(y)
    for p, q in [ [-1, 1], [-1, -1],[1, 1], [1, -1]]:
        smallest = p * x[0] + q * y[0] + 0
        for i in range(n):
            cur =   q * y[i] + i + p * x[i]
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res
n=int(input())
x=[]
y=[]
for _ in range(n):
    a,b=sep()
    x.append(a)
    y.append(b)
print(maxAbsValExpr(x,y)-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

n = readInt()
minPoint,maxPoint = [],[]
for _ in range(n):
    x,y = readIntList()
    if not minPoint and not maxPoint:
        minPoint = [x,y]
        maxPoint = [x,y]
    else:
        if x < max(minPoint) or y < max(minPoint):
            minPoint = [x,y]
        if x > min(maxPoint) or y > min(maxPoint):
            maxPoint = [x,y]
# print(minPoint,maxPoint)
print(abs(minPoint[0]-maxPoint[0]) + abs(maxPoint[1]-minPoint[1]))

Submission status: Wrong Answer

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

print(max(abs(max(i)+max(j)), abs(min(i)+min(j))))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ab=[]
A=0
B=0
C=1e18
D=1e18
for i in range(n):
	x,y=map(int,input().split())
	A=max(A,x+y)
	B=max(B,x-y)
	C=min(C,x+y)
	D=min(D,x-y)
print(max(A-C,B-D))

Submission status: Wrong Answer

Solution code:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def solve():
    n = getN()

    points = [getList() for i in range(n)]

    ans = 0

    points.sort(key=lambda x: x[0])
    x0, y0 = points[0]
    for x, y in points:
        ans = max(ans, abs(x0 - x) + abs(y0 - y))

    points.sort(key=lambda x: x[1])
    x0, y0 = points[0]
    for x, y in points:
        ans = max(ans, abs(x0 - x) + abs(y0 - y))

    points.sort(key=lambda x: -x[0])
    x0, y0 = points[0]
    for x, y in points:
        ans = max(ans, abs(x0 - x) + abs(y0 - y))

    points.sort(key=lambda x: -x[1])
    x0, y0 = points[0]
    for x, y in points:
        ans = max(ans, abs(x0 - x) + abs(y0 - y))

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
C = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    C[i] = x + y
C = sorted(C)
print(abs(C[-1] - C[0]))

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for _ in [0]*N]


if N>=4:
    P.sort(lambda x:x[0])
    goodP=[P[0],P[-1]]

    P.sort(lambda x:x[1])
    goodP.append(P[0])
    goodP.append(P[-1])
else:
    goodP=P[:]
    
res=[]
for i in range(len(goodP)):
    for j in range(len(goodP)):
        if not i<j:
            continue
        res.append(abs(goodP[i][0]-goodP[j][0])+abs(goodP[i][1]-goodP[j][1]))
print(max(res))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

n = readInt()
minPoint,maxPoint = [],[]
for _ in range(n):
    x,y = readIntList()
    if not minPoint and not maxPoint:
        minPoint = [x,y]
        maxPoint = [x,y]
    else:
        if x < min(minPoint) or y < min(minPoint):
            minPoint = [x,y]
        if x > max(maxPoint) or y > max(maxPoint):
            maxPoint = [x,y]
# print(minPoint,maxPoint)
print(abs(minPoint[0]-maxPoint[0]) + abs(maxPoint[1]-minPoint[1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
dist = []
max = -pow(10, 10)
min = pow(10, 10)
for i in range(n):
    x, y = (int(x) for x in input().split())
    if max < x + y:
        max = x + y
    if min > x + y:
        min = x + y
print(max-min)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    cnt = collections.Counter()
    for x, y in xy:
        cnt[x+y] += 1

    ans = max(cnt.keys()) - min(cnt.keys())
    print(ans)

if __name__ == '__main__':
    resolve()