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:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    for i in range(n):
        x,y = invr()
        q = max(q,x + y)
        qq = max(qq,abs(x - y))
        w = min(w,x + y)
        ww = min(ww,abs(x - y))
    print(max(q - w,qq - ww))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = 0
b = 10**9
c=0
d = 10**9
aint=0
bint=0
cint=0
dint=0
g =[]
for i in range(n):
  x,y = map(int, input().split())
  if x>a:
    a=x
    aint=i
  if x<b:
    b=x
    bint=i
  if y>c:
    c=y
    cint=i
  if y<d:
    d=y
    dint=i
  g.append([x,y])
r = [aint,bint,cint,dint]
ans= [0]
def man(a,b):
  return abs(g[a][0]-g[b][0])+abs(g[a][1]-g[b][1])
for i in r:
  for j in r:
    if i==j:
      continue
    ans.append(man(i,j))
print(max(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
kouho=[0]*6#xmax,ymax,summax,xmin,ymin,summin
kouho[0]=[0,0]
kouho[1]=[0,0]
kouho[2]=[0,0]
kouho[3]=[10**9+1,0]
kouho[4]=[0,10**9+1]
kouho[5]=[10**9+1,10**9+1]
ans=0
for i in range(N):
    x,y=map(int,input().split())
    if x>kouho[0][0]:
        kouho[0][0]=x
        kouho[0][1]=y
    if y>kouho[1][1]:
        kouho[1][0]=x
        kouho[1][1]=y
    if x+y>kouho[2][0]+kouho[2][1]:
        kouho[2][0]=x
        kouho[2][1]=y
    if x<kouho[3][0]:
        kouho[3][0]=x
        kouho[3][1]=y
    if y<kouho[4][1]:
        kouho[4][0]=x
        kouho[4][1]=y
    if x+y<kouho[5][0]+kouho[5][1]:
        kouho[5][0]=x
        kouho[5][1]=y
for j in range(5):
    for k in range(j+1,6):
        ans=max(ans,abs(kouho[j][0]-kouho[k][0])+abs(kouho[j][1]-kouho[k][1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

A= []
N = int(input())
for i in range(N):
    a,b = ilele()
    A.append(a+b)
print(abs(min(A) - max(A)))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for _ in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
    
al,be = 1000000000,1000000000
f = [(1,1),(1,-1),(-1,1),(-1,-1)]
ans = -1145141919810364

for k,l in f:
    alfa = al * k
    beta = be * l
    man = []
    for i,j in xy:
        man.append((alfa-i) + (beta-j))
    ans = max(ans,max(man) - min(man))
    
print(ans)

Submission status: Wrong Answer

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

xdict = {}
ydict = {}
for i in range(n):
    x,y = map(int,input().split())
    if x in xdict:
        xdict[x].add(y)
    else:
        xdict[x] = {y}
    if y in ydict:
        ydict[y].add(x)
    else:
        ydict[y] = {x}

xmin = min(xdict)
ymin = min(ydict)

xmin_ymin = min(xdict[xmin])
ymin_xmin = min(ydict[ymin])

xmax = max(xdict)
ymax = max(ydict)

xmax_ymax = max(xdict[xmax])
ymax_xmax = max(ydict[ymax])

ans = 0
ans = max(xmax - xmin + xmax_ymax - xmin_ymin,ans)
ans = max(ymax - xmin + ymax_xmax - xmin_ymin,ans)
ans = max(xmax - ymin + xmax_ymax - ymin_xmin,ans)
ans = max(ymax - ymin + ymax_xmax - ymin_xmin,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
x0,y0=XY[0]
d=0
p,q=XY[0]
for x,y in XY:
    if abs(x-x0)+abs(y-y0)>d:
        p,q=x,y
        d=abs(x-x0)+abs(y-y0)
d=0
for x,y in XY:
    if abs(x-p)+abs(y-q)>d:
        d=abs(x-p)+abs(y-q)
print(d)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = []
for i in range(n):
  arr.append(tuple(map(int, input().split())))
arr.sort(key = sum)
mx = max(arr, key = sum)
mn = min(arr, key = sum)
print(abs(mx[0]-mn[0]) + abs(mx[1] - mn[0]))

Submission status: Wrong Answer

Solution code:
a=[]
for t in range(int(input())):
  x,y=[int(_) for _ in input().split()]
  a.append([x,y])
  a.sort()
  print(abs(a[-1][0]-a[0][0])+abs(a[-1][1]-a[0][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
x,y = list(map(int,input().split()))
c = 0
for i in range(n-1):
    a,b = list(map(int,input().split()))
    c = max(abs(x-a)+abs(y-b),c)
    x,y = a,b
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
x1, y1 = map(int, input().split())
centre = [x1, y1]

left_bottom = [x1, y1]
left_bottom_dist = 0

left_top = [x1, y1]
left_top_dist = 0

right_bottom = [x1, y1]
right_bottom_dist = 0

right_top = [x1, y1]
right_top_dist = 0

for i in range(N-1):
  xi, yi = map(int, input().split())
  if xi <= x1 and yi <= y1:
    if x1 - xi + y1 - xi >= left_bottom_dist:
      left_bottom = [xi, yi]
      left_bottom_dist = x1 - xi + y1 - xi
  if xi <= x1 and yi >= y1:
    if x1 - xi + yi - y1 >= left_top_dist:
      left_top = [xi, yi]
      left_top_dist = x1 - xi + yi - y1
  if xi >= x1 and yi <= y1:
    if xi - x1 + y1 - yi >= right_bottom_dist:
      right_bottom = [xi, yi]
      right_bottom_dist = xi - x1 + y1 - yi 
  if xi >= x1 and yi >= y1:
    if xi - x1 + yi - y1 >= right_top_dist:
      right_top = [xi, yi]
      right_top_dist = xi - x1 + yi - y1

D1 = abs(right_top[0] - left_bottom[0]) + abs(right_top[1] - left_bottom[1])
D2 = abs(right_bottom[0] - left_top[0]) + abs(right_bottom[1] - left_top[1])
D3 = abs(left_top[0] - left_bottom[0]) + abs(left_top[1] - left_bottom[1])
D4 = abs(right_top[0] - right_bottom[0]) + abs(right_top[1] - right_bottom[1])
D5 = abs(left_top[0] - right_top[0]) + abs(left_top[1] - right_top[1])
D6 = abs(left_bottom[0] - right_bottom[0]) + abs(left_bottom[1] - right_bottom[1])

print(max(D1, D2, D3, D4, D5, D6))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
import math
ll=[]
for i in range(n):
    ll.append([l[i][0]+l[i][1],i])
ll.sort()
print(int(math.fabs(l[ll[0][1]][0]-l[ll[-1][1]][0])+math.fabs(l[ll[0][1]][1]-l[ll[-1][1]][1])))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n):
    l.append(tuple(map(int,input().split())))
xl = sorted(l, key=lambda x: x[1], reverse=True)
yl = sorted(l, key=lambda x: x[0], reverse=True)
a = abs(xl[0][0]-xl[-1][0])+abs(xl[0][1]-xl[-1][1])
b = abs(yl[0][0]-yl[-1][0])+abs(yl[0][1]-yl[-1][1])
print(max(a,b))

Submission status: Wrong Answer

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

memo_x = sorted(memo, key=lambda x: x[0])
memo_y = sorted(memo, key=lambda x: x[1])

for i in range(1,N):
    tmp = abs(memo_x[i][0]-memo_x[0][0])-abs(memo_x[0][1]-memo_x[i][1])
    ans = max(ans,tmp)

for i in range(1,N):
    tmp = abs(memo_y[i][0]-memo_y[0][0])-abs(memo_y[0][1]-memo_y[i][1])
    ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
z = []
for _ in range(N):
    x, y = map(int, input().split())
    z.append(x+y)
z.sort()
print(z[-1]-z[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
x1, y1 = map(int, input().split())
centre = [x1, y1]

left_bottom = [x1, y1]
left_bottom_dist = 0

left_top = [x1, y1]
left_top_dist = 0

right_bottom = [x1, y1]
right_bottom_dist = 0

right_top = [x1, y1]
right_top_dist = 0

for i in range(N-1):
  xi, yi = map(int, input().split())
  if xi <= x1 and yi <= y1:
    if x1 - xi + y1 - xi >= left_bottom_dist:
      left_bottom = [xi, yi]
      left_bottom_dist = x1 - xi + y1 - xi
  if xi <= x1 and yi >= y1:
    if x1 - xi + yi - y1 >= left_top_dist:
      left_top = [xi, yi]
      left_top_dist = x1 - xi + yi - y1
  if xi >= x1 and yi <= y1:
    if xi - x1 + y1 - yi >= right_bottom_dist:
      right_bottom = [xi, yi]
      right_bottom_dist = xi - x1 + y1 - yi 
  if xi >= x1 and yi >= y1:
    if xi - x1 + yi - y1 >= right_top_dist:
      right_top = [xi, yi]
      right_top_dist = xi - x1 + yi - y1

D1 = abs(right_top[0] - left_bottom[0]) + abs(right_top[1] - left_bottom[1])
D2 = abs(right_bottom[0] - left_top[0]) + abs(right_bottom[1] - left_top[1])
D3 = abs(left_top[0] - left_bottom[0]) + abs(left_top[1] - left_bottom[1])
D4 = abs(right_top[0] - right_bottom[0]) + abs(right_top[1] - right_bottom[1])
D5 = abs(left_top[0] - right_top[0]) + abs(left_top[1] - right_top[1])
D6 = abs(left_bottom[0] - right_bottom[0]) + abs(left_bottom[1] - right_bottom[1])

print(max(D1, D2, D3, D4, D5, D6))
print(left_bottom, left_top, right_bottom, right_top)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for _ in range(n):
  x,y=map(int,input().split( ))
  a.append(x+y)
a.sort()
i=0
j=n-1
ans=0
while i<j:
  ans=max(ans,abs(a[j]-a[i]))
  i+=1
  j-=1
if n&1:
  try:
    ans=max(ans,a[i]-a[i-1],a[i+1]-a[i])
  except:
    pass
print(ans)

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    for i in range(n):
        x,y = invr()
        q = max(q,x + y)
        qq = max(qq,x - y)
        w = min(w,x + y)
        ww = min(ww,x - y)
    print(max(q - w,qq - ww))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x,y = map(int,input().split())
minx, miny = x,y
maxx, maxy = x,y
maxdist = 0
for i in range(N-1):
  x,y = map(int,input().split())
  dist1 = abs(minx - x) + abs(miny - y)
  dist2 = abs(maxx - x) + abs(maxy - y)
  if dist1 > maxdist:
    maxx = x
    maxy = y
    maxdist = dist1
  elif dist2 > maxdist:
    minx = x
    miny = y
    maxdist = dist2
    
print(maxdist)

Submission status: Wrong Answer

Solution code:
n=int(input())

minx=10**6
maxx=-10**6
miny=10**6
maxy=-10**6

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

    maxx=max(maxx,x+y)
    minx=min(minx,x+y)
    maxy=max(maxy,x-y)
    miny=min(miny,x-y)

print(max(maxx-minx,maxy-miny))