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:
from math import sqrt
from functools import reduce

def convex_hull_graham(points):
  TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

#  def cmp(a, b):
#    return (a > b) - (a < b)
  def turn(p, q, r):
    a=(q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1])
    (a > 0) - (a < 0)
  def _keep_left(hull, r):
    while len(hull) > 1 and turn(hull[-2], hull[-1], r) == TURN_RIGHT:
      hull.pop()
    if not len(hull) or hull[-1] != r:
      hull.append(r)
    return hull
  points = sorted(points)
  l = reduce(_keep_left, points, [])
  u = reduce(_keep_left, reversed(points), [])
  return l.extend(u[i] for i in range(1, len(u) - 1)) or l


# Function to find the maximum 
# distance between any two points 
def maxDist(p): 
  n = len(p) 
  maxm = 0
  # Iterate over all possible pairs 
  for i in range(n): 
    for j in range(i + 1, n): 
      # Update maxm
      dist=  abs( p[i][0] - p[j][0])+abs( p[i][1] - p[j][1]) 
      maxm = max(maxm, dist) 
  # Return actual distance 
  #return sqrt(maxm) 
  return maxm
# Driver Code 
if __name__ == '__main__': 
  # Number of points 
  n=int(input())
  xy=[None]*n
  for i in range(n):
    xy[i]=list(map(int,input().split()))
  # Given points 
  # Function Call 
  xy=convex_hull_graham(xy)
  print(maxDist(xy))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
matrix = []
for i in range(n):
  a=[]
  for j in range(1):
    k = input()
    a= [int(i) for i in k.split()]
    matrix.append(a)
mu = []

while len(matrix)!=0:
  g=0
  while g != len(matrix):
    
    sum = abs(matrix[0][0]-matrix[g][0])+ abs(matrix[0][1]-matrix[g][1])
    mu.append(sum)
    g+=1
  matrix.remove(matrix[0])
  

print(max(mu))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ListN = [[0 for i in range(2)] for j in range(N)]

for i in range (N):
  x, y, = map(int, input().split())
  ListN[i] = [x,y]
  
ListN = list(map(list, set(map(tuple, ListN))))
m = 0
minN = ListN[0][0] + ListN[0][1]
maxN = ListN[0][0] + ListN[0][1]

for i in range (len(ListN)-1):
  flg = False
  if minN >= ListN[i][0] + ListN[i][1]:
    minN = ListN[i][0] + ListN[i][1]
    flg = True
  elif maxN <= ListN[i][0] + ListN[i][1]:
    maxN = ListN[i][0] + ListN[i][1]
    flg = True
  if flg:
    for j in range (i,len(ListN)):
     m = max(m, abs(ListN[i][0] - ListN[j][0]) + abs(ListN[i][1] - ListN[j][1]) )

print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
D = []
for i in range(N):
    D.append([int(a) for a in input().split()])
ans = 0
for i in range(N):
    for j in range(i+1,N):
        tmp = abs(D[i][0] - D[j][0]) + abs(D[i][1] - D[j][1])
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import math


N = int(input())

xy = []

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

s = 0
for i,(x,y) in enumerate(xy):
    for a,b in xy[i:]:
        s = max(s, abs(x-a)+abs(y-b))

print(s)

Submission status: Time Limit Exceeded

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

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

unique_xys = get_unique_list(xys)

max_list = []
max_dis = 0
for xy in unique_xys:
    dist = abs(xy[0]) + abs(xy[1])

    if(dist > max_dis):
        max_list = []
        max_list.append(xy)
        max_dis = dist

    elif(dist == max_dis):
        max_list.append(xy)

#print(max_list)

ans = 0

for siten in max_list:
    for syuten in unique_xys:
        dist = abs(siten[0] - syuten[0]) + abs(siten[1] - syuten[1])
        ans = max(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
xy.sort()
xy = [list(x) for x in zip(*xy)]
import copy
ans = 0
for i in range(N-1):
    w = xy.copy()
    x = list(map(lambda x: abs(x-xy[0][i]),w[0]))
    y = list(map(lambda y: abs(y-xy[1][i]),w[1]))
    z = [i+j for i,j in zip(x,y)]
    ans = max(ans,max(z))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Array = []
for i in range(N):
    next_x, next_y = map(int, input().split())
    Array.append([next_x,next_y])

def Chevdistaaa (xdist,ydist):
    xdists = xdist - ydist
    ydists = xdist + ydist
    return(xdists,ydists)


Array2 = []
Point1x = 0
Point1y = 0
Point2x = 0
Point2y = 0
for i in range(N):
    for j in range(N):
        Point1x = Array[i][0]
        Point1y = Array[i][1]
        Point2x = Array[j][0]
        Point2y = Array[j][1]
        Dist = abs(Point1x -  Point2x) + abs(Point1y - Point2y)
        Array2.append(Dist)

print(max(Array2))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
points = []
currentMax = 0

N = int(input())
for i in range(N):
    points.append(list(map(int, input().rstrip().split())))

for i in range(len(points)):
    for j in range(len(points)):
        X = abs(points[i][0] - points[j][0])
        Y = abs(points[i][1] - points[j][1])
        dist = X + Y
        
        if (dist >= currentMax):
            currentMax = dist

print(currentMax)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
N = int(input())

def dist(dot1, dot2):
    dx = abs(dot1[0]-dot2[0])
    dy = abs(dot1[1]-dot2[1])
    return dx+dy

dots = []

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

max_len = 0
for i in range(N):
    for j in range(i):
        max_len = max(max_len, dist(dots[i], dots[j]))

print(max_len)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
xyi = []
x = np.zeros(N)
y = np.zeros(N)

ans = 0
for i in range(N):
  x[i],y[i] = map(int, input().split())
  if i >0 :
    x_temp = np.abs(x[i] - x[:i])
    y_temp = np.abs(y[i] - y[:i])
    xy_temp = x_temp + y_temp
    temp = np.max(xy_temp)
    if temp > ans:
      ans = temp
  
  
print(int(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x, y = map(int, input().split())
n_list = [[x, y]]
dist_max = 0

for i in range(n - 1):
    x, y = map(int, input().split())
    for j in range(len(n_list)):
        dist = abs(n_list[j][0] - x) + abs(n_list[j][1] - y)
        if dist > dist_max:
            dist_max = dist
    n_list.append([x, y])

print(dist_max)

Submission status: Time Limit Exceeded

Solution code:
int_n = int(input())
list_agg = list()
for i in range(int_n):
  list_agg.append(list(map(int, input().split())))

#print(list_agg)

max = 0 
i_tmp = 0
j_tmp = 0

for i in range(len(list_agg)):
  for j in range(i, len(list_agg)):
    #tmp = abs(list_agg[i][0]-list_agg[j][0]) + abs(list_agg[i][1]-list_agg[j][1])
    tmp = (list_agg[i][0]-list_agg[j][0])**2 + (list_agg[i][1]-list_agg[j][1])**2
    if max < tmp:
      max = tmp
      i_tmp = i
      j_tmp = j
#print(max)
print(abs(list_agg[i_tmp][0]-list_agg[j_tmp][0]) + abs(list_agg[i_tmp][1]-list_agg[j_tmp][1]))

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)

ans = 0
for i in range(N-1):
    for j in range(N):
        if i < j:
            dx = abs(X[i]-X[j])
            dy = abs(Y[i]-Y[j])
            L = dx + dy
            ans = max(ans, L)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ListN = [[0 for i in range(2)] for j in range(N)]

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

m = 0
minN = ListN[0][0] + ListN[0][1]
maxN = ListN[0][0] + ListN[0][1]

for i in range (len(ListN)-1):
  flg = False
  if minN >= ListN[i][0] + ListN[i][1]:
    minN = ListN[i][0] + ListN[i][1]
    flg = True
  elif maxN <= ListN[i][0] + ListN[i][1]:
    maxN = ListN[i][0] + ListN[i][1]
    flg = True
  if flg:
    for j in range (i,len(ListN)):
     m = max(m, abs(ListN[i][0] - ListN[j][0]) + abs(ListN[i][1] - ListN[j][1]) )

print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

listA=[]

while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
ans=0
for i in range(N):
  for j in range(i+1,N):
    ans=max(ans,abs(listA[i][0]-listA[j][0])+abs(listA[i][1]-listA[j][1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

if __name__=="__main__":
  n=int(input())
  l=[]
  for _ in range(n):
    x=[int(i) for i in input().split()]
    l.append(x)
  if len(l)==1:
    print(0)
    exit
  n=len(l)
  ans=[]
  for i in range(n):
    for j in range(1,n):
      ans.append(dist(l[i],l[j]))
  print(max(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import random

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


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


p_a = xys[0]
p_b = xys[1]
for _ in range(5):
    random.shuffle(xys)
    for p_c in xys:
        d_a_b = m(p_a, p_b)
        d_a_c = m(p_a, p_c)
        d_b_c = m(p_b, p_c)

        if d_a_b > max(d_a_c, d_b_c):
            pass
        else:
            if d_a_c > d_b_c:
                p_b = p_c
            else:
                p_a = p_c
print(m(p_a, p_b))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
x_list = np.empty((0,2), int)

for i in range(n):
    x_1, x_2 = map(int, input().split())
    x_list = np.append(x_list, np.array([[x_1, x_2]]), axis=0)

max_val = 0

for i, l in enumerate(x_list):
    x_list_i = x_list[i]
    if i == (n -1):
        break
    else:
        for j in range(i+1, n):
            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:
def dist(v1, v2):
    return abs(v1[0]-v2[0]) + abs(v1[1]-v2[1])

def main():
    N = int(input())
    v = []
    for i in range(N):
        vx, vy = map(int, input().split())
        v.append((vx, vy))

    max_dist = 0
    for i in range(N):
        w = v[i]
        v_except_w = v[:i] + v[i+1:]
        sorted_v_e = sorted(v_except_w, key=lambda x: dist(x, w))
        if max_dist < dist(w, sorted_v_e[-1]):
            max_dist = dist(w, sorted_v_e[-1])

    print(max_dist)    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import random

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


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


p_a = xys[0]
p_b = xys[1]
for _ in range(10):
    random.shuffle(xys)
    for p_c in xys:
        d_a_b = m(p_a, p_b)
        d_a_c = m(p_a, p_c)
        d_b_c = m(p_b, p_c)

        if d_a_b > max(d_a_c, d_b_c):
            pass
        else:
            if d_a_c > d_b_c:
                p_b = p_c
            else:
                p_a = p_c
print(m(p_a, p_b))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
 
def calc_distance(a,b):
    distance = round(abs(a[0]-b[0]) + abs(a[1]-b[1]),6)
    return distance
 
dots = []
for i in range(int(input())):
    dots.append(list(map(int,input().split())))
 
combis = list(itertools.combinations(dots,2))
max_distance = 0
for combi in combis:
    distance = calc_distance(combi[0],combi[1])
    max_distance = max(distance,max_distance) 
 
print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from functools import reduce

def convex_hull_graham(points):
  TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

  def cmp(a, b):
    return (a > b) - (a < b)
  def turn(p, q, r):
    return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
  def _keep_left(hull, r):
    while len(hull) > 1 and turn(hull[-2], hull[-1], r) == TURN_RIGHT:
      hull.pop()
    if not len(hull) or hull[-1] != r:
      hull.append(r)
    return hull
  points = sorted(points)
  l = reduce(_keep_left, points, [])
  u = reduce(_keep_left, reversed(points), [])
  return l.extend(u[i] for i in range(1, len(u) - 1)) or l


# Function to find the maximum 
# distance between any two points 
def maxDist(p): 
  n = len(p) 
  maxm = 0
  # Iterate over all possible pairs 
  for i in range(n): 
    for j in range(i + 1, n): 
      # Update maxm
      dist=  abs( p[i][0] - p[j][0])+abs( p[i][1] - p[j][1]) 
      maxm = max(maxm, dist) 
  # Return actual distance 
  #return sqrt(maxm) 
  return maxm
# Driver Code 
if __name__ == '__main__': 
  # Number of points 
  n=int(input())
  xy=[None]*n
  for i in range(n):
    xy[i]=list(map(int,input().split()))
  # Given points 
  # Function Call 
  xy=convex_hull_graham(xy)
  print(maxDist(xy))

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

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:
class SegTree:
    def __init__(self, N, fill, function):
        L = 1
        k = 1
        while k<N:
            L += 1
            k<<=1

        segsize = [None]*L
        data = [None]*L
        for l in range(L):
            segsize[l] = 1<<(L-l-1)
            data[l] = [fill]*(1<<l)

        self.L = L
        self.segsize = segsize
        self.data = data
        self.function = function

    def update(self, i, value):
        self.data[self.L-1][i] = value
        for l in range(self.L-2, -1, -1):
            i//=2
            self.data[l][i] = self.function(*self.data[l+1][i*2:i*2+2])

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

        imid = ibgn - ibgn%ssize + ssize//2
        if iend<=imid or imid<=ibgn: return self.query(ibgn, iend, l+1)
        return self.function(
            self.query(ibgn, imid, l+1),
            self.query(imid, iend, l+1)
        )

    def print(self):
        for l, row in enumerate(self.data):
            print('{:2d} {}'.format(l, row))

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.data[-1][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.data[-1][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:
N = int(input())
X=[0]*N
Y=[0]*N
for i in range(0,N):
    X[i],Y[i] = map(int,input().split())
n=0
m=0
for j in range(0,N):
    for k in range(0,N):
        n = abs(X[j]-X[k])+abs(Y[j]-Y[k])
        if n>m:
            m = n
            
print(m)

Submission status: Time Limit Exceeded

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

N = int(input())

A = [ [] for _ in range(N) ]
for i in range(N):
  A[i] = list(map(int,input().split()))
#print(A)

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])
    if ( d <= ans ):
      continue
    ans = d
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def man_dis(x,y):
    return(abs(x[0]-y[0])+abs(x[1]-y[1]))
    

n=int(input())
a=set()
for i in range (n):
    x,y=map(int,input().split())
    a.add((x,y))
s=list(a)

if len(s) ==1:
    print (0)
else:
    ans=0
    for j in range (len(s)-1):
        for k in range (j,len(s)):
            ans=max(ans,man_dis(s[j],s[k]))
    print (ans)

Submission status: Time Limit Exceeded

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

max=0

for i in range(n):
	for j in range(n-i-1):
		k = j+i+1
		dist = abs(num_list[i][0]-num_list[k][0])+abs(num_list[i][1]-num_list[k][1])
		if dist > max:
			max = dist
print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
xyi = []
xi  = []
yi  = []
ans = 0
for i in range(N):
  xyi.append(list(map(int, input().split())))
  xi.append(xyi[i][0])
  yi.append(xyi[i][1])
  x = np.array(xi)
  y = np.array(yi)
  if i >0 :
    x_temp = np.abs(x[i] - x[:i])
    y_temp = np.abs(y[i] - y[:i])
    xy_temp = x_temp + y_temp
    temp = np.max(xy_temp)
    if temp > ans:
      ans = temp
  
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
D={}
for i in range(N):
  x,y=map(int, input().split())
  if x not in D:
    D[x]=[y,y]
  else:
    a,b=D[x][0],D[x][1]
    D[x][0]=min(a,y)
    D[x][1]=max(b,y)
d=len(D)
if len(D)==1:
  for i in D:
    print(abs(D[i][0]-D[i][1]))
    exit()
ans=0
for i in D:
  for j in D:
    if i<=j:
      a,b,c,d=D[i][0],D[i][1],D[j][0],D[j][1]
      ans=max(ans,abs(d-a)+(j-i),abs(c-b)+(j-i))
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
a = 100000000000000
m = 0
lm = 0
rm = 0
lt  = []
rt  = []
lb = []
rb = []

for l in c:
    m = max(m,l[0]+l[1])
    a = min(a,l[0]+l[1])
    if l[0] > l[1]:
        rm = max(rm,l[0]-l[1])
    if l[0] < l[1]:
        lm = max(lm,l[1]-l[0])

for l in c:
    if l[0] + l[1] == m:
        rt.append(l)
    if l[0] + l[1] == a:
        lb.append(l)
    if l[0] > l[1] and l[0] - l[1] == rm:
        rb.append(l)
    if l[0] < l[1] and l[1] - l[0] == lm:
        lt.append(l)


for i in lt:
    for j in rb:
        ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))

for i in rt:
    for j in lb:
        ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    n = int(input())
    p = [list(map(int, input().split())) for i in range(n)]
    max_p = []
    for i in range(n):
        a, b = p[i][0], p[i][1]
        if len(max_p) == 0:
            max_p.append([a, b])
        if max_p[0][0]**2 + max_p[0][1]**2 < a**2 + b**2:
            max_p.append([a, b])
    ans = 0
    for mp in max_p:
        for i in range(n):
            tmp = abs(mp[0] - p[i][0]) + abs(mp[1] - p[i][1])
            ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = []
for _ 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):
    ans = max(ans, abs(L[i][0] - L[j][0]) + abs(L[i][1] - L[j][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
X=[]
Y=[]
P=np.ndarray((0,2))
for i in range(n):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(Y)
    P=np.vstack((P,[x+y,x-y]))
    
ans = max(max(P[:,0])-min(P[:,0]),max(P[:,1])-min(P[:,1]))

print(int(ans+0.5))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ls = []

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

for i in range(N):
    a = ls[i][0]
    b = ls[i][1]
    for j in range(N):
        c = ls[j][0]
        d = ls[j][1]
        e = abs(a-c)+abs(b-d)
        if m < e:
            m = e


print(m)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
    
@jit
def main():
    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)
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
length = 0

for set in permutations(point,2):
   calc = abs(set[0][0]-set[1][0]) + abs(set[0][1]-set[1][1])
   length = max(calc, length)
   
print(length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
coordinates = []
for i in range(N):
    coordinate = list(map(int, input().split()))
    coordinates.append(coordinate)
max_dist = 0
for i in range(N-1):
    for j in range(i+1, N):
        dist = abs(coordinates[i][0] - coordinates[j][0]) + abs(coordinates[i][1] - coordinates[j][1])
        if max_dist < dist:
            max_dist = dist
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ps = [list(map(int, input().split(" "))) for i in range(n)]
#print(ps)
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):
    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())
pt = []
for i in range(n):
  x, y = map(int, input().split())
  pt.append((x, y))
ans = []
for j in range(n):
  for k in range(n):
    ans.append(str(abs(pt[j][0] - pt[k][0]) + abs(pt[j][1] - pt[k][1])))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    P = []
    for _ in range(N):
        x, y = input().split()
        P.append((int(x), int(y)))
    ans = 0
    for i in range(N - 1):
        for j in range(i, N):
            ans = max(ans, abs(P[i][0] - P[j][0]) + abs(P[i][1] - P[j][1]))
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ans = 0
for i in range(N):
    for j in range(i+1, N):
        dist = abs(x[j]-x[i]) + abs(y[j]-y[i])
        if dist > ans:
            ans = dist
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
M = 0
for i in range(N):
    for l in range(i):
        temp = abs(X[i][0] - X[l][0]) + abs(X[i][1] - X[l][1])
        if M <= temp:
            M = temp
print(M)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def li():  return list(mi())

def main():
    n = ii()
    d = dict()
    
    for i in range(n):
        d[i] = li()

    res = 0

    for i in range(n):
        for j in range(i+1,n):
            dist = abs(d[i][0] - d[j][0]) + abs(d[i][1] - d[j][1])
            res = max(res,dist)
    # pass
    print(res)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
points = []
for _ in range(N):
  points.append(tuple(map(int, input().split())))

# get orientation
def orientation(p, q, r):
  v = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
  if v == 0:
    return 0
  elif v > 0:
    return 1
  else:
    return 2

# get left most point
def left_index(points):
  minn = 0
  for i in range(1, len(points)):
    if points[i][0] < points[minn][0]:
      minn = i
    elif points[i][0] == points[minn][0]:
      if points[i][1] > points[minn][1]:
        minn = i
  return minn

# get convex hull
def convex_hull(points, n):
  if n < 3:
    return
  l = left_index(points)
  hull = []
  p = l
  q = 0
  while True:
    hull.append(p)
    q = (p + 1) % n
    for i in range(n):
      if orientation(points[p], points[i], points[q]) == 2:
        q = i
    p = q
    if p == l:
      break
  return hull

hull = convex_hull(points, len(points))

res = 0

def distance(p, q):
  return abs(p[0] - q[0]) + abs(p[1] - q[1])

if len(points) == 2:
  print(distance(points[0], points[1]))
  exit()

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

# Rotating Calipers
n = len(hull)
i = j = 0
for k in range(n):
  if hull[k] < hull[i]: i = k
  if hull[j] < hull[k]: j = k
res = 0
si = i; sj = j
while i != sj or j != si:
  res = max(res, distance(points[hull[i]], points[hull[j]]))
  if cross(points[hull[i]], points[hull[i-n+1]], points[hull[j]], points[hull[j-n+1]]) < 0:
    i = (i + 1) % n
  else:
    j = (j + 1) % n
print(res)

Submission status: Time Limit Exceeded

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

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

ans=0
for i in range(n):
  for j in range(n):
    y=abs(x[i][0]-x[j][0])+abs(x[i][1]-x[j][1])
    if ans<y:
      ans=y
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    a = ls[i][0]
    b = ls[i][1]
    for j in range(N):
        c = ls[j][0]
        d = ls[j][1]
        e = abs(a-c)+abs(b-d)

        result.append(e)
m = result[0]
for i in range(len(result)):
    if m < result[i]:
        m = result[i]


print(m)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(len(x)):
    for j in range(i+1,len(x)):
        tmp = abs(x[i]-x[j]) +abs(y[i]-y[j])
        if tmp>ans:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
checker = []
counter = 0
third = 0
fourth = 0
for i in range(x):
    details = input()
    details = details.split()
    first = int(details[0])
    second = int(details[1])
    if len(checker) == 0:
        checker.append((first, second))
        third, fourth = first, second
    else:
        checker.append((first, second))
        for numbers in checker:
            current = abs(third - first) + abs(fourth - second)
            if current > counter:
                counter = current
print(counter)