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:
def main():
    examE()

def examA():
    N = I()
    ans = 1^N
    print(ans)
    return

def examB():
    a, b, c, d = LI()
    ans = max(a*c,a*d,b*c,b*d)
    print(ans)
    return

def examC():
    N = I()
    if N==1:
        ans = 0
    else:
        ans = pow(10,N,mod) - pow(9,N,mod)*2 + pow(8,N,mod)
        ans += mod*2
        ans %= mod
    print(ans)
    return

def examD():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    S = I()
    C = combination(S,mod)
    cnt = 0
    for i in range(S//3):
        cur = S - (i+1)*3 + i
        cnt += C.comb(cur,i)
        cnt %= mod
    ans = cnt
    print(ans)
    return

def examE():
    N = I()
    CD = [[]for _ in range(2)]
    for i in range(N):
        x, y = LI()
        CD[0].append(x-y)
        CD[1].append(x+y)
    ans = max(max(CD[0]) - min(CD[0]),max(CD[1]) - min(CD[1]))
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
max_pp = -2 * 10**10
min_pp = 2 * 10**10
max_pn = -2 * 10**10
min_pn = 2 * 10**10

for i in range(n):
  x, y = map(int, input().split())
  max_pp = max(max_pp, x + y)
  min_pp = min(min_pp, x + y)
  max_pn = max(max_pn, x - y)
  min_pn = min(min_pn, x - y)
print(max(max_pp - min_pp, max_pn - min_pn))

Submission status: Accepted

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

ans1 = max(axis1)-min(axis1)
ans2 = max(axis2)-min(axis2)

print(max(ans1,ans2))

Submission status: Accepted

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

print(max(max(pointx)-min(pointx),(max(pointy)-min(pointy))))

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
x = []
y = []
for i in range(n):
    xx,yy = inm()
    x.append(xx)
    y.append(yy)
dif = [x[i]-y[i] for i in range(n)]
sum = [x[i]+y[i] for i in range(n)]
print(max(max(dif)-min(dif),max(sum)-min(sum)))

Submission status: Accepted

Solution code:
n = int(input())
maxx, minx, maxy, miny = -10 ** 10, 10 ** 10, -10 ** 10, 10 ** 10
for i in range(n):
    x, y = map(int, input().split())
    x, y = x + y, x - y
    maxx = max(x, maxx)
    minx = min(x, minx)
    maxy = max(y, maxy)
    miny = min(y, miny)
print(max(maxx - minx, maxy - miny))

Submission status: Accepted

Solution code:
from sys import stdin
n=int(input())
D1=[]
D2=[]
for _ in range(n):
    x, y= map(int, stdin.readline().split())
    r1=x+y
    r2=abs((10**9-x)+y)
    D1.append(r1)
    D2.append(r2)

ans1=max(D1)-min(D1)
ans2=max(D2)-min(D2)
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
N = int(input())
p1 = (0, 0)
p2 = (0, 0)
p3 = (0, 0)
p4 = (0, 0)

for i in range(N):
    x, y = map(int, input().split())
    if i == 0:
        p1 = (x, y)
        p2 = (x, y)
        p3 = (x, y)
        p4 = (x, y)
    else:
        if p1[0] + p1[1] < x + y:
            p1 = (x, y)
        if -p2[0] + p2[1] < -x + y:
            p2 = (x, y)
        if -p3[0] - p3[1] < - x - y:
            p3 = (x, y)
        if p4[0] - p4[1] < x - y:
            p4 = (x, y)

ans1 = abs(p1[0] - p3[0]) + abs(p1[1] - p3[1])
ans2 = abs(p2[0] - p4[0]) + abs(p2[1] - p4[1])

print(max(ans1, ans2))

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def INP():
    N=10;A=10
    n=random.randint(1,N)
    a=[random.randint(1,A) for i in range(n)]
    return n,a
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True



n=I()
p=[]
m=[]

for i in range(n):
    x,y=LI()
    p+=[x+y]
    m+=[x-y]

ans=max(max(p)-min(p),max(m)-min(m))
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

'''
3
1 1
2 4
3 2
'''

def solve(l):
	n = len(l)
	d = defaultdict(int)
	l1,l2,l3 = [],[],[]
	for x,y in l:
		l1.append(x+y)
		l2.append(x-y)
		l3.append(y-x)
	a = abs(max(l1) - min(l1))
	b = abs(max(l2) - min(l2))
	c = abs(max(l3) - min(l3))
	return max(a,b,c)

N = int(stdin.readline())
L = []
for i in range(N):
	a,b = map(int, input().split())
	L.append([a,b])
ans = solve(L)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = []
B = []
for i in range(N):
    x,y = list(map(int,input().split()))
    A.append(x+y)
    B.append(-x+y)


A.sort()
B.sort()

print(max(abs(A[0]-A[-1]),abs(B[0]-B[-1])))

Submission status: Accepted

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

xpys = [x + y for x, y in xys]
dist1 = max(xpys) - min(xpys)
xmys = [x - y for x, y in xys]
dist2 = max(xmys) - min(xmys)
print(max(dist1, dist2))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    r = [(x+y,x-y) for x,y in p]
    mx = [float("inf"),float("inf")]
    my = [float("inf"),float("inf")]
    Mx = [-float("inf"),float("inf")]
    My = [float("inf"),-float("inf")]
    for X,Y in r:
        if X < mx[0]:
            mx = [X,Y]
        if Y < my[1]:
            my = [X,Y]
        if Mx[0] < X:
            Mx = [X,Y]
        if My[1] < Y:
            My = [X,Y]
    ans = 0
    for X,Y in r:
        x = (X+Y)//2
        y = (X-Y)//2
        for A,B in (mx,my,Mx,My):
            a = (A+B)//2
            b = (A-B)//2
            d = abs(x-a)+abs(y-b)
            if ans < d:
                ans = d
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
que= [[]for i in range(2)]
for i in range(N):
    x,y = map(int,input().split())
    que[0].append(x-y)
    que[1].append(x+y)
que[0].sort()
que[1].sort()
ans = max(que[0][-1]-que[0][0],que[1][-1]-que[1][0])
print(ans)

Submission status: Accepted

Solution code:

"""

xを小さい順に見ていく
あるY以下で-x-yが最大のものと, -x+yが最大の物を保持
Yを座圧しておく
→セグ木

"""

#0-indexed , 半開区間[a,b)
#calc変更で演算変更
class SegTree:

    def __init__(self,N,first):
        self.NO = 2**(N-1).bit_length()
        self.First = first
        self.data = [first] * (2*self.NO)

    def calc(self,l,r):
        return max(l,r)

    def update(self,ind,x):
        ind += self.NO - 1
        self.data[ind] = max( x , self.data[ind] )
        while ind >= 0:
            ind = (ind - 1)//2
            self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])

    def query(self,l,r):
        L = l + self.NO
        R = r + self.NO
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s , self.data[R-1])
            if L & 1:
                s = self.calc(s , self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

from sys import stdin
N = int(stdin.readline())

xy = []
dic = {}
lis = []
for i in range(N):

    x,y = map(int,stdin.readline().split())
    xy.append((x,y))

    if y not in dic:
        dic[y] = 0
        lis.append(y)

xy.sort()
lis.sort()
for i in range(len(lis)):
    dic[lis[i]] = i

LT = SegTree(len(lis),float("-inf"))
RT = SegTree(len(lis),float("-inf"))
ans = 0

for X,Y in xy:

    ans = max(ans , X+Y+LT.query(0,dic[Y]+1))
    ans = max(ans , X-Y+RT.query(dic[Y],len(lis)))

    LT.update(dic[Y] , -X-Y )
    RT.update(dic[Y] , -X+Y )

print (ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################
 

N = I()
x,y = LIR(N,2)

max1 = -float('inf')
min1 = float('inf')
for i in range(N):
    max1 = max(max1,x[i]-y[i])
    min1 = min(min1,x[i]-y[i])

max2 = -float('inf')
min2 = float('inf')
for i in range(N):
    max2 = max(max2,x[i]+y[i])
    min2 = min(min2,x[i]+y[i])

print(max(max1-min1,max2-min2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = int(input())

M1 = -10 ** 10
M2 = - 10 ** 10

m1 = 10 ** 10
m2 = 10 ** 10

for i in range(N):
  x, y = map(int, input().split())
  M1 = max(x + y, M1)
  m1 = min(x + y, m1)
  M2 = max(x - y, M2)
  m2 = min(x - y, m2)
print(max(M1 - m1, M2 - m2))

Submission status: Accepted

Solution code:
n = int(input())
raw = []
p = []
m = []
for _ in range(n):
  x,y = map(int,input().split())
  p.append(x+y)
  m.append(x-y)
print(max((max(p)-min(p)),max(m)-min(m)))

Submission status: Accepted

Solution code:
N = int(input())
points = []
for _ in range(N):
    points.append([int(s) for s in input().split()])
def dist(x, y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])
points.sort(key=lambda x: x[0] + x[1])
d1 = dist(points[0], points[-1])
# print(points)
points.sort(key=lambda x: x[0] - x[1])
d2 = dist(points[0], points[-1])
# print(points)
print(max(d1, d2))

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)]
A.sort(key=lambda p:p[0]+p[1])
B.sort(key=lambda p:p[0]-p[1])
def dist(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
ans0=dist(A[0],A[-1])
ans1=dist(B[0],B[-1])
print(max(ans0,ans1))

Submission status: Accepted

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

n = int(input())

x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a+b)
    y.append(a-b)

x.sort()
y.sort()

res = max(x[-1]-x[0],y[-1]-y[0])

print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
l = [(item[0]+item[1], item[0]-item[1]) for item in xy]
l.sort()
v0 = l[-1][0]-l[0][0]
l.sort(key=lambda x: x[1])
v1 = l[-1][1]-l[0][1]
ans = max(v0,v1)
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    p, m = [0]*n, [0]*n
    for i in range(n):
        x, y = map(int, input().split())
        p[i] = x + y
        m[i] = x - y

    print(max(max(p) - min(p), max(m) - min(m)))

main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pa,ma=-10**10,-10**10
pi,mi=10**10,10**10
for i in range(N):
    x,y=map(int,input().split())
    s=x+y
    if s>pa:
        pa=s
    if s<pi:
        pi=s
    s=x-y
    if s>ma:
        ma=s
    if s<mi:
        mi=s
print(max(pa-pi,ma-mi))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    xy = LIR(n)
    f0 = [x - y for x, y in xy]
    f0.sort()
    f1 = [x + y for x, y in xy]
    f1.sort()
    print(max(f0[-1] - f0[0], f1[-1] - f1[0]))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

N=intput()
xy=[]
wa=[]
sa=[]
for i in range(N):
    x,y=mint()
    wa.append(x+y)
    sa.append(x-y)
print(max(max(wa)-min(wa), max(sa)-min(sa)))

Submission status: Accepted

Solution code:
import numpy as np

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

x = xy[:,0]
y = xy[:,1]

a = x+y
b = -x+y

ans = max(a.max() - a.min(), b.max()-b.min())
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*xy = map(int,read().split())

wa = []
sa = []
for x,y in zip(xy[::2],xy[1::2]):
    wa.append(x+y)
    sa.append(x-y)

v = max(wa)-min(wa)
w = max(sa)-min(sa)

print(max(v,w))

Submission status: Accepted

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
U = [x+y for x, y in XY]
V = [x-y for x, y in XY]
min_u = min(U)
max_u = max(U)
min_v = min(V)
max_v = max(V)
print(max(
    max_u - min_u,
    max_v - min_v
))

Submission status: Accepted

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

z = []
w = []
for i in range(N):
    x,y = xy[i]
    z.append(x+y)
    w.append(x-y)
ans = max(max(z)-min(z),max(w)-min(w))
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    p = [list(map(int, input().split())) for i in range(n)]

    p0, p1 = [0]*n, [0]*n

    for i in range(n):
        p0[i] = p[i][0] - p[i][1]
        p1[i] = p[i][0] + p[i][1]
    
    ans = max(max(p0)-min(p0), max(p1)-min(p1))
    print(ans)



    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
XY = list(map(int, input().split()) for _ in range(n))
x_max = -float("inf")
y_max = -float("inf")
x_min = float("inf")
y_min = float("inf")
for x, y in XY:
    a, b = x-y, x+y
    x_max = max(x_max, a)
    x_min = min(x_min, a)
    y_max = max(y_max, b)
    y_min = min(y_min, b)
s = x_max - x_min
t = y_max - y_min
ans = max(s, t)
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    XL=[0]*N
    YL=[0]*N
    for i in range(N):
        x,y=MI()
        X=x+y
        Y=x-y
        XL[i]=X
        YL[i]=Y
        
    x=max(XL)-min(XL)
    y=max(YL)-min(YL)
    
    print(max(x,y))
        

main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
data = ILL(N)

dicplus = DD(int)
dicminus = DD(int)

for x,y in data:
  dicplus[x+y] = 1
  dicminus[x-y] = 1
k_plus = [k for k in dicplus]
k_minus = [k for k in dicminus]

ans1 = max(k_plus)-min(k_plus)
ans2 = max(k_minus)-min(k_minus)

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

XY = np.array(read().split(), np.int64)[1:]

X, Y = XY[::2], XY[1::2]

A = X + Y
B = X - Y

a = A.max() - A.min()
b = B.max() - B.min()
print(max(a, b))

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
n = int(input())

z_vec = [0] * n
w_vec = [0] * n


for i in range(0, n + 1):
    line = input()
    tmp = line.split()
    z_vec[i] = int(tmp[0]) + int(tmp[1])
    w_vec[i] = int(tmp[0]) - int(tmp[1])

z_ans = max(z_vec) - min(z_vec)
w_ans = max(w_vec) - min(w_vec)


print(f'{max(z_ans, w_ans)}')

Submission status: Runtime Error

Solution code:
n = int(input())

z_vec = [0] * n
w_vec = [0] * n


for i in range(0, n + 1):
    tmp = input().split()
    z_vec[i] = int(tmp[0]) + int(tmp[1])
    w_vec[i] = int(tmp[0]) - int(tmp[1])

z_ans = max(z_vec) - min(z_vec)
w_ans = max(w_vec) - min(w_vec)


print(f'{max(z_ans, w_ans)}')

Submission status: Runtime Error

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(i+1,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)
  max = distance[0]
  if distance[i-1] > max:
    max = temp[i]

print(max)

Submission status: Runtime Error

Solution code:
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)-1):
  for j in range(i, len(x)-1):
    temp = abs(x[i] - x[j+i]) + abs(y[i] - y[j+i])
    distance.append(temp)

max = distance[0]
 
for i in range(1,len(distance)-1):
  if distance[i] >= max:
    max = distance[i]
 
print(max)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]
rt = 0
for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  rt+= dps[i]
print(sum(dps))

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]
rt = 0
for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  rt+= dp[i]
print(sum(dps))