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:
n = int(input())
X = []
Y = []
for i in range(n):
    x,y = map(int, input().split())
    x,y = x-y,x+y
    X.append(x)
    Y.append(y)

a = max(Y) - min(Y)
b = max(X) - min(X)

print(max(a,b))

Submission status: Accepted

Solution code:
n = int(input())
maxPlus, minPlus, maxMinus, minMinus = 0, 10**9 , -10**9, 10**9
for _ in range(n):
    x, y = map(int, input().split())
    maxPlus = max(x + y, maxPlus)
    minPlus = min(x + y, minPlus)
    maxMinus = max(x - y, maxMinus)
    minMinus = min(x - y, minMinus)
print(max(abs(maxPlus - minPlus), abs(maxMinus - minMinus)))

Submission status: Accepted

Solution code:
#E
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]

Cx=[0 for i in range(N)]
Cy=[0 for i in range(N)]

for i in range(N):
    x[i],y[i]=map(int,input().split())
    Cx[i]=x[i]+y[i]
    Cy[i]=x[i]-y[i]
    
ans=max(max(Cx)-min(Cx),max(Cy)-min(Cy))
print(ans)

Submission status: Accepted

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

for i in range(n):
  buf = x[i]
  x[i] = x[i]+y[i]
  y[i] = buf-y[i]

dx = max(x) - min(x)
dy = max(y) - min(y)
  
print(max(dx,dy))

Submission status: Accepted

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

ans = 0
for i in range(4):
  mi = l[i][0]
  for j in range(n):
    mi = min(mi, l[i][j])
    ans = max(ans, l[i][j] - mi)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

f0 = []
f1 = []
for _ in range(N):
    x, y = list(map(int, input().split()))
    f0.append(x-y)
    f1.append(x+y)
max_0 = max(f0)
max_1 = max(f1)
min_0 = min(f0)
min_1 = min(f1)
print(max(max_0-min_0, max_1-min_1))

Submission status: Accepted

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

N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

d1 = []
d2 = []
for x, y in xy :
  d1.append(x + y)
  d2.append(x - y)

d1.sort(reverse=True)
d2.sort(reverse=True)

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

Submission status: Accepted

Solution code:
N = int (input())
x = []*N
y = []*N
for i in range (N):
    a,b = list(map(int,input().split()))
    x.append(a)
    y.append(b)
syou = x[0]+y[0]
dai = x[0]+y[0]
for i in range (N):
    if x[i]+y[i]>dai:
        dai = x[i]+y[i]
    if x[i]+y[i]<syou:
        syou = x[i]+y[i]
ans = dai - syou
gyakusyou = 10**9 -x[i] +y[i]
gyakudai = 10**9 -x[i] + y[i]
for i in range (N):
    if 10**9 -x[i] +y[i]>gyakudai:
        gyakudai = 10**9 -x[i] +y[i]
    if 10**9 -x[i] +y[i]<gyakusyou:
        gyakusyou = 10**9 -x[i] +y[i]
if gyakudai - gyakusyou > ans:
    ans = gyakudai - gyakusyou
print (ans)

Submission status: Accepted

Solution code:
n = int(input())
p = []
for _ in range(n):
    x,y = map(int,input().split())
    p += [(x,y)]
p.sort()


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


ans = 0
q = set()
pmax = p[0]
pmin = p[0]
for i in range(1, n):
    for point in q:
        ans = max(ans, dist(point, p[i]))
    ans = max(ans, dist(p[i], pmax), dist(p[i], pmin))
    if pmax[1] < p[i][1]:
        q.add(pmax)
        pmax = p[i]
    if pmin[1] > p[i][1]:
        q.add(pmin)
        pmin = p[i]

    qrem = set()
    for point in q:
        if pmin[0]-point[0] <= point[1]-pmin[1] and pmax[0]-point[0] <= pmax[1]-point[1]:
            qrem.add(point)
    q -= qrem

print(ans)

Submission status: Accepted

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(max(i)-min(i), max(j)-min(j)))

Submission status: Accepted

Solution code:
import numpy as np

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

XpY = XY_set[:, 0] + XY_set[:, 1]
XmY = XY_set[:, 0] - XY_set[:, 1]

ans = max(XpY.max() - XpY.min(), XmY.max() - XmY.min())
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    points = [list(map(int, input().split())) for _ in range(N)]
    ks = [x + y for x, y in points]
    ls = [x - y for x, y in points]
    kk = max(ks) - min(ks)
    ll = max(ls) - min(ls)
    print(max(kk, ll))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

p1 = []
p2 = []
p3 = []

for i in range(N):
    p1.append(xy[i][0] + xy[i][1])
    p2.append(xy[i][0] - xy[i][1])
    p3.append(-xy[i][0] + xy[i][1])

p1_r = max(p1) - min(p1)
p2_r = max(p2) - min(p2)
p3_r = max(p3) - min(p3)

print(max(p1_r, p2_r, p3_r))

Submission status: Accepted

Solution code:
n=int(input())
p=[]
m=[]
bb=0
tt=False
for i in range(n):
    x,y=list(map(int,input().split()))
    p.append(x+y)
    m.append(x-y)
    bb+=1

minp=min(p)
maxp=max(p)
minm=min(m)
maxm=max(m)

ans=[maxp-minp,maxm-minm,minm,maxm,minp-maxp]
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
Array1 = []
Array2 = []

for i in range(N):
    next_x, next_y = map(int, input().split())
    s = next_x + next_y
    t = next_x - next_y
    Array1.append(s)
    Array2.append(t)

print(max(max(Array1)-min(Array1),max(Array2)-min(Array2)))

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())
ps = set()
for _ in range(N):
  ps.add(tuple(map(int, input().split())))
ps = list(ps)
ps.sort()

def cross3(a, b, c):
  return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def cross(a, b, c, d):
  return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
  qs = []
  N = len(ps)
  for p in ps:
    # 一直線上で高々2点にする場合は ">=" にする
    while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  t = len(qs)
  for i in range(N-2, -1, -1):
    p = ps[i]
    while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  return qs

# キャリパー法(Rotating Calipers法)
# 凸多角形を回転しながら走査し、最遠点対を求める
def dist(a, b):
  return abs(a[0]-b[0]) + abs(a[1]-b[1])

def rotating_calipers(ps):
  qs = convex_hull(ps)
  n = len(qs)
  if n == 2:
    return dist(qs[0], qs[1])
  i = j = 0
  for k in range(n):
    if qs[k] < qs[i]: i = k
    if qs[j] < qs[k]: j = k
  res = 0
  si = i; sj = j
  while i != sj or j != si:
    res = max(res, dist(qs[i], qs[j]))
    if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
      i = (i + 1) % n
    else:
      j = (j + 1) % n
  return res

if len(ps) == 1:
  print(0)
elif len(ps) == 2:
  print(dist(ps[0], ps[1]))
else:
  print(rotating_calipers(ps))