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   
# Function calculates distance 
# between two points 
def dist(p1, p2): 
  x0 = p1[0] - p2[0] 
  y0 = p1[1] - p2[1] 
  return abs(x0)+abs(y0)

# 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 
      maxm = max(maxm, dist(p[i], p[j])) 
  # Return actual distance 
  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 
  print(maxDist(xy))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
i, j, k = 0, 0, 0
x = []
y = []
m = []
while i < N:
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)
    i += 1
for j in range(N):
    for k in range(N):
        m.append(abs(x[j] - x[k]) + abs(y[j] - y[k])) 
        
print(max(m))

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

dl = []

for i in range(0,N):
  for j in range(i,N):
    d = abs(x[i] - x[j]) + abs(y[i] - y[j])
    dl.append(d)

print(max(dl))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())
pos = (list(map(int, input().split())) for _ in range(n))

ans = max(abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) for pos1, pos2 in combinations(pos, 2))

print(ans)

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 = []

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

Submission status: Time Limit Exceeded

Solution code:
import random
N = int(input())
lismoto = "0"*N*2
lis = list(lismoto)
for i in range(0,len(lis),2):
    lis[i],lis[i+1] = map(int,input().split())

li = [lis[idx:idx + 2] for idx in range(0,len(lis), 2)]

ma = 0
for i in range(10**7):
    a = random.randint(0,N-1)
    b = random.randint(0,N-1)
    
    karima = abs(li[a][0]-li[b][0]) + abs(li[a][1] - li[b][1])
    if karima > ma:
        ma = karima

print(ma)

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 
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])
    if max < tmp:
      max = tmp
print(max)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[0]*n
y=[0]*n
z=[0]*n
a=-1
b=-1
for i in range(n):
    x[i],y[i] = list(map(int, input().strip().split()))
for i in range(n):
    z[i]=x[i]**2+y[i]**2
for i in range(n):
    if z[i]==max(z):
        a=i
        break
for i in range(n):
    if z[i]==min(z):
        b=i
        break
print(abs(x[a]-x[b])+abs(y[a]-y[b]))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import sqrt

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

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

def dist(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])
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

def main():
    N = int(readline())
    m = map(int,read().split())
    XY = list(zip(m,m))

    XY.sort()
    # cf = convex_hull(XY)
    # print(cf)
    ans = rotating_calipers(XY)
    print(ans)

if __name__ == '__main__':
    main()

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):
  for j in range(i+1, N):
    if ans < (abs(xy[i][0]-xy[j][0]) + abs(xy[i][1]-xy[j][1])):
      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())
location = set()
for i in range(n):
  x, y = map(int, input().split())
  location.add((x, y))
location_list = list(location)
loc_x = sorted(location_list, key=lambda x: x[0])
loc_y = sorted(location_list, key=lambda x: x[1])
new = [loc_x[0], loc_y[0], loc_x[-1], loc_y[-1]]
for i in range(len(location)):
  if loc_x[i] == loc_y[0]:
    break
  new.append(loc_x[i])
for i in range(len(location)):
  if loc_y[i] == loc_x[0]:
    break
  new.append(loc_y[i])
for i in range(len(location)-1, -1, -1):
  if loc_x[i] == loc_y[-1]:
    break
  new.append(loc_x[i])
for i in range(len(location)):
  if loc_x[i] == loc_y[-1]:
    break
  new.append(loc_x[i])
answer = 0
for i in range(len(new)):
  for j in range(len(new)):
    a = new[i]
    b = new[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())

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
for i in range (len(ListN)-1):
 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())
xy = [list(map(int,input().split()))for _ in range(n)]

xsort = sorted(xy,key=lambda x:x[0])
ysort = sorted(xy,key=lambda x:x[1])

ans = 0
for i in range(min(n,10**4)):
    for j in range(min(n,10**4)):
        ans = max(ans,abs(xsort[i][0]-xsort[-j][0])+abs(xsort[i][1]-xsort[-j][1]))
        ans = max(ans,abs(ysort[i][0]-ysort[-j][0])+abs(ysort[i][1]-ysort[-j][1]))
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):
		k = j+i
		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:
N=int(input())
X=[]
Y=[]
man=[]
for m in range(N):
    x,y=map(int, input().split())
    X.append(x)
    Y.append(y)
for i in range(N):
    for j in range(i,N):
        res=abs(X[i]-X[j])+abs(Y[i]-Y[j])
        man.append(res)
print(max(man))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

xy = []
for _ in range(N):
  x,y=map(int,input().split())
  xy.append((x,y))
M,m = 3*(10**9), -3*(10**9)
x_max, x_min, y_max, y_min, t_max, t_min = m,M,m,M,m,M
cand = [xy[0] for _ in range(6)]
for x,y in xy[1:]:
  if x > x_max: x_max = x; cand[0]=(x,y);
  if x < x_min: x_min = x; cand[1]=(x,y);
  if y > y_max: y_max = y; cand[2]=(x,y);
  if y < y_min: y_min = y; cand[3]=(x,y);
  if x+y > t_max: t_max = x+y; cand[4]=(x,y);
  if x+y < t_min: t_min = x+y; cand[5]=(x,y);

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:
N=int(input())
X=[]
for i in range(N):
  array = list(map(int,input().split()))
  X.append(array)
D=[]
for i in range(N):
  for j in range(N-i):
    D.append(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1]))
print(max(D))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    dis = abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1])
    ans = max(ans,dis)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

ans = 0

m = 1
a = [x[0]]
b = [y[0]]

for i in range(1, n):
    f0 = True
    f1 = True
    for j in range(m):
        d = abs(x[i]-a[j])+abs(y[i]-b[j])
        if ans < d:
            ans = d
        if x[i] <= a[j] and y[i] <= b[j]:
            f0 = False
        if x[i] >= a[j] and y[i] >= b[j]:
            f1 = False
    if f0 or f1:
        m += 1
        a.append(x[i])
        b.append(y[i])

print(ans)

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())
s=[]
if n==1:
    print(0)
else:
    for i in range (n):
        x,y=map(int,input().split())
        s.append([x,y])
    ans=0
    for j in range (n-1):
        for k in range (j,n):
            ans=max(ans,man_dis(s[j],s[k]))
    print (ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for i in range(N)]
d=set()
for i in range(N):
    for j in range(N):
        d.add(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 = []
y = []
for i in range(n):
  xx,yy = map(int, input().split())
  x.append(xx)
  y.append(yy)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
input=__import__('sys').stdin.readline
def getdist(a,b):return abs(a[0]-b[0])+abs(a[1]-b[1])
n=int(input())
s=[]
for _ in range(n):
    s+=[*map(int,input().split())],
s.sort()
ans=0
sx=sorted(s)
sy=sorted(s,key=lambda x:x[1])
for i in sx:
    ans=max(ans,getdist(sx[0],i))
    ans=max(ans,getdist(sx[-1],i))
ans=max(ans,getdist(sx[-1],sx[-2]))
ans=max(ans,getdist(sx[0],sx[1]))
for i in sy:
    ans=max(ans,getdist(sy[0],i))
    ans=max(ans,getdist(sy[-1],i))
ans=max(ans,getdist(sy[-1],sy[-2]))
ans=max(ans,getdist(sy[0],sy[1]))
def ff1(x):return x[0]+x[1]
def ff2(x):return x[0]-x[1]
f1=sorted(s,key=ff1)
f2=sorted(s,key=ff2)
ans=max(ans,getdist(f1[0],f1[-1]))
ans=max(ans,getdist(f1[0],f1[1]))
ans=max(ans,getdist(f1[-1],f1[-2]))
ans=max(ans,getdist(f2[0],f2[-1]))
ans=max(ans,getdist(f2[0],f2[1]))
ans=max(ans,getdist(f2[-1],f2[-2]))
def ff1(x):return abs(x[0]+x[1])
def ff2(x):return abs(x[0]-x[1])
f1=sorted(s,key=ff1)
f2=sorted(s,key=ff2)
ans=max(ans,getdist(f1[0],f1[-1]))
ans=max(ans,getdist(f1[0],f1[1]))
ans=max(ans,getdist(f1[-1],f1[-2]))
ans=max(ans,getdist(f2[0],f2[-1]))
ans=max(ans,getdist(f2[0],f2[1]))
ans=max(ans,getdist(f2[-1],f2[-2]))
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)

print(max(result))

Submission status: Time Limit Exceeded

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

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

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)

x_mid=(a+b)//2
y_mid=(c+d)//2

for i in range(N):
    if dp[i]!=-1:
        continue
    dist=0
    ind=-1
    for j in range(i+1,N):
        if X[i]<=x_mid<=X[j] or X[j] <= x_mid <= X[i]:
            if Y[i]<=y_mid<=Y[j] or Y[j] <= y_mid <= Y[i]:
                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:
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 one(x,y):
    a=np.zeros(0)
    b=np.zeros(0)
    for i in range(len(x)):
        for j in range(i+1,len(x)):
            a = np.insert(a,0,abs(x[j]-x[i]))
            b = np.insert(b,0,abs(y[j]-y[i]))
    c = a+b
    print(int(c[np.argmax(c)]))

one(x,y)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
xy = []
x  = []
y  = []

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

x = np.array(x)
y = np.array(y)

ans = 0

for i in range(N-1):
  x_temp = np.abs((x[i] - x[i+1:]))
  y_temp = np.abs((y[i] - y[i+1:]))
  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,),*e=[[*map(int,i.split())]for i in open(0)]
a=sorted(e)
b=sorted(e,key=lambda x: x[1])
ans=0
for i,j in a[:10]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in a[:10]:
    for ii,jj in a[10:]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in a[10:]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in b[10:]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

dist=[]

for i in range(n):
	for j in range(n-i):
		k = j+i
		dist.append(abs(num_list[i][0]-num_list[k][0])+abs(num_list[i][1]-num_list[k][1]))

print(max(dist))

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(i+1, n):
        ans = max(ans, abs(a[i]-a[j]) + abs(b[i]-b[j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ps = [tuple(map(int, input().split())) for _ in range(N)]
ps = list(set(ps))
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())
c = [[int(i) for i in input().split()] for i in range(n)]
max_length = 0
for i in range(n-1):
    for j in range(i+1,n):
        length = abs(c[i][0] - c[j][0]) + abs(c[i][1] - c[j][1])
        max_length = max(max_length, length)
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    P = [list(map(int, input().split())) for _ in range(n)]
    ans = 0

    for i, pi in enumerate(P):
        for pj in P[i+1:]:
            ans = max(ans, abs(pi[0] - pj[0])+abs(pi[1] - pj[1]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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 = max(r, res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
points = []
for _ in range(N):
  points.append(list(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()

for i in range(len(hull)):
  for j in range(len(hull)):
    if i == j:
      continue
    res = max(res, distance(points[hull[i]], points[hull[j]]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
pts = []
maxdist = 0
for i in range(n):
    x, y = map(int, input().split())
    for p in pts:
        maxdist = max(maxdist, (abs(x-p[0])+abs(y-p[1])))
    pts.append( (x, y) )

print(maxdist)

Submission status: Time Limit Exceeded

Solution code:
def ge():
    return map(int,input().split())
def main():
    #a,b,c,d=ge()
    #N=int(input())
    #a=list(map(int,input().split()))
    #a=input()
    N=int(input())
    x=[]
    y=[]
    for _ in range(N):
        X,Y=ge()
        x.append(X)
        y.append(Y)
    x_list=[]
    for i in range(len(x)-1):
        for j in range(i,len(x)):
            x_list.append(abs(x[i]-x[j]))
    y_list=[]
    for i in range(len(y)-1):
        for j in range(i,len(y)):
            y_list.append(abs(y[i]-y[j]))
    ans=0
    for i in range(len(x_list)):
        ans=max(ans,x_list[i]+y_list[i])
    print(ans)



main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[0]*N
Y=[0]*N
D=[]
trial=N*(N-1)/2
for i in range(N):
  X[i],Y[i]=map(int,input().split())
for i in range(N-1):
  for j in range(i+1,N):
    d=abs(X[i]-X[j])+abs(Y[i]-Y[j])
    D.append(d)
print(max(D))

Submission status: Time Limit Exceeded

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

n = int(input())
ans = 0
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort(key=lambda p: (p[0], p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[0], -p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], -p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))

P.sort(key=lambda p: (-p[0], p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[0], -p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[1], p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[1], -p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
Y=[]
man=[]
for m in range(N):
    x,y=list(map(int, input().split()))
    X.append(x)
    Y.append(y)
for i in range(N):
    for j in range(i,N):
        res=abs(X[i]-X[j])+abs(Y[i]-Y[j])
        man.append(res)
print(max(man))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[]
max=0
for i in range(n):
  k,kk=map(int, input().split())
  m=list(l)
  #print(l)
  while(len(m)>0):
    h=m.pop()
    ma=abs(h[0]-k)+abs(h[1]-kk)
    if ma>max:
      max=ma
  l.append([k,kk])
print(max)

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 cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

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

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

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

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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import sqrt

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

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

def dist(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])
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

def main():
    N = int(readline())
    m = map(int,read().split())
    XY = list(zip(m,m))

    XY.sort()

    ans = rotating_calipers(XY)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

#print(n, xy)
tmp = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        l = abs(xy[i][0] - xy[j][0]) + abs(xy[i][1] - xy[j][1])
        if tmp <= l:
            tmp = l
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
XY=[input().split(' ')for i in range(n)]
xy=[[int(XY[j][i])for i in range(2)]for j in range(n)]
S=0
for i in range(n-1):
  for j in range(i+1,n):
    x_i,y_i=xy[i]
    x_j,y_j=xy[j]
    if S<abs(x_i-x_j)+abs(y_i-y_j):
      S=abs(x_i-x_j)+abs(y_i-y_j)
print(S)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

xy = []

for z in range(n):
    a = list(map(int,input().split()))
    xy.append(a)



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

kyori = []

for i in range(n-1):
    for j in range(i+1,n):
        s = how_far(xy[i],xy[j])
        kyori.append(s)

print(max(kyori))

Submission status: Time Limit Exceeded

Solution code:
import copy

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())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])

l.sort()
k = copy.deepcopy(l[0])
ll = [k]
for i in range(1,len(l)):
    if k != l[i]:
        ll.append(l[i])
        k = l[i]
if len(ll) == 1:
    print(0)
elif len(ll) == 2:
    print(abs(ll[0][0]-ll[1][0])+abs(ll[0][1]-ll[1][1]))
else:
    F = convex_hull(ll)
    L = len(F)
    ans = 0
    for i in range(L-1):
        for j in range(i+1,L):
            ans = max(ans,abs(F[i][0]-F[j][0])+abs(F[i][1]-F[j][1]))
    print(ans)

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(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:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

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

n = ii()
l = []
for i in range(n):
    l += [li()]

m = 0
for i in range(n-1):
    for j in range(i+1, n):
        m = max(m, man(l[i], l[j]))

print(m)