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: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai_e(n,m): #高速素因数分解 m[n]=nを割ることの出来る最小の素数
    a = set()
    i = 1
    while n>1:
        a.add(m[n])
        n=n//m[n]
    nokori=n
    a.add(nokori)
    return a

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def era(n): #b[n]=nを割ることの出来る最小の素数　の配列を生成　エラトステネスの篩
    b=[i for i in range(n+1)]
    for i in range(2,int(math.sqrt(n)+10)):
        j=1
        temp=i*j
        while temp<=n:
            b[temp]=min(i,b[temp])
            temp+=i
    return b


def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x-y)
        b.append(x+y)
    a=sorted(a)
    b=sorted(b)
    aa=abs(a[0]-a[-1])
    bb=abs(b[0]-b[-1])
    print(max(aa,bb))












if __name__ == "__main__":

    main()

Submission status: Accepted

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

x.sort()
y.sort()

print(max(abs(y[0] - y[-1]), abs(x[-1] - x[0])) if x and y else abs(x[-1] - x[0]) if x else abs(y[0] - y[-1]))

Submission status: Accepted

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


p=max(M)-min(M)
q=max(N)-min(N)
print(max(p,q))

Submission status: Accepted

Solution code:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion

n = inp()
data = [inpl() for _ in range(n)]
lotate_x = [x - y for x, y in data]
lotate_y = [x + y for x, y in data]
ans = max(max(lotate_x) - min(lotate_x), max(lotate_y) - min(lotate_y))
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
from scipy.spatial.distance import chebyshev
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ans = 0
plus = []
minus = []
for i in range(N):
    li = xy[i]
    x = li[0]
    y = li[1]
    plus.append(x+y)
    minus.append(x-y)
ans = 0
ans = max(max(plus)-min(plus),max(minus)-min(minus))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a14=set([])
a23=set([])
for _ in range(N):
	x,y=map(int, input().split())
	a14.add(x+y)
	a23.add(x-y)


b14=max(a14)-min(a14)
b23=max(a23)-min(a23)

print(max(b14,b23))



# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Accepted

Solution code:

N=int(input())
za=list()
for i in range(N):
    za.append(list(map(int,input().split())))
che=list()
for i in range(N):
    a=za[i][0]-za[i][1]
    b=za[i][0]+za[i][1]
    che.append([a,b])
dai1=-1*10**9
syou1=2*(10**9)
dai2=-1*10**9
syou2=2*(10**9)
ans1=0
ans2=0
for i in range(N):
    dai1=max(dai1,che[i][0])
    syou1=min(syou1,che[i][0])
    dai2=max(dai2,che[i][1])
    syou2=min(syou2,che[i][1])
ans1=dai1-syou1
ans2=dai2-syou2
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
max_XminusY = -float('inf')
min_XminusY =  float('inf')
max_XplusY  = -float('inf')
min_XplusY  =  float('inf')

for _ in range(n):
    x, y = map(int, input().split())
    max_XminusY = max(max_XminusY, x - y)
    min_XminusY = min(min_XminusY, x - y)
    max_XplusY  = max(max_XplusY, x + y)
    min_XplusY  = min(min_XplusY, x + y)

print(max(abs(max_XminusY - min_XminusY), abs(max_XplusY - min_XplusY)))

Submission status: Accepted

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


def solve(N: int, x):
    x = list(set(x))
    xs = [_[0] for _ in x]
    ys = [_[1] for _ in x]
    sum_n = [x_+y_ for x_, y_ in zip(xs, ys)]
    sum_m = [x_-y_ for (x_,y_) in zip(xs, ys)]

    a = max(max(sum_n)- min(sum_n), max(sum_m)-min(sum_m))
    print(a)
    

    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 = [()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = (int(next(tokens)),int(next(tokens)))
    solve(N, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = [x[i]+y[i] for i in range(n)]
b = [x[i]-y[i] for i in range(n)]
ans1 = max(a)-min(a)
ans2 = max(b)-min(b)
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N = I()
    XY = LIR(N)

    Z = sorted([x+y for x, y in XY])
    W = sorted([x-y for x, y in XY])
    print(max(Z[-1] - Z[0], W[-1] - W[0]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[[0 for j in range(2)] for i in range(n)]

hu=[-1,-10**9]
hs=[-1,2*(10**9)]
mu=[-1,0]
ms=[-1,10**9]

for i in range(n):
    x,y=map(int,input().split())
    a[i][0]=x
    a[i][1]=y
    z1=y-x
    z2=x+y
    if z1>hu[1]:
        hu[0]=i
        hu[1]=z1
    if z1<ms[1]:
        ms[0]=i
        ms[1]=z1
    if z2<hs[1]:
        hs[0]=i
        hs[1]=z2
    if z2>mu[1]:
        mu[0]=i
        mu[1]=z2

m=abs(a[mu[0]][0]-a[hs[0]][0]) + abs(a[mu[0]][1]-a[hs[0]][1])
h=abs(a[hu[0]][0]-a[ms[0]][0]) + abs(a[hu[0]][1]-a[ms[0]][1])

print(max(m, h))

Submission status: Accepted

Solution code:
N = int(input())

x, y = map(int, input().split())

rt = (x, y)
rb = (x, y)
lt = (x, y)
lb = (x, y)

for _ in range(N-1):
    x, y = map(int, input().split())
    if (x + y - rt[0] - rt[1] > 0):
        rt = (x, y)
    if (x + y - lb[0] - lb[1] < 0):
        lb = (x, y)
    if (x - y - rb[0] + rb[1] > 0):
        rb = (x, y)
    if (x - y - lt[0] + lt[1] < 0):
        lt = (x, y)

def dist(p, q):
    return (abs(p[0]-q[0]) + abs(p[1]-q[1]))
print(max(dist(rt, lb), dist(rb, lt)))

Submission status: Accepted

Solution code:
n = int(input())
ps = []
ms = []
xs = []
ys = []
for i in range(n):
    x,y = map(int, input().split())
    ps.append(x+y)
    ms.append(x-y)
    xs.append(x)
    ys.append(y)
ps.sort()
ms.sort()
a1 = ps[-1]-ps[0]
a2 = ms[-1]-ms[0]
print(max(a1,a2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    Z = list(tuple(map(int,input().split())) for _ in range(N))
    L = []

    L1 = sorted(z[0]+z[1] for z in Z)
    L.append(L1[-1]-L1[0])

    L1 = sorted(z[0]-z[1] for z in Z)
    L.append(L1[-1]-L1[0])

    L1 = sorted(-z[0]+z[1] for z in Z)
    L.append(L1[-1]-L1[0])

    L1 = sorted(-z[0]-z[1] for z in Z)
    L.append(L1[-1]-L1[0])
    return str(max(L))

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    XY = []
    for i in range(N):
        x, y = map(int, input().strip().split())
        XY.append((x, y))
    return N, XY


def solve(N, XY):
    ans = []
    XY.sort(key=lambda a: a[0] + a[1])
    x0, y0 = XY[0]
    x1, y1 = XY[-1]
    ans.append(abs(x1-x0) + abs(y1-y0))
    XY.sort(key=lambda a: a[1] - a[0])
    x0, y0 = XY[0]
    x1, y1 = XY[-1]
    ans.append(abs(x1-x0) + abs(y1-y0))
    return max(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
N = int(input())
x = [0]* N
y = [0] * N
for i in range(N):
  a , b = map(int,input().split())
  x[i] = a+b
  y[i] = a-b

ans = max([max(x) - min(x),max(y) - min(y)])
print(ans)

Submission status: Accepted

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

xzy = []
for _ in range(4):
  xzy.append([])

for x, y in xy:
  xzy[0].append(x + y)
  xzy[1].append(x - y)
  xzy[2].append(-x + y)
  xzy[3].append(-x - y)


anses = []
for z in xzy:
  anses.append(max(z) - min(z))
print(max(anses))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
point_set = set()
point_dict1 = {}
point_dict2 = {}
for i in range(n):
    x, y = map(int, input().split())
    point_set.add((x, y))
    point_dict1[x + y] = (x, y)
    point_dict2[y - x] = (x, y)
if len(point_set) == 1:
    print(0)
else:
    min_point1 = min(point_dict1)
    max_point1 = max(point_dict1)
    min_point2 = min(point_dict2)
    max_point2 = max(point_dict2)
    print(max(max_point1 - min_point1, max_point2 - min_point2))

Submission status: Accepted

Solution code:
import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import math

N = int(input())

max_sum = -math.inf
min_sum = math.inf
max_diff = -math.inf
min_diff = math.inf
for _ in range(N):
    x, y = map(int, input().split())
    max_sum = max(max_sum, x+y)
    min_sum = min(min_sum, x+y)
    max_diff = max(max_diff, x-y)
    min_diff = min(min_diff, x-y)

answer = max(max_sum - min_sum, max_diff - min_diff)
print(answer)

Submission status: Accepted

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

f0 = []
f1 = []
for i in XY:
    f0.append(i[0]-i[1])
    f1.append(i[0]+i[1])#左がf0右がf1

print(max(max(f0)-min(f0),max(f1)-min(f1)))

Submission status: Accepted

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():
    n = ni()
    d = [na() for _ in range(n)]

    tINF = 10 ** 15

    max_numR = -INF
    min_numR = INF
    max_numL = -INF
    min_numL = INF

    for x, y in d:
        max_numR = max(max_numR, x + y)
        min_numR = min(min_numR, x + y)

        max_numL = max(max_numL, tINF - x + y)
        min_numL = min(min_numL, tINF - x + y)

    ans = max(max_numR - min_numR, max_numL - min_numL)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2
# from itertools import accumulate
# from collections import defaultdict, Counter

def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n = int(input())
    coords = []
    for i in range(n):
        coords.append([int(x) for x in input().split()])
    
    r = int(1e9)
    x1, y1 = [0, 0]
    x2, y2 = [r, 0]
    x3, y3 = [0, r]
    x4, y4 = [r, r]

    d1 = []
    d2 = []
    d3 = []
    d4 = []
    
    for x, y in coords:
        d1.append(abs(x-x1) + abs(y - y1))
        d2.append(abs(x-x2) + abs(y - y2))
        d3.append(abs(x-x3) + abs(y - y3))
        d4.append(abs(x-x4) + abs(y - y4))

    d1.sort()
    d2.sort()
    d3.sort()
    d4.sort()

    # print(*d1)
    # print(*d2)
    # print(*d3)
    # print(*d4)

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


#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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: Accepted

Solution code:
n = int(input())

x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
d1_max = x[0]+y[0]
d1_min = x[0]+y[0]
d2_max = x[0] - y[0]
d2_min = x[0]-y[0]
ans = -1
for i in range(1,n):
    d1_max = max(d1_max,x[i]+y[i])
    d1_min = min(d1_min,x[i]+y[i])
    d2_max = max(d2_max,x[i] - y[i])
    d2_min = min(d2_min,x[i]-y[i])
    ans = max((d1_max-d1_min),(d2_max-d2_min))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for s in range(n):
    x,y = map(int,input().split())
    a.append(x+y)
    b.append(x-y)
c = max(a) - min(a)
d = max(b) - min(b)
if c < d:
    c = d
print(c)

Submission status: Accepted

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 = []
p = []
m = []
for i in range(n):
    a,b = mp()
    point.append((a,b))
    p.append(a+b)
    m.append(a-b)
print(max(max(p)-min(p), max(m)-min(m)))

Submission status: Accepted

Solution code:

N = int(input())
p_list = []
for _ in range(N):
    a, b = input().split()
    a, b = int(a), int(b)
    p_list.append((a, b))

# print(list_pt)

# 凸包? が判定できれば？

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 convex_hull(points):
    # どの3点も直線上に並んでいないと仮定する。
    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]


# p_list = convex_hull([(1,1), (3,1), (2,2), (2,3)])

""" try max time """
# N = 2*10**5
# import numpy as np
# X = np.random.randint(1, 10**9, (N, 2)).tolist()

p_list = convex_hull(p_list)

from itertools import combinations

max_len = 0
for a, b in combinations(p_list, 2):
    max_len = max(max_len, abs(a[0] - b[0]) + abs(a[1] - b[1]))

print(max_len)

Submission status: Accepted

Solution code:
N = int(input())
X, Y = zip(*[[int(a) for a in input().split()] for _ in range(N)])

L = [(x, y, x + y, y - x) for x, y in zip(X, Y)]

L.sort(key = lambda a : a[2])  # x+yでソート
ans = abs(L[0][0] - L[-1][0]) + abs(L[0][1] - L[-1][1])

L.sort(key = lambda a : a[3])  # y-xでソート
ans = max(ans, abs(L[0][0] - L[-1][0]) + abs(L[0][1] - L[-1][1]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
m1, m2, m3, m4 = [-10**10]*4

def maxAbsValExpr(x, y, n):
    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] 
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res

x = []
y = []
for _ in range(n):
    u, v = [int(x) for x in input().strip().split()]
    x.append(u)
    y.append(v)
    # if x+y>
    # m1 = max(m1, x+y)
    # m2 = max(m2, y-x)
    # m3 = max(m3, x-y)
    # m4 = max(m4, -1*y-x)

res = maxAbsValExpr(x, y, n)
print(res)

Submission status: Accepted

Solution code:
n=int(input())
fxy=[[] for _ in range(n)]
for i in range(n):
    x,y=map(int, input().split())
    fxy[i].append(x-y)
    fxy[i].append(x+y)
fxy.sort()
ans=fxy[-1][0]-fxy[0][0]
fxy.sort(key=lambda x: x[1])
ans=max(ans,fxy[-1][1]-fxy[0][1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
XY_set = set(tuple(map(int, input().split())) for _ in range(N))
N = len(XY_set)

XY45 = np.array([(x + y, x - y) for x, y in XY_set]).T
ans = max(XY45[0].max() - XY45[0].min(),
          XY45[1].max() - XY45[1].min())
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

# coding: utf-8


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):
    # どの3点も直線上に並んでいないと仮定する。
    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]

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))
if N == 2:
    x0,y0 = p[0]
    x1,y1 = p[1]
    print(abs(x0-x1)+abs(y0-y1))
    exit()

p = get_convex_hull(p)
n = len(p)
for i in range(n):
    xi,yi = p[i]
    for j in range(i+1,n):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
point = []
for _ in range(n):
    point.append((tuple(map(int, input().split()))))
point = list(set(point))
point = sorted(point)
if len(point) == 1: print(0)
else:  
    d1 = max([(x+y) for x,y in point])- min([(x+y) for x,y in point])
    d2 = max([(x-y) for x,y in point]) - min([(x-y) for x,y in point])
    print(max(d1,d2))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    """
    https://www.quora.com/How-can-I-find-the-maximum-Manhattan-distance-between-2-points-from-a-given-set-of-points
    """
    N = int(input())
    x, y = map(int, input().split())
    maximalp = x + y
    minimalp = x + y
    maximaln = x - y
    minimaln = x - y
    for _ in range(N - 1):
        x, y = map(int, input().split())
        maximalp = max(maximalp, x + y)
        minimalp = min(minimalp, x + y)
        maximaln = max(maximaln, x - y)
        minimaln = min(minimaln, x - y)
    print(max(maximalp - minimalp, maximaln - minimaln))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
d0 = []
d1 = []
for i in range(n):
  xi,yi = map(int,input().split())
  d0.append(xi-yi)
  d1.append(xi+yi)
print(max(max(d0)-min(d0),max(d1)-min(d1)))

Submission status: Accepted

Solution code:
N = int(input())
x, y = map(int, input().split())
A = [x + y, x + y, y - x, y - x]
for i in range(N - 1):
  x, y = map(int, input().split())
  p = x + y
  q = y - x
  A[0] = max(A[0], p)
  A[1] = min(A[1], p)
  A[2] = max(A[2], q)
  A[3] = min(A[3], q)
print(max(A[0] - A[1], A[2] - A[3]))

Submission status: Accepted

Solution code:
INF=2**31
n=int(input())
f=lambda:map(int,input().split())
s=t=INF
S=T=-INF
for _ in range(n):
  x,y=f()
  s=min(s,x+y)
  S=max(S,x+y)
  t=min(t,x-y)
  T=max(T,x-y)
print(max(S-s,T-t))

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    x, y = [int(i) for i in input().split()]
    a.append(x)
    b.append(y)
ans = 0
for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
    cur_min = float('inf')
    cur_max = float('-inf')
    for i in range(n):
        tmp = s*a[i] + t*b[i]
        cur_min = min(cur_min, tmp)
        cur_max = max(cur_max, tmp)
    ans = max(ans, cur_max - cur_min)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
a,b,c,d=-10**10,10**10,-10**10,10**10
l=[0]*4
for x,y in XY:
    if x+y>a: a=x+y;l[0]=(x,y)
    if x+y<b: b=x+y;l[1]=(x,y)
    if x-y>c: c=x-y;l[2]=(x,y)
    if x-y<d: d=x-y;l[3]=(x,y)
from itertools import combinations
print(max([abs(p[0]-q[0])+abs(p[1]-q[1]) for p,q in combinations(l,2)]))

Submission status: Accepted

Solution code:
N = int(input())

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

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

x, y = points[0]

maxvalue_p = x + y
minvalue_p = x + y
maxvalue_m = x - y
minvalue_m = x - y
maxvalue_p_p = points[0]
minvalue_p_p = points[0]
maxvalue_m_p = points[0]
minvalue_m_p = points[0]

for x, y in points:
	p = x + y
	m = x - y
	if maxvalue_p == None or maxvalue_p < p:
		maxvalue_p = p
		maxvalue_p_p = (x, y)
	if minvalue_p == None or minvalue_p > p:
		minvalue_p = p
		minvalue_p_p = (x, y)
	if maxvalue_m == None or maxvalue_m < m:
		maxvalue_m = m
		maxvalue_m_p = (x, y)
	if minvalue_m == None or minvalue_m > m:
		minvalue_m = m
		minvalue_m_p = (x, y)

topvalue = 0

for x, y in points:
	topvalue = max(topvalue, 
		m_dis(x, y, maxvalue_p_p[0], maxvalue_p_p[1]),
		m_dis(x, y, minvalue_p_p[0], minvalue_p_p[1]),
		m_dis(x, y, maxvalue_m_p[0], maxvalue_m_p[1]),
		m_dis(x, y, minvalue_m_p[0], minvalue_m_p[1]))

print(topvalue)

Submission status: Accepted

Solution code:
n=int(input(""))
lista=[]
listb=[]

for i in range(n):
    xy=input("").split(" ")
    lista+=[int(xy[0])+int(xy[1])]
    listb+=[int(xy[0])-int(xy[1])]
t=max(lista)-min(lista)
tt=max(listb)-min(listb)
print(max(t,tt))

Submission status: Accepted

Solution code:
#from collections import deque
#from math import gcd
#MOD = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
ans = 0
#print(ans)
r = []
for k in range(N):
  r.append(tuple(map(int, input().split())))
r.sort(key = lambda x:x[0])
#print(r)
nowx = -1
lastx_min = r[0][0]
lastx_max = r[0][0]

miny = r[0][1]
maxy = r[0][1]
k = 0
while k < N:
  if nowx != r[k][0]:
    nowx = r[k][0]
    while r[k][0] == nowx:
      ans = max(ans, abs(miny - r[k][1]) + nowx - lastx_min, abs(maxy-r[k][1])+ nowx -lastx_max)
      if miny - (nowx - lastx_min) > r[k][1]:
        miny = r[k][1]
        lastx_min = nowx
      if maxy + (nowx - lastx_max) < r[k][1]:
        maxy = r[k][1]
        lastx_max = nowx
      k += 1
      if k == N:
        break

print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, P):
    a = [x - y for x, y in P]
    b = [x + y for x, y in P]
    c = max(max(a) - min(a), max(b) - min(b))
    print(c)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, P)

Submission status: Accepted

Solution code:
N = int(input())
dist = []
dist2 = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    dist.append(x + y)
    dist2.append(x - y)
dist.sort()
dist2.sort()
ans = dist[N - 1] - dist[0]
ans2 = dist2[N - 1] - dist2[0]
print(max(ans, ans2))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
  x,y=(int(i) for i in input().split())
  a.append(x-y)
  b.append(x+y)
a.sort()
b.sort()
print(max(a[-1]-a[0],b[-1]-b[0]))

Submission status: Accepted

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:
    srt1 = sorted(points, key=lambda x: x[0] + x[1])
    x1,y1 = srt1[0]
    x2,y2 = srt1[-1]
    ans1 = abs(x1+y1 - (x2+y2))
    srt2 = sorted(points, key=lambda x: x[0] - x[1])
    x1,y1 = srt2[0]
    x2,y2 = srt2[-1]
    ans2 = abs((x1-y1) - (x2-y2))
    print(max(ans1, ans2))