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:

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
data = [readInts() for i in range(n)]
xy = {}
for x,y in data:
	if x in xy:
		xy[x].append(y)
	else:
		xy[x] = [y]
for x in xy:
	xy[x].sort()

#print(xy)
ans = 0
for x1,y1 in data:
	for x2 in xy:
		ans = max(ans, abs(x1-x2)+abs(y1-xy[x2][0]),abs(x1-x2)+abs(y1-xy[x2][-1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
beforex=[]
beforey=[]
sum=0
for i in range(int(input())):
  xy=list(map(int,input().split()))
  beforex.append(xy[0])
  beforey.append(xy[1])

for i in range(len(beforex)-1):
  for j in range(i,len(beforex)):
    sum=max(sum,abs(beforex[i]-beforex[j])+abs(beforey[i]-beforey[j]))

print(sum)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding:utf-8

def main():
    line = int(input())
    xy = [map(int, input().split()) for _ in range(line)]
    x, y = [list(i) for i in zip(*xy)]
    stdOut = solve(line, x, y)
    print(stdOut)


"""
方針


"""


def solve(line, x, y):
    lenMax = 0
    for i in range(line):
        for j in range(line):
            l = abs(x[i] - x[j]) + abs(y[i] - y[j])
            if l > lenMax:
                lenMax = l
    return lenMax


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
points=[]
summaxp=[]
summinp=[]
diffmaxp=[]
diffminp=[]

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y
    if not [x,y] in points:
        points.append([x,y])
        if x+y > summax:
            summaxp=[[x,y]]
            summax = x+y
        elif x+y == summax:
            summaxp.append([x,y])
        if x+y < summin:
            summinp=[[x,y]]
            summin = x+y
        elif x+y == summin:
            summinp.append([x,y])
        if x-y > diffmax:
            diffmaxp=[[x,y]]
            diffmax = x-y
        elif x-y == diffmax:
            diffmaxp.append([x,y])
        if x-y < diffmin:
            diffminp=[[x,y]]
            diffmin = x-y
        elif x-y == diffmin:
            diffminp.append([x,y])

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)

Submission status: Time Limit Exceeded

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

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(int(rotating_calipers(ps)))

Submission status: Time Limit Exceeded

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

result=0
for i in range(n):
    for j in range(n):
        tmp=abs(xylist[i][0]-xylist[j][0])+abs(xylist[i][1]-xylist[j][1])
        if tmp > result:
            result=tmp
        else:
            continue

print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

xy = [ [0,0] ]*N

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

max = 0

for s in range(N-1):
  for t in range(s+1,N):
    manh = 0
    x_d = xy[s][0] - xy[t][0]
    y_d = xy[s][1] - xy[t][1]
    if x_d > 0:
      manh += x_d
    else:
      manh -= x_d
    if y_d > 0:
      manh += y_d
    else:
      manh -= y_d
    
    if manh > max:
      max = manh

print(max)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
X=[]
Y=[]
man=0
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=np.abs(X[i]-X[j])+np.abs(Y[i]-Y[j])
        if man<res:
            man=res
print(man)

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])
    return (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())
  s = set() 
  #xy=[None]*n
  for i in range(n):
    x,y=map(int,input().split())
    s.add((x,y))
  # Given points 
  # Function Call 
  xy=convex_hull_graham(s)
  print(maxDist(xy))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

md = 0
for i in range(n-1):
    for j in range(i+1,n):
        d1 = cd[i][0] - cd[j][0]
        d2 = -cd[i][0] + cd[j][0]
        d3 = cd[i][1] - cd[j][1]
        d4 = - cd[i][1] + cd[j][1]
        md = max(md, d1, d2, d3, d4)

print(md)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

pnt=[]
for i in range(n):
  pnt.append(list(map(int,input().split())))
pnt.sort(key=lambda x:abs(x[0])+abs(x[1]),reverse=True)
mn=list(reversed(pnt))
mx=0

for i in range(min(n,16000)):
  for j in range(i+1,min(n,16000)):
    mx=max(abs(pnt[i][0]-pnt[j][0])+abs(pnt[i][1]-pnt[j][1]),mx)
    mx=max(abs(pnt[i][0]-mn[j][0])+abs(pnt[i][1]-mn[j][1]),mx)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

l = [None] * N

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

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

print(max([d(p0,p1) for p0 in l for p1 in l]))

Submission status: Time Limit Exceeded

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

n = 0
for i in range(N):
    for j in range(i):
        if n < abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1]):
            n = abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1])

print(n)

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])
    return (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())
  s = set() 
  #xy=[None]*n
  for i in range(n):
    x,y=map(int,input().split())
    s.add((x,y))
  # Given points 
  # Function Call 
  xy=convex_hull_graham(s)
  print(maxDist(xy))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [[] for _ in range(N)]
d = set()
ans = 0
for i in range(N):
    X[i] = list(map(int, input().split()))

for i in range(1, N):
    for j in range(i):
        d.add(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1]))
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def dist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

N=int(input())
P=[0]*N

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

P=list(set(P))
N=len(P)

S=[0]*N
D=[]
for k in range(N):
    if S[k]==0:
        S[k]=1
        Old_Old_=0
        Old_I=-1
        I=k
        Flag=False
        while True:
            M=-1
            Old_Old_I=Old_I
            Old_I=I
            for i in range(N):
                if M<dist(P[I],P[i]):
                    J=i
                    M=dist(P[I],P[i])

            if J==Old_Old_I and Flag:
                break
            I=J
            S[I]=1
            Flag=True

    D.append(dist(P[Old_I],P[J]))

print(max(D))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lis = [list(map(int, input().split())) for i in range(N)]
S = 0
count = 0

for i in range(N):
  for j in range(N - i):
    count = abs(lis[i][0] - lis[j][0]) + abs(lis[i][1] - lis[j][1])
    S = max(S, count)

print(S)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());L=sorted([list(map(int,input().split()))for _ in "_"*n])
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])
    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
if len(L)<3:print(abs(L[0][0]-L[1][0])+abs(L[0][1]-L[1][1]));exit()
L=convex_hull(L)
l=len(L)
m=0
for i in range(1,l):
  a,b=L[i]
  for j in range(i):
    c,d=L[j]
    m=max(m,abs(a-c)+abs(b-d))
print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ps = [[*map(int, input().split())] for _ in range(N)]
print(max(sum(abs(ps[i][k] - ps[j][k]) for k in range(2)) for i in range(N) for j in range(i+1, N)))

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
n = int(input())
ps = list(map(list, [map(float, input().split()) for i in range(n)]))

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(int(rotating_calipers(ps)))

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)]
ans = 0
for i in range(N-1):
    a = xy[1][i]
    x = xy[0][i+1:]
    y = list(map(lambda y: abs(y-a),xy[1][i+1:]))
    z = [i+j for i,j in zip(x,y)]
    ans = max(ans,max(z)-xy[0][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
n = int(input())
ps = list(map(list, [map(float, input().split()) for i in range(n)]))
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(int(rotating_calipers(ps)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

s = int(input())
n = 1
S = []
ans = []

while n <= s:
    a, b = map(int, input().split())
    S.append([a, b])
    n += 1

for pair in itertools.combinations(S, 2):
    ans.append(abs(pair[0][0] - pair[1][0])+abs(pair[0][1] - pair[1][1]))


print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr
N = int(input())
l = [tuple(map(int, input().split())) for i in range(N)]
d=list()
for i, j in list(itr.combinations(range(N),2)):
    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 itertools import combinations as cmb
n=int(input())

def distant(d1,d2):
  return abs(d1[0]-d2[0])+abs(d1[1]-d2[1])

ds=[tuple(map(int,input().split())) for _ in range(n)]
ds=list(cmb(ds,2))
ret=0
for d0,d1 in ds:
  ret=max(ret,distant(d0,d1))

print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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-1):
    le=i+1
    r=len(l)-1
    ma=-1
    while(i<r):
      mid=le+(r-le)//2
      if dist(l[i],l[mid])>ma:
        ma=dist(l[i],l[mid])
        le=mid+1
      else:
        r=mid-1
    ans.append(ma)
  print(max(ans))

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}
lY = sorted(list(setY))
iY = {y:i for i, y in enumerate(lY)}

ans1 = 0
S = SegTree(len(iY), INF, min)
bottom = S.data[-1]

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

############################

Z = 10**9+1
P = sorted([(x, Z-y) for x, y in XY])

iY = {Z-y: i for i, y in enumerate(reversed(lY))}

ans2 = 0
S = SegTree(len(iY), INF, min)
bottom = S.data[-1]

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

print(max(ans1, ans2))

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())
S=[list(map(int,input().split())) for i in range(n)]
ans=0
x_min=10**9
x_max=0
y_min=10**9
y_max=0
    
for i in range(n):
    for j in range(i,n):
        if x_min<min(S[i][0],S[j][0]) and x_max>max(S[i][0],S[j][0]) and y_min<min(S[i][1],S[j][1]) and y_max>max(S[i][1],S[j][1]):
            continue
        x=S[i][0]-S[j][0]
        y=S[i][1]-S[j][1]
        x=math.fabs(x)
        y=math.fabs(y)
        key=x+y
        if key>ans:
            ans=key
            x_min=min(S[i][0],S[j][0])
            X_max=max(S[i][0],S[j][0])
            y_min=min(S[i][1],S[j][1])
            y_max=max(S[i][1],S[j][1])

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            tmp = abs(list_x[i] - list_x[j]) + abs(list_y[i] - list_y[j])
            if tmp > ans:
                ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr
N = int(input())
l = [tuple(map(int, input().split())) for i in range(N)]
d=list()
for i, j in itr.product(list(range(N)),list(range(1,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 math import sqrt
def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        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

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

ans = rotating_calipers(a)
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]

ListN = list(map(list, set(map(tuple, ListN))))
ListN.sort(reverse=True)
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:
t=int(input())
z=[]
for i in range(t):
      a,b=map(int,input().split())
      z.append([a,b])
k=[0]      
for i in range(len(z)):
      for j in range(i+1,len(z)):
            x1=(z[j])[0]
            x2=(z[j])[1]
            y1=(z[i])[0]
            y2=(z[i])[1]
            k.append(abs(y1-x1)+abs(y2-x2))
print(max(k))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

xy = [0] + [tuple(map(int, input().split())) for _ in range(N)]
m = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        xyi = xy[i]
        xyj = xy[j]
        tmp = abs(xyi[0]-xyj[0]) + abs(xyi[1]-xyj[1])
        if m < tmp:
            m = tmp
print(m)

Submission status: Time Limit Exceeded

Solution code:
def main():
	N = int(input())
	p = []
	for i in range(N):
		x, y = [int(a) for a in input().split(" ")]
		p.append({"x" : x, "y" : y})
	aveX = 0
	aveY = 0
	for i in range(N):
		aveX += p[i]["x"]
		aveY += p[i]["y"]
	aveX /= N
	aveY /= N
	for i in range(N):
		p[i]["d"] = abs(aveX - p[i]["x"]) + abs(aveY - p[i]["y"])
	p.sort(key=lambda z: z["d"])
	D = []
	P = [p[-1]]
	k = 1
	while k < len(p) and abs(p[-k-1]["d"] - P[0]["d"]) < 1:
		P.append(p[-k-1])
		k += 1
	for i in range(N - 1):
		for j in range(len(P)):
			D.append(abs(P[j]["x"] - p[i]["x"]) + abs(P[j]["y"] - p[i]["y"]))
	print(max(D))

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())

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

d = list(itertools.combinations(num, 2))
m = 0
for i in d:
    m = max(m ,abs(i[0][0] - i[1][0]) + abs(i[0][1] - i[1][1]) )
print(m)

Submission status: Time Limit Exceeded

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

def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        # 一直線上で高々2点にする場合は ">=" にする
        while len(qs) > 1 and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs

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

def rotating_calipers(ps):
    qs = convex_hull(ps)
    n = len(qs)
    if n == 2:
        return dist(qs[0], qs[1])
    i = j = 0
    for k in range(n):
        if qs[k] < qs[i]:
            i = k
        if qs[j] < qs[k]:
            j = k
    res = 0
    si, sj = i, 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(input())
    ps = [tuple(map(int, input().split())) for _ in range(N)]
    ps = list(set(ps))
    ps.sort()

    print(rotating_calipers(ps))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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



m=0
for k in range(0,len(x)-1):
  for l in range(k,len(y)):
  
      if abs(x[k]-x[l])+abs(y[k]-y[l])>m:
         m=abs(x[k]-x[l])+abs(y[k]-y[l])
    
print(m)

Submission status: Time Limit Exceeded

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

N = int(readline().strip())
A = []
for i in range(N):
  xi, yi = map(int, readline().split())
  A.append([xi, yi])

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
d = 0
def md(a,b):
  return abs(a[0]-b[0]) +abs(a[1]-b[1])

for i in range(n):
  for j in range(n):
    dxy = md(xy[i],xy[j])
    if i != j and dxy >d:
      d = dxy
print(d)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
dis_max = 0

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

l = [i for i in range(1,N+1)]
c = itertools.combinations(l, 2)

for v in itertools.combinations(l, 2):
  distance = abs(XY[v[0]-1][0]-XY[v[1]-1][0])+abs(XY[v[0]-1][1]-XY[v[1]-1][1])
  if distance > dis_max:
    dis_max = distance
print(dis_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 t in l:
    ll=l[:]
    ll.remove(t)
    for s in ll:
         a.append(minkowski(t,s, 1 ))
print(int(max(a)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
points=[]
summaxp=[]
summinp=[]
diffmaxp=[]
diffminp=[]

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y
    if not [x,y] in points:
        points.append([x,y])
        if x+y > summax:
            summaxp=[[x,y]]
            summax = x+y
        elif x+y == summax:
            summaxp.append([x,y])
        if x+y < summin:
            summinp=[[x,y]]
            summin = x+y
        elif x+y == summin:
            summinp.append([x,y])
        if x-y > diffmax:
            diffmaxp=[[x,y]]
            diffmax = x-y
        elif x-y == diffmax:
            diffmaxp.append([x,y])
        if x-y < diffmin:
            diffminp=[[x,y]]
            diffmin = x-y
        elif x-y == diffmin:
            diffminp.append([x,y])

sol = 0
for p1 in summaxp:
    for p2 in summinp:
        kyori = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        if kyori > sol:
            sol = kyori

for p1 in diffmaxp:
    for p2 in diffminp:
        kyori = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        if kyori > sol:
            sol = kyori

print(sol)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt

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

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

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

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

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

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

print(rotating_calipers(ps))

Submission status: Time Limit Exceeded

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

d = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
  for j in range(N):
    if i < j:
      d[i][j] = abs(x[i]-x[j]) + abs(y[i]-y[j])
print(max(max(d)))

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):
    sol = abs(pt[j][0] - pt[k][0]) + abs(pt[j][1] - pt[k][1])
    ans.append(str(sol))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
num=int(input())

x=[]
y=[]
for i in range(num):
  line=input().split()
  line=[int(a) for a in line]
  x.append(line[0])
  y.append(line[1])


ans=0
for a in range(num):
  for b in range(num):
    if a==b:
      continue
    else:
      manx=abs(x[a]-x[b])
      many=abs(y[a]-y[b])
      man=manx+many
      if man>ans:
        ans=man
print(ans)