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())
ps = [list(map(int, input().split())) for _ in range(N)]
ps.sort()

# 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

print(rotating_calipers(ps))

Submission status: Time Limit Exceeded

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

ans = abs(a[0]-a[1]) + abs(b[0]-b[1])

for i in range(n-1):
    for j in range(1, n):
        tmp = abs(a[i]-a[j]) + abs(b[i]-b[j])
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#def input():
    #return sys.stdin.readline()[:-1]
N = int(input())
x=[0]*N
y=[0]*N
for i in range(N):
    xy=list(map(int,input().split()))
    x[i]=xy[0]
    y[i]=xy[1]
d=0
for i in range(N):
    for j in range(i+1, N):
        d=max(abs(x[i]-x[j])+abs(y[i]-y[j]), d)
print(d)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
z=[]
for i in range(t):
      a,b=map(int,input().split())
      z.append([a,b])
k=[0]      
for i in z:
      for j in z:
            if(i!=j):
                  k.append(abs(j[0]-i[0])+abs(j[1]-i[1]))
print(max(k))

Submission status: Time Limit Exceeded

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

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


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


print(rotating_calipers(p))

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
mx = - float("inf")
nums=[]
for _ in range(N):
  nums.append(list(map(int,input().split())))
for i in range(N-1):
  for d in range(i+1,N):
    mx = max(mx,abs(nums[i][0]-nums[d][0])+abs(nums[i][1]-nums[d][1]))
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys
input= sys.stdin.readline
N = int(input())
l = [tuple(map(int, input().split())) for i in range(N)]
d=list()
for i in range(N):
    for j in range(N):
        d.append(abs(l[i][0]-l[j][0]) + abs(l[i][1]-l[j][1]))
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
import sys  # def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)

n = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(n)]
XY.sort()

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area

def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

ans = 0
if n < 5:
    plist = XY
else:
    plist = convex_hull(XY)
for a, b in combinations(plist, 2):
    ans = max(ans, dist(a, b))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = []
_max = 0
for i in range(N):
    d.append(list(map(int, input().split(' '))))
    if i == 0:
        continue
    for j in range(i):
        if i == j:
            continue
        tmp = abs(d[i][0] - d[j][0]) + abs(d[i][1] - d[j][1])
        if tmp > _max:
            _max = tmp
print(_max)

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
xy = [readInts() for _ in range(n)]
ans = 0
for i in range(n-1):
    x1,y1 = xy[i]
    for j in range(i+1,n):
        x2, y2 = xy[j]
        ans = max(ans, abs(x1-x2) + abs(y1 - y2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTreeLayer:
    def __init__(self, segsize, function, upper_layer=None, lower_layer=None):
        self.data = []
        self.segsize = segsize
        self.function = function
        self.upper_layer = upper_layer
        self.lower_layer = lower_layer

    def update(self, i, value):
        self.data[i] = value

        if not self.upper_layer: return
        v_upper = vi = self.data[i]
        
        j = i-1 if i&1 else i+1
        if j<len(self.data):
            vj = self.data[j]
            v_upper = self.function(vi, vj)
            
        self.upper_layer.update(i//2, v_upper)

    def query(self, ibgn, iend):
        if ibgn%self.segsize==0 and iend-ibgn==self.segsize:
            return self.data[ibgn//self.segsize]

        imid = (ibgn//self.segsize)*self.segsize + self.segsize//2
        if iend<=imid or imid<=ibgn: return self.lower_layer.query(ibgn, iend)
        return self.function(
            self.lower_layer.query(ibgn, imid),
            self.lower_layer.query(imid, iend)
        )

    def extend(self, add, fill):
        self.data.extend([fill]*add)
        ndata = len(self.data)
        ndata_upper_new = (ndata+1)//2 if ndata>1 else 0
        
        if not self.upper_layer and ndata_upper_new>0:
            self.upper_layer = SegTreeLayer(
                self.segsize*2, self.function, lower_layer=self)

        if self.upper_layer:
            ndata_upper_now = len(self.upper_layer.data)
            return self.upper_layer.extend(ndata_upper_new - ndata_upper_now, fill)

        return self

class SegTree:
    def __init__(self, N, fill, function):
        self.bottom = SegTreeLayer(1, function)
        self.top = self.bottom.extend(N, fill)

    def update(self, i, value):
        self.bottom.update(i, value)

    def query(self, ibgn, iend):
        return self.top.query(ibgn, iend)

N = int(input())
INF = 10**10
XY = [tuple(map(int, input().split())) for _ in range(N)]

P = sorted(XY)

setY = {y for x, y in P}
iY = {y:i for i, y in enumerate(sorted(list(setY)))}

ans1 = 0
S = SegTree(len(iY), INF, min)

for x, y in P:
    iy = iY[y]
    if S.bottom.data[iy]==INF: S.update(iy, x+y)
    
    t = S.query(0, iy+1)
    if t!=INF: ans1 = max(ans1, x+y-t)

############################
    
P = sorted([(x, 10**9+1-y) for x, y in XY])
setY = {y for x, y in P}
iY = {y:i for i, y in enumerate(sorted(list(setY)))}

ans2 = 0
S = SegTree(len(iY), INF, min)

for x, y in P:
    iy = iY[y]
    if S.bottom.data[iy]==INF: S.update(iy, x+y)
    
    t = S.query(0, iy+1)
    if t!=INF: ans2 = max(ans2, x+y-t)

print(max(ans1, ans2))

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=list(combinations(charo,2))
maximun=0
result=[abs(j[0][0]-j[1][0])+abs(j[0][1]-j[1][1]) for j in wan ]
print(max(result))

Submission status: Time Limit Exceeded

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

ans=0
for i in range(n):
    for k in range(n):
        dis = abs(lo[i][0]-lo[k][0])+abs(lo[i][1]-lo[k][1])
        if dis>ans:
            ans=dis
        
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

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

if n == 2:
    point.append(point[1])
point = convex_hull(point)
ans = 0
for i in range(len(point)):
    for j in range(len(point)):
        if i != j:
            ans = max(ans, abs(point[i][0] - point[j][0]) + abs(point[i][1] - point[j][1]))
print(ans)

Submission status: Time Limit Exceeded

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

# coding: utf-8


def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

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 = 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: 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)

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

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


print(rotating_calipers(p))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
data = [input().split() for i in range(n)]
max = 0
for i in range(n):
    for j in range(i+1,n):
        a = abs(int(data[i][0]) - int(data[j][0])) + abs(int(data[i][1]) - int(data[j][1]))
        if max < a:
            max = a

print(max)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())
    data = []
    ans = 0
    for i in range(n):
        row = [int(x) for x in input().rstrip().split(" ")]
        for (x, y) in data:
            dist = abs(x - row[0]) + abs(y - row[1])
            if ans < dist:
                ans = dist
        data.append(row)

    print(ans)


if __name__ == "__main__":
    resolve()

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ps = []
for i in range(n):
    a,b = map(int,input().split())
    ps.append((a,b))

ps.sort()

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

def dist(a,b):
    val = abs(a[0] - b[0]) + abs(a[1] - b[1])
    return val
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
print(rotating_calipers(ps))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.spatial.distance import minkowski
import itertools
n=int(input())
l=[]
a = []
for i in range(n):
    l.append(list(map(int,input().split())))
for v in itertools.combinations(l, 2):
    a.append(minkowski( v[0],v[1] , 1 ))
print(int(max(a)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
n = int(input())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]

@jit
def main(x,y):
    a=[]
    b=[]
    for i in range(len(x)):
        for j in range(i+1,len(x)):
            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(b+c)])

main(x,y)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
zahyo=[[],[]]*N
big=0
for i in range(0,N):
    zahyo[i]=list(map(int,input().split()))
    for j in range(0,i):
        if i==0:
            break
        jj=abs(zahyo[i][0]-zahyo[j][0])+abs(zahyo[i][1]-zahyo[j][1])
        if jj>big:
            big=jj
print(big)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
a=[]
for i in range(num):
   temp = input().split() 
   temp = [int(n) for n in temp]
   a.append(temp)
   
b=[]
for i in range(num):
    for j in range(i+1,num):
        tem1 = a[i][0]-a[j][0]
        if(tem1<0):
            tem1 = -tem1
        tem2 = a[i][1]-a[j][1]
        if(tem2<0):
            tem2 = -tem2
        b.append(tem1+tem2)

b.sort(reverse=True)
print(b[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

table_p = {}
table_m = {}

points = []
for _ in range(N):
	x, y = map(int, input().split())
	points.append((x, y))
	a = x + y
	b = x - y
	if a in table_p:
		table_p[a].append((x, y))
	else:
		table_p[a] = [(x, y)]
	if b in table_m:
		table_m[b].append((x, y))
	else:
		table_m[b] = [(x, y)]

list_p = []
list_m = []
for a, ps in table_p.items():
	list_p.append((a, ps[0]))

for b, ps in table_m.items():
	list_m.append((b, ps[0]))

list_p.sort()
list_m.sort()

topvalue = 0

for x, y in points:
	topvalue = max(topvalue, 
		m_dis(x, y, list_p[0][1][0], list_p[0][1][1]),
		m_dis(x, y, list_p[-1][1][0], list_p[-1][1][1]),
		m_dis(x, y, list_m[0][1][0], list_m[0][1][1]),
		m_dis(x, y, list_m[-1][1][0], list_m[-1][1][1]))

print(topvalue)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy_list = []
ans = 0

for _ in range(n):
    xy_list.append(list(map(int, input().split())))

for index, xy in enumerate(xy_list):
    for xy_next in xy_list[index+1:]:
        ans = max(abs(xy_next[0]-xy[0])+abs(xy_next[1]-xy[1]), ans)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)
d = 0
for i in range(N):
    for j in range(i+1, N):
        w = abs(x[i] - x[j]) + abs(y[i] - y[j])
        if w > d:
            d = w
print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = []
for i in range(N):
    s = [int(i) for i in input().split()]
    P.append(s)

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

print(L)

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)]

length = 0
temp = 0

for i in range(N):
  for j in range(N):
    temp = abs(x[i] - x[j]) +abs(y[i] - y[j])
    
    if temp > length:
      length = temp
      
print(length)

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()))))

li = 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())
xlist=[]
ylist=[]
for i in range(n):
    x,y=map(int,input().split())
    flag=0
    for j in range(len(xlist)):
        flag=0
        if xlist[j]==x:
            if ylist[j]==y:
                flag=1
                break
            else:
                xlist.append(x)
                ylist.append(y)
                flag=1
    if flag==0:
        xlist.append(x)
        ylist.append(y)
        
n=len(xlist)
ans=0
for i in range(n):
    for j in range(i+1,n):
        val=abs(xlist[j]-xlist[i])+abs(ylist[j]-ylist[i])
        #print("val:",val)
        ans=max(val,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xx = 0
yy = 0
max_distance = -1
xlist = []
ylist = []


for i in range(n):
    x, y = map(int,input().split())
    xlist.append(x)
    ylist.append(y)
    
for i in range(n):
    xx = xlist[i]
    yy = ylist[i]
    for i in range(n):
        z = abs(xx - xlist[i]) + abs(yy - ylist[i])
        if max_distance < z:
            max_distance = z

print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

def e():
    
    @lru_cache(maxsize=None)
    def check(j, a):
        return abs(j[0] - a[0]) + abs(j[1] - a[1])
    
    s = set()
    res = 0
    N = int(input())
    for i in range(N):
        a = tuple(map(int, input().split()))
        for j in s:
            res = max(res, check(j,a))
        s.add(a)
        
    print(res)
    
    
e()

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)

xy = zip(x,y)
xy = sorted(xy)
x,y = zip(*xy)

ps = []

for i in range(n):
    ps.append((x[i],y[i]))

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

def dist(a,b):
    val = abs(a[0] - b[0]) + abs(a[1] - b[1])
    return val
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
print(rotating_calipers(ps))

Submission status: Time Limit Exceeded

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

print(max(b))

Submission status: Time Limit Exceeded

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

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)])
  

dis=[]
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])
    
    dis.append(x_dis + y_dis)
      
print(max(dis))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

xa = []
ya = []

for i in range(N):
  x, y = map(int, input().split())
  xa.append(x)
  ya.append(y)
  
max = abs(xa[1] - xa[0]) + abs(ya[1] - ya[0])

if (N > 2):
  for i in range(N):
    for j in range(i):
      if abs(xa[i] - xa[j]) + abs(ya[i] - ya[j]) > max:
        max = abs(xa[i] - xa[j]) + abs(ya[i] - ya[j])
      
print(max)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())
points = []
dist = 0
for _ in range(n):
  points.append(tuple(map(int, input().split())))
for (x1, y1), (x2, y2) in combinations(points, 2):
  if dist < abs(x1-x2) + abs(y1-y2):
    dist = abs(x1-x2) + abs(y1-y2)
print(dist)