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: Time Limit Exceeded

Solution code:
n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
ans=0
for i in range(0,n-1):
    for j in range(i+1,n):
        d=abs(data[i][0]-data[j][0])+abs(data[i][1]-data[j][1])
        ans=max(ans,d)
print(ans)

Submission status: Time Limit Exceeded

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):
    for j in range(i + 1, n):
        a = lst[i][0] - lst[j][0]
        b = lst[i][1] - lst[j][1]
        if abs(a) + abs(b) in result:
            continue
        result.append(abs(a) + abs(b))

print(max(result))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
x_list = [] 
for i in range(n):
    x_1, x_2 = map(int, input().split())
    x_list.append([x_1, x_2])

max_val = 0

for i, l in enumerate(x_list):
    x_list_i = x_list[i]
    if i == len(x_list):
        continue
    else:
        for j in range(i+1,len(x_list)):
            x_list_j = x_list[j]
            val = np.abs(x_list_i[0]-x_list_j[0]) + np.abs(x_list_i[1]-x_list_j[1])

            if val > max_val:
                max_val = val

print (max_val)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

XY=[]
for i in range(N):
    x,y=input().split()
    XY.append((int(x),int(y)))
    
Md=[]

for s in range(N):
    for t in range(N):
        d=abs(XY[s][0]-XY[t][0])+abs(XY[s][1]-XY[t][1])
        Md.append(d)

print(max(Md))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a=[]
b=[]
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
for i in range(n):
    for j in range(i+1,n):
    	a.append(abs(x[j]-x[i]))
    	b.append(abs(y[j]-y[i]))
a_n = np.array(a)
b_n = np.array(b)
c = a_n+b_n
print(c[np.argmax(c)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = set()
for _ in range(N):
    x, y = map(int, input().split())
    p.add((x, y))
p = list(p)

res = 0
for x, y in p:
    p.sort(key=lambda i: abs(i[0] - x) + abs(i[1] - y))
    res = max(res, abs(x - p[-1][0]) + abs(y - p[-1][1]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
def manhattan(a,b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

if __name__ == "__main__":
    N = int(input())
    ans = float("-inf")
    pos_arr = [tuple(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ans = max(manhattan(pos_arr[i],pos_arr[j]),ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# キャリパー法ってのが見つかったのでやってみる

# ps = [(x, y), ...]: ソートされた座標list
def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        # 一直線上で高々2点にする場合は ">=" にする
        while len(qs)>1 and cross(qs[-1], qs[-2], qs[-1], 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 cross(qs[-1], qs[-2], qs[-1], 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

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

print(rotating_calipers(ps))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
location = set()
for i in range(n):
  x, y = map(int, input().split())
  location.add((x, y))
location_list = list(location)
answer = 0
for i in range(len(location)):
  for j in range(len(location)):
    a = location_list[i]
    b = location_list[j]
    answer = max(answer, abs(a[0] - b[0]) + abs(a[1] - b[1]))
print(answer)

Submission status: Time Limit Exceeded

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):
    for j in range(i + 1, n):
        a = lst[i][0] - lst[j][0]
        b = lst[i][1] - lst[j][1]
        result.append(abs(a) + abs(b))

print(max(result))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
  
ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    a, b = np.array(l[i]), np.array(l[j])
    n = int(np.linalg.norm(a-b, ord=1))
    ans = max(ans, n)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int,input().split())))
max = 0
for xy1 in xy:
  for xy2 in xy:
    dis = abs(xy1[0]-xy2[0]) + abs(xy1[1]-xy2[1])
    if dis > max:
      max = dis
print(max)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
node = {}
for i in range(n):
    x, y = map(int, input().strip().split())
    if x in node.keys():
        if y < node[x][0]:
            node[x][0] = y
        elif y > node[x][1]:
            node[x][1] = y
    else:
        node[x] = [y, y]
res = 0

for key1, value1 in node.items():
    for key2, value2 in node.items():
        manhattan = abs(key1 - key2) + abs(value1[0] - value2[1])
        if res < manhattan:
            res = manhattan

print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def manhat(point1, point2):
    return(abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]))
N = int(stdin.readline())
points = set()
maxs = 0
for i in range(N):
    x, y = map(int, stdin.readline().split())
    for point1 in points:
        if manhat(point1, (x,y)) > maxs:
            maxs = manhat(point1, (x,y))
    points.add((x, y))
print(maxs)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

X=[]
Y=[]

for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)

dp=[-1]*N #点iと他の点との間で最長のマンハッタン距離を格納。

a=min(X)
b=max(X)
c=min(Y)
d=max(Y)

for i in range(N):
    if dp[i]!=-1:
        continue
    if 2*a < X[i] < b//2 and c*2 < Y[i] < d//2:
        continue
    dist=0
    ind=-1
    for j in range(i+1,N):
        tmp = abs(X[i]-X[j])+abs(Y[i]-Y[j])
        if dist < tmp:
            dist = tmp
            ind = j
    dp[i]=dist
    dp[j]=dist
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x, y = [], []
for i in range(n):
	tempx, tempy = map(int, input().split())
	x.append(tempx)
	y.append(tempy)
dist = []
for i in range(n):
	for j in range(i+1, n):
		dist.append(abs(x[i] - x[j]) + abs(y[i] - y[j]))
print(max(dist))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
dots=[]
for i in range(n):
  x,y = input().split()
 
  dots.append([int(x),int(y)])
  
max_dis=0
for i, dot_1 in enumerate(dots):
  for dot_2 in dots[i:]:
    x_dis = abs(dot_1[0]-dot_2[0])
    y_dis = abs(dot_1[1]-dot_2[1])
    
    tmp_dis = x_dis + y_dis
    if max_dis < tmp_dis:
      max_dis = tmp_dis
      
print(max_dis)

Submission status: Time Limit Exceeded

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 = [],[]
allPOints = []
for _ in range(n):
    x,y = readIntList()
    allPOints.append([x,y])

res = float('-inf')
for i in range(len(allPOints)):
    for j in range(i+1,len(allPOints)):
        res = max(res,abs(allPOints[i][0]-allPOints[j][0]) + abs(allPOints[i][1]-allPOints[j][1]))

print(res)

Submission status: Time Limit Exceeded

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

a = 0
for i in range(0,n):
    for j in range(i+1,n-i):
        c = abs(x[i] - x[i + j]) + abs(y[i] - y[i + j])
        if a >= c:
            a = a
        else:
            a = c
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
charo=[]
for i in range(int(input())):
    x,y=list(map(int,input().split()))
    charo.append([x,y])
wan=combinations(charo,2)
result=[]
for j in list(wan):
    cal=abs(j[0][0]-j[1][0])+abs(j[0][1]-j[1][1])
    result.append(cal)
print(max(result))

Submission status: Time Limit Exceeded

Solution code:
from scipy.spatial import ConvexHull
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

# 直線状か判定
isline = True
x1, y1 = dots[0]
x2, y2 = dots[1]
for i in range(2, N):
    x3, y3 = dots[i]
    isline &= (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1)

if not isline:
    hull = ConvexHull(dots).points + 0.1

    dots = np.array(hull, dtype=np.int64).tolist()
    M = len(dots)

    ans = 0
    for i in range(M-1):
        xi, yi = dots[i]
        for j in range(i + 1, M):
            xj, yj = dots[j]
            ans = max(ans, abs(xi - xj) + abs(yi - yj))
    print(ans)
else:
    dots.sort()
    xi, yi = dots[0]
    xj, yj = dots[-1]
    print(abs(xi - xj) + abs(yi - yj))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
N = int(input())
Z = [list(map(int,input().split())) for _ in range(N)]
ans = 0
for x in itertools.combinations(Z,2):
  ans = max(ans, abs(x[0][0]-x[1][0])+abs(x[0][1]-x[1][1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt


class Vector:
    def __init__(self, ls):
        '''
        ls ... list
        '''
        self.vec = ls

    def __len__(self):
        return len(self.vec)

    def __getitem__(self, idx):
        return self.vec[idx]

    def __repr__(self):
        return f'Vector({self.vec})'

    def add(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a + b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def sub(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a - b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def mul(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a * b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)
    def norm(self):
        tmp = sum([x * x for x in self.vec])
        return sqrt(tmp)


def norm(vec):
    '''
    vec ... Vector class
    '''
    return vec.norm()


def cross(a, b):
    '''
    Outer product for 2d
    a,b ... Vector class
    '''
    assert len(a) == 2 and len(b) == 2
    first = a[0] * b[1]
    second = a[1] * b[0]
    return first - second


def dot(a, b):
    return sum(a.mul(b))


EPS = 1e-10


def is_ccw(p0, p1, p2):
    '''
    p1-p0に対してp2-p0が`基本的に`反時計回りならばTrueを返す。
    同一直線上にあってもconvex hulをつくるのには含めて良いので、popする必要はない、したがってFalseをァ得すことにする
    '''
    a = p1.sub(p0)
    b = p2.sub(p0)
    if cross(a, b) > EPS:
        # 'COUNTER_CLOCKWISE'
        return True
    else:
        return False
        # 時計回り、同一直線上の場合,popする必要はないのでFalse
    # # つまり下記のようなこと
    # elif cross(a, b) < -EPS:
    #     # 'CLOCKWISE'
    #     return False
    # else:
    #     return False  # 同一直線上にあるとかそういう場合


# andrewのアルゴリズムで凸包を求める。
# このアルゴリズムの挙動はP403を見るとわかりやすい。
# また凸包でなくなったときに点を取り除いていく作業はP402の下から7行目に示しされている。

def convex_hull(points: list):
    points.sort(key=lambda x: (x[0], x[1]))
    if len(points) < 3:
        # 点が2点しかないならば線しかないが、
        # 今回は制約によりこうなる状況はないので無視する。
        pass

    # 凸包の上部(イメージはP403の図)
    conv_upper = [points[0], points[1]]  # 初期値として最初の二点が与えられます。
    for p in points[2:]:
        # 反時計回りである限りは
        while len(conv_upper) >= 2 and is_ccw(conv_upper[-2], conv_upper[-1], p):
            # conv_upper[-1]は凸包を作る点ではないので捨てる
            conv_upper.pop()
        conv_upper.append(p)

    # 凸包の下部
    points = points[::-1]
    conv_lower = [points[0], points[1]]
    for p in points[2::]:
        # 反時計回りである限りは
        while len(conv_lower) >= 2 and is_ccw(conv_lower[-2], conv_lower[-1], p):
            conv_lower.pop()
        conv_lower.append(p)

    # また、出力は反時計回りにしたい。
    # conv_upperもconv_lowerも時計回りになっているので結合して引っくり返せばよい
    # ただしアルゴリズムの性質上、ソートしたときに端にある点はだぶるので削除する
    ret = conv_upper[1:-1] + conv_lower

    return ret[::-1]

# load data
N = int(input())
points = []
for _ in range(N):
    points.append(Vector(list(map(int, input().split()))))

ans = convex_hull(points)

# print result
# 凸多角形の頂点で最も下にあるものの中でもっとも左にある頂点から順に、反時計回りで出力してくださいというのが一番面倒
li = []
for i in ans:
  li.append(tuple(i))

m = 0
for i in range(len(li)):
    for j in range(i, len(li)):
      if i==j:
          continue
      m = max(m, abs(li[i][0]-li[j][0])+abs(li[i][1]-li[j][1]))
print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def kyori(xi, yi, xj, yj):
    s = abs(xi - xj) + abs(yi - yj)
    return s

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

l = 0
for i in range(N):
    for j in range(N):
        a = kyori(x[i], y[i], x[j], y[j])
        if a > l:
            l = a
print(l)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
num=[list(map(int,input().split())) for _ in range(n)]
n1=[]
num1=10**9
ans=0
for i in range(n):
    n1.append(num[i][0]+num[i][1])
    ans=max(ans,max(n1)-min(n1))
n1=[]
for i in range(n):
    n1.append(num1-num[i][0]+num[i][1])
    ans=max(ans,max(n1)-min(n1))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

cand = []
for i in (-1,0,1):
    for j in (-1,0,1):
        points.sort(key = lambda x: i*x[0] + j*x[1])
        cand.append(points[0])
outs = []
for i in cand:
    for p in points:
        outs.append(dist(i,p))
print(max(outs))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data_x  = []
data_y = []
res = []

for i in range(N):
    a, b = map(int, input().split())
    data_x.append(a)
    data_y.append(b)

for i in range(N):
    for j in range(i + 1, N):
        x = abs(data_x[i] - data_x[j])
        y = abs(data_y[i] - data_y[j])
        r = x + y
        res.append(r)

X = max(res)
print(X)

Submission status: Time Limit Exceeded

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

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

cand = []
for i in (-1,0,1):
    for j in (-1,0,1):
        points.sort(key = lambda x: i*x[0] + j*x[1])
        cand.append(points[0])
outs = []
for i in cand:
    for p in points:
        outs.append(dist(i,p))
print(max(outs))

Submission status: Time Limit Exceeded

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

a = 0
b = []
for i in range(0,n):
    for j in range(i+1,n-i):
        c = abs(x[i] - x[i + j]) + abs(y[i] - y[i + j])
        b.append(c)
print(max(b))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
coords = []
maxlength = 0
for i in range(n):
  (x_i, y_i) = [int(x) for x in input().split(' ')]
  for coord in coords:
    manhtn = abs(coord[0] - x_i) + abs(coord[1] - y_i)
    if manhtn > maxlength:
      maxlength = manhtn
  coords.append((x_i, y_i))
print(maxlength)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

X=[]
Y=[]

for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)

dp=[-1]*N #点iと他の点との間で最長のマンハッタン距離を格納。

for i in range(N):
    if dp[i]!=-1:
        continue
    dist=0
    ind=-1
    for j in range(i+1,N):
        tmp = abs(X[i]-X[j])+abs(Y[i]-Y[j])
        if dist < tmp:
            dist = tmp
            ind = j
    dp[i]=dist
    dp[j]=dist
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l = list()

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

max_dist = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        max_dist = max(max_dist, abs(l[i][0]-l[j][0]) + abs(l[i][1]- l[j][1]))
print(max_dist)

Submission status: Time Limit Exceeded

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

N = int(input())
points = []
for a in range(N):
    chi = input().split()
    child = (int(chi[0]), int(chi[1]))
    points.append(child)


ress = []

for qwerty in range(N-1):
    for uiop in range(qwerty, N):
        ress.append(dist(points[qwerty], points[uiop]))

print(max(ress))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x + y)
    Y.append(x - y)
# print(X, Y)
ans = 0
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        tmp = max(abs(X[i] - X[j]), abs(Y[i] - Y[j]))
        ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

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

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(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def manhattann(x1,x2,y1,y2):
  return abs(x1-x2) + abs(y1-y2)

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

dist = list(set(dist))
_max = 0
n = len(dist)
for i in range(n-1):
  for j in range(i+1,n):
    _max = max(_max, manhattann(dist[i][0], dist[j][0], dist[i][1], dist[j][1]))

print(_max)

Submission status: Time Limit Exceeded

Solution code:
n = input()
n = int(n)

p = []
for i in range(n):
  x,y = map(int, input().split(' '))
  p.append([x, y])

md = -1
for i in range(len(p)-1):
  for j in range(i+1, len(p)):
    x1, y1 = p[i]
    x2, y2 = p[j]
    d = abs(x1-x2) + abs(y1-y2)
    d = int(d)
    md = max(md,d)
print(md)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i],y[i] = map(int,input().split())
ans = 0
for j in range(N):
    for k in range(N):
        if abs(x[j] - x[k]) + abs(y[j]-y[k]) > ans:
            ans = abs(x[j] - x[k]) + abs(y[j]-y[k])
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
i=0
for i in range(n-1):
    j=i+1
    while j<n:
        m=abs(data[i][0]-data[j][0])+abs(data[i][1]-data[j][1])
        ans=max(ans,m)
        j+=1

print(ans)

Submission status: Time Limit Exceeded

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())
xi = x[0] - x[1]
yi = y[0] - y[1]
if xi < 0:
  xi = -(xi)
if yi < 0:
  yi = -(yi)
max = xi + yi
for i in range(N):
  for j in range(N-i):
    xi = x[i] - x[j]
    yi = y[i] - y[j]
    if xi < 0:
      xi = -(xi)
    if yi < 0:
      yi = -(yi)
    if xi + yi > max:
      max = xi + yi
print(max)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
points = []
for i in range(n):
    points.append(list(map(int,input().split())))
max_dist = 0
for i in range(len(points)):
    for j in range(i+1,len(points)):
        max_dist = max(max_dist,abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]))
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
point = []
for _ in range(n):
    point.append((tuple(map(int, input().split()))))
point = set(point)
max_d = 0
for p in point:
    for q in point:
        d = abs(p[0] - q[0]) + abs(p[1] - q[1])
        if d > max_d:
            max_d = d
print(max_d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

N = int(sys.stdin.readline())
xy = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param

m = 0
for i in range(N):
    for j in range(i+1,N):
        m = max(m,abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(m)

Submission status: Time Limit Exceeded

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

ma = 0
for i in range(N):
    for j in range(i+1,N):
        if abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]) > ma:
            ma = abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1])

print(ma)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = max(ans, abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        d=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1])
        ans=max(ans,d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

lst = [[0, 0] for _ in range(N)]
d = 0
for i in range(N):
  x, y = map(int, input().split())
  lst[i][0] = x
  lst[i][1] = y
  
  for j in range(i):
    #print(lst[j], [x, y])
    d = max(d, abs(lst[j][0] - x)+abs(lst[j][1] - y))
  
print(d)

Submission status: Time Limit Exceeded

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

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

out = 0
for i in range(n):
    x1, y1 = pairs[i]
    for j in range(i+1, n):
        x2, y2 = pairs[j]
        cur = abs(x1-x2) + abs(y1-y2)
        out = max(cur, out)
print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

dots=[]
for i in range(n):
  x,y = input().split()

  dots.append([int(x),int(y)])
  
max_dis=0
for dot_1 in dots:
  for dot_2 in dots:
    x_dis = abs(dot_1[0]-dot_2[0])
    y_dis = abs(dot_1[1]-dot_2[1])
    
    tmp_dis = x_dis + y_dis
    if max_dis < tmp_dis:
      max_dis = tmp_dis
      
print(max_dis)

Submission status: Accepted

Solution code:
n=int(input())
zp=[]
zl=[]
for i in range(n):
    a,b=map(int,input().split())
    zp.append(a+b)
    zl.append(a-b)
ans=max((max(zp)-min(zp)),(max(zl)-min(zl)))
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


def func(x, m):
    return x % m


# 処理内容
def main():
    N = int(input())
    z = [0] * N
    w = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        z[i] = x + y
        w[i] = x - y
    
    ans = max(max(z) - min(z), max(w) - min(w))
    
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def main():
    n = int(input())
    z = [[], []]
    for i in range(n):
        x, y = map(int, input().split())
        z[0].append(x + y)
        z[1].append(x - y)
    z[0] = sorted(z[0])
    z[1] = sorted(z[1])
    print(max(z[0][-1] - z[0][0], z[1][-1] - z[1][0]))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

p_one = input()
p_one_list = p_one.split(' ')

zmax = int(p_one_list[0]) + int(p_one_list[1])
zmin = int(p_one_list[0]) + int(p_one_list[1])
wmax = int(p_one_list[0]) - int(p_one_list[1])
wmin = int(p_one_list[0]) - int(p_one_list[1])


for i in range(1, n):
    line = input()
    tmp = line.split(' ')
    z = int(tmp[0]) + int(tmp[1])
    w = int(tmp[0]) - int(tmp[1])
    zmax = max(zmax, z)
    wmax = max(wmax, w)
    zmin = min(zmin, z)
    wmin = min(wmin, w)


z_ans = zmax - zmin
w_ans = wmax - wmin


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

Submission status: Accepted

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

A=sorted(A)
B=sorted(B)

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

Submission status: Accepted

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

A=sorted(A)
B=sorted(B)

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

Submission status: Accepted

Solution code:
n = int(input())
point_dict1 = {}
point_dict2 = {}
for i in range(n):
    x, y = map(int, input().split())
    point_dict1[x + y] = (x, y)
    point_dict2[y - x] = (x, y)
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:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
a=[]
b=[]
for i in range(n):
  a.append(l[i][0]+l[i][1])
  b.append(l[i][0]-l[i][1])
print(max(max(a)-min(a),max(b)-min(b)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

Z=[]
W=[]

for _ in range(N):
    x,y=map(int,input().split())
    Z.append(x+y)
    W.append(x-y)
    
print(max(max(Z)-min(Z),max(W)-min(W)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

a.sort()
b.sort()

ans = max(a[-1]-a[0], b[-1]-b[0])
print(ans)

Submission status: Accepted

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

n=int(input())
a,b,c,d=-10**9,10**9,-10**9,10**9
for _ in range(n):
	x,y=map(int,input().split())
	a=max(a,x+y)
	b=min(b,x+y)
	c=max(c,x-y)
	d=min(d,x-y)
print(max(a-b,c-d))

Submission status: Accepted

Solution code:
n=int(input())
a,b,c,d=-10**9,10**9,-10**9,10**9
for _ in range(n):
	x,y=map(int,input().split())
	a=max(a,x+y)
	b=min(b,x+y)
	c=max(c,x-y)
	d=min(d,x-y)
print(max(a-b,c-d))

Submission status: Accepted

Solution code:
N = int(input())
A = []; B = []
for i in range(N):
  x,y = map(int,input().split())
  a = x+y; A.append(a)
  b = x-y; B.append(b)
A.sort();B.sort()
Max_A = A[-1] - A[0]
Max_B = B[-1] - B[0]
ans = max(Max_A,Max_B)
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    _x = []
    _y = []
    for _ in range(n):
        x, y = input_int_list()
		# 座標系を45度回転させて考える
        _x.append(x - y)
        _y.append(x + y)
	
    ans = max(max(_x) - min(_x), max(_y) - min(_y))

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
p = [[None] for i in range(N)]

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

p.sort()
#print(p)

INFINITE = 5 * 10**9
maxUp = {}
minDown = {}

for i in range(1, N):
    maxUp[i] = max(maxUp.get(i-1, -INFINITE), p[i-1][1] - p[i-1][0])
for i in range(1, N):
    minDown[i] = min(minDown.get(i-1, INFINITE), p[i-1][0] + p[i-1][1])

#print(maxUp)
#print(minDown)

ans = -INFINITE
for i in range(1, N):
    ans = max(ans, 
        p[i][0] - p[i][1] + maxUp.get(i, -INFINITE)
    )
    ans = max(ans, 
        p[i][0] + p[i][1] - minDown.get(i, INFINITE)
    )
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

x=[]
y=[]

for i in range(n):
  s,t=map(int,input().split())
  x.append(s+t)
  y.append(s-t)

print(max(max(x)-min(x),max(y)-min(y)))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=998244353
########################################################
n=int(input())
A=[]
for i in range(n):
    x,y=INPUT()
    a=x+y
    b=y-x
    A.append([a,b])
A.sort()
ans=0
maxiy=A[0][1]
miniy=maxiy
for i in range(n):
    ans=max(max(abs(A[i][0]-A[0][0]),max(abs(A[i][1]-maxiy),abs(A[i][1]-miniy))),ans)
    maxiy=max(maxiy,A[i][1])
    miniy=min(miniy,A[i][1])
print(ans)