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:
import sys
import math
import itertools


class Heap:
    def __init__(self, N, f):
        self.vs = [None] * N
        self.size = 0
        self.f = f

    def push(self, n):
        self.vs[self.size] = n
        c = self.size
        p = (c - 1) // 2
        self.size += 1
        while self.swap(p, c):
            c = p
            p = (c - 1) // 2
        # print(self.vs)

    def pop(self):
        ret = self.vs[0]
        self.vs[0] = self.vs[self.size - 1]
        self.vs[self.size - 1] = None
        self.size -= 1
        p = 0
        lc = p * 2 + 1
        rc = p * 2 + 2
        c = rc if rc < self.size and self.f(self.vs[rc], self.vs[lc]) else lc
        while self.swap(p, c):
            p = c
            lc = p * 2 + 1
            rc = p * 2 + 2
            c = rc if rc < self.size and self.f(self.vs[rc], self.vs[lc]) else lc
        # print(self.vs)
        return ret

    def swap(self, p, c):
        if p < 0:
            return False
        if c >= self.size:
            return False
        if self.f(self.vs[c], self.vs[p]):
            self.vs[c], self.vs[p] = self.vs[p], self.vs[c]
            return True
        else:
            return False


def f3(a, b):
    if a[0] < b[0]:
        return True
    if a[0] > b[0]:
        return False
    if a[1] > b[1]:
        return True
    else:
        return False


def comp(x, y, z):
    fs = [
        lambda a, b: a < b,
        lambda a, b: a > b
    ]

    def swap(a):
        return a[1], a[0]

    def ret(a, b):
        if x == 0:
            m, n = a, b
        else:
            m, n = swap(a), swap(b)
        f1 = fs[y]
        f2 = fs[z]
        if f1(m[0], n[0]):
            return True
        if m[0] != n[0]:
            return False
        if f2(m[1], n[1]):
            return True
        else:
            return False
    return ret


fs = [comp(x, y, z) for x, y, z in itertools.product([0, 1], [0, 1], [0, 1])]


N = int(sys.stdin.readline().strip())
hs = [Heap(N, f) for f in fs]

for i in range(N):
    x, y = [int(a) for a in sys.stdin.readline().strip().split(" ")]
    for h in hs:
        h.push((x, y))


ls = [h.pop() for h in hs]


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


ret = 0
for a, b in itertools.product(ls, ls):
    r2 = dist(a, b)
    if ret < r2:
        ret = r2
print(ret)

Submission status: Time Limit Exceeded

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

D=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        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())
xy=[]
for i in range(N):
    x,y=map(int,input().split())
    xy.append([x,y])

import itertools

ans=0
for i in itertools.combinations(xy,2):
    xy1=i[0]
    xy2=i[1]
    x=abs(xy1[0]-xy2[0])
    y=abs(xy1[1]-xy2[1])
    ans=max(ans,x+y)
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())

xy = []

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

# xy = get_unique_list(xy)
# N = len(xy)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())

xy = []

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

xy = get_unique_list(xy)
N = len(xy)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def manhattan_distance(start, end):
       sx, sy = start
       ex, ey = end
       return abs(ex - sx) + abs(ey - sy)

ret = 0
import itertools
for i in itertools.product(tmp, repeat=2):
    man = manhattan_distance(*i)
    if ret < man:
        ret = man
print(ret)

Submission status: Time Limit Exceeded

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

def manhattan_distance(start, end):
       sx, sy = start
       ex, ey = end
       return abs(ex - sx) + abs(ey - sy)

ret = 0
import itertools
for i in itertools.product(tmp, repeat=2):
    if ret < manhattan_distance(*i):
        ret = manhattan_distance(*i)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import sys

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

min_diff = 10**9
max_diff = 1
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

cand_set = set()
for x,y in XY:
    if x-y in (min_diff, max_diff) or x+y in (min_sum, max_sum):
        cand_set.add((x, y))

if len(cand_set) == N:
    print(max(max_sum-min_sum, max_diff - min_diff))
    sys.exit()

dist = 0
for p1, p2 in combinations(cand_set, 2):
    dist = max(dist, abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]))
    
print(dist)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

manhat_list = []
x_list = []
y_list = []

for num in range(n):
    x, y = map(int, input().split())
    manhat_list.append(x+y)
    x_list.append(x)
    y_list.append(y)

    max_l = manhat_list.index(max(manhat_list))
    min_l = manhat_list.index(min(manhat_list))

print(abs(x_list[max_l] - x_list[min_l]) + abs(y_list[max_l] - y_list[min_l]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    def calc_dist(pi):
        ret = -1
        reti = -1
        px, py = P[pi]
        for i, (x, y) in enumerate(P):
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                reti = i
        return ret, reti

    prev = -2
    ans = -1

    used = {0}
    from random import randrange

    i = 0
    while True:
        ret, i = calc_dist(i)
        if ret == prev:
            ans = ret
        if ~ans and i in used:
            break
        if prev < ret:
            prev = ret

        if len(used) == N:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


t=0
m=0
for k in range(0,len(x)-1):
  for l in range(k,len(y)):
      if abs(x[k]-x[l])<t:
         m=m
      elif 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:
N = int(input())
listn =[]
for i in range(N):
    listn.append(list(map(int, input().split())))

listx = []

for i in range(N-1):
    for j in range(i+1,N):
        x = abs(listn[i][0] - listn[j][0]) + abs(listn[i][1] - listn[j][1])
        listx.append(x)
    
print(max(listx))

Submission status: Time Limit Exceeded

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


def solve(N: int, x: "List[int]", y: "List[int]"):
    t = 0
    for i in range(N):
        for j in range(N):
            t = max(t, abs(x[i]-x[j]) + abs(y[i]-y[j]))
    return print(t)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

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) == -1:
      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, Y = [], []
for _ in range(n):
  x,y = map(int, input().split())
  X.append(x)
  Y.append(y)

maximum = 0
for i in range(n):
  for j in range(i):
    tmp = abs(X[i]-X[j]) + abs(Y[i]-Y[j])
    if tmp > maximum:
      maximum = tmp
print(maximum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
cheby = []
for i in range(n):
    l = [xy[i][0]-xy[i][1],xy[i][0]+xy[i][1]]
    cheby.append(l)

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

Submission status: Time Limit Exceeded

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

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

    def calc_dist(pi):
        ret = -1
        reti = -1
        px, py = P[pi]
        for i, (x, y) in enumerate(P):
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                reti = i
        return ret, reti

    prev = -2
    ans = -1

    used = {0}
    from random import randrange

    i = 0
    while True:
        ret, i = calc_dist(i)
        if ret == prev:
            ans = ret
            if i in used:
                break
        if prev < ret:
            prev = ret

        if len(used) == N:
            break

        while i in used:
            i = randrange(0, N)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = [None]*n
y = [None]*n

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

biggest = 0
  
for a in range(n-1):
  for b in range(1,n):
    kyori = abs(x[a]-x[b])+abs(y[a]-y[b])
    if biggest < kyori:
      biggest = kyori
  
print(biggest)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xylist=[list(map(int,input().split())) for i in range(n)]
xylist.sort()
n=n//2+1
left=xylist[:n+1]
right=xylist[n-1:]

result=0
for i in range(len(left)):
    for j in range(len(right)):
        tmp=abs(left[i][0]-right[j][0])+abs(left[i][1]-right[j][1])
        if tmp > result:
            result=tmp

print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
a = sorted([list(map(int, input().split(" "))) for i in range(n)])
check = [True] + [False for i in range(n - 2)] + [True]
na = []
for i in range(1, n-1):
  if a[0][1] <= a[i][1] <= a[n-1][1] or a[0][1] >= a[i][1] >= a[n-1][1]:
    continue
  else:
    check[i] = True
for i in range(n):
  if check[i]:
    na.append(a[i])
maxi = 0
for (ix, iy), (jx, jy) in itertools.combinations(na, 2):
  maxi = max(maxi, max(jx, ix)-min(ix, jx) + max(iy, jy)-min(iy, jy))
print(maxi)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

P = []

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


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


def getLengest(nowIndex, points):
    maxscore = 0
    maxIndices = []

    for i in range(N):
        if i != nowIndex:
            ll = getMan(points[nowIndex], points[i])
            if maxscore <= ll:
                maxscore = ll
                maxIndices.append(i)
            elif maxscore < ll:
                maxscore = ll
                maxIndices = [i]
    #print(nowIndex, maxIndices, maxscore)
    return maxIndices, maxscore


maxs = 0
queue = [0]
already = []
while len(queue) > 0:
    now = queue[0]
    already.append(now)
    del(queue[0])
    nextIndices, score = getLengest(now, P)
    if maxs <= score:
        maxs = score
        for a in nextIndices:
            if a not in already:
                queue.append(a)
    elif maxs < score:
        maxs = score
        already = []
        for a in nextIndices:
            if a not in already:
                queue.append(a)

print(maxs)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x_arr = []
y_arr = []
total = []
for i in range(N):
    x, y = map(int, input().split())
    x_arr.append(x)
    y_arr.append(y)
for i in range(N):
    for i in range(N):
        if(i==N-1):
            break
        abs_sumx = abs(x_arr[i] - x_arr[i+1])
        abs_sumy = abs(y_arr[i] - y_arr[i+1])
        sum = abs_sumx + abs_sumy
        total.append(sum)
print(max(total))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
res = []
l1 = []
l2 = []
for i in range(n):
  a, b = map(int, input().split())
  l1.append(a)
  l2.append(b)
for i in range(n):
  for j in range(i, n):
    res.append(abs(l1[i] - l1[j]) + abs(l2[i] - l2[j]))

print(max(res))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

list_xy = []
for i in range(N):
    t = list(map(int, input().split()))
    
    if t not in list_xy:
        list_xy.append(t)

import itertools
mm_d = 0
for a , b in list(itertools.combinations(list_xy, 2)):
    m_d = abs(a[0]- b[0]) + abs(a[1] - b[1])
    
    if m_d > mm_d:
        mm_d = m_d
        
print(mm_d)

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 = abs(cd[i][0] - cd[j][0])
        d2 = abs(cd[i][1] - cd[j][1])
        md = max(md, d1, d2)

print(md)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xl, yl = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xl.append(x)
    yl.append(y)
xl_ = xl.copy()
yl_ = yl.copy()
xl_.sort()
yl_.sort()
xm = xl_[n//2-1]
ans = 0
for k in range(min(n, 1000)):
    ym = yl[k]
    ans1, ans2, ans3, ans4 = 0, 0, 0, 0
    for i in range(n):
        if xl[i] > xm:
            if yl[i] > ym:
                ans1 = max(ans1, abs(xl[i]-xm)+abs(yl[i]-ym))
            else:
                ans4 = max(ans4, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            if yl[i] > ym:
                ans2 = max(ans2, abs(xl[i]-xm)+abs(yl[i]-ym))
            else:
                ans3 = max(ans3, abs(xl[i]-xm)+abs(yl[i]-ym))
ans = int(max(abs(ans1+ans3), abs(ans2+ans4)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

P = []

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


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


def getLengest(nowIndex, points):
    maxscore = 0
    maxIndices = []

    for i in range(N):
        if i != nowIndex:
            ll = getMan(points[nowIndex], points[i])
            if maxscore <= ll:
                maxscore = ll
                maxIndices.append(i)
            elif maxscore < ll:
                maxscore = ll
                maxIndices = [i]
    #print(nowIndex, maxIndices, maxscore)
    return maxIndices, maxscore


maxs = 0
queue = [0]
already = []
while len(queue) > 0:
    now = queue[0]
    already.append(now)
    del(queue[0])
    nextIndices, score = getLengest(now, P)
    if maxs <= score:
        maxs = score
        for a in nextIndices:
            if a not in already:
                queue.append(a)

print(maxs)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M=N*N
x = [0] * N
y = [0] * N
z=[]
for i in range(0,N):
    x[i], y[i] = map(int, input().split())
for i in range(0,M):
    z.append(abs(x[i//N]-x[i%N])+abs(y[i//N]-y[i%N]))
print(max(z))

Submission status: Time Limit Exceeded

Solution code:
def dist(a,b):
  d = a - b
  if d < 0:
    return -(d)
  else:
    return d

def max_dist_set(a_set,b_set):
  max_d = 0
  for a in a_set:
    for b in b_set:
      d = dist(a,b)
      if d > max_d:
        max_d = d
  return max_d

N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
  x[i],y[i] = map(int,input().split())
xi = dist(x[0], x[1])
yi = dist(y[0], y[1])
max = xi + yi
for i in range(N):
  for j in range(N-i):
    xi = dist(x[i], x[j])
    yi = dist(y[i], y[j])
    if xi + yi > max:
      max = xi + yi
print(max)

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+1,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())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        ans=max(ans,abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

min_diff = 10**9
max_diff = 1
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

cand_set = set()
for x,y in XY:
    if x-y in (min_diff, max_diff) or x+y in (min_sum, max_sum):
        cand_set.add((x, y))

dist = 0
for p1, p2 in combinations(cand_set, 2):
    dist = max(dist, abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]))
    
print(dist)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=[input() for i in range(a)]

c=[]
for i in b:
	n=i.split()
	c.append(n)

kyori=[]

for i in range(len(c)):
	for j in range(len(c)):
		man_kyori=abs(int(c[i][0])-int(c[j][0])+abs(int(c[i][1])-int(c[j][1])))
		kyori.append(man_kyori)

print(max(kyori))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = list()
for i in range(N):
  A.append(list(map(int,input().split())))
ret = 0
for i in range(N-1):
  for j in range(i + 1,N):
    tmp = abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1])
    if ret < tmp:
      ret = tmp
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
dis_max = 0

XY = []
count = 0
for i in range(N):
  xy = list(map(int,input().split()))
  if xy not in XY:
    XY.append(xy)
    count += 1

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


def get_output():
    result = 0
    for i, x1y1 in enumerate(xy):
        for j, x2y2 in enumerate(xy[i+1:]):
            result = max(result, abs(x1y1[0] - x2y2[0]) + abs(x1y1[1] - x2y2[1]))
    return result


print(get_output())

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

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


def main():
    N = NI()
    xy = [NLI() for _ in range(N)]
    
    if N == 2:
        convex_ls = xy
    else:
        convex_ls = convex_hull(xy)
    

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


if __name__ == '__main__':
    main()

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(i+1, N):
        tmp = abs(list_x[i] - list_x[j]) + abs(list_y[i] - list_y[j])
        tmp2 = abs(list_x[j] - list_x[i]) + abs(list_y[j] - list_y[i])
        if tmp > ans:
            ans = tmp
        if tmp2 > ans:
            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*10**10 + y)

s = 0
for i,x in enumerate(xy):
    for a in xy[i:]:
        s = max(s, abs(x//10**10-a//10**10)+abs(x%10**10-a%10**10))
        # print(x,a, abs(x//10**10-a//10**10), abs(x%10**10-a%10**10))

print(s)

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 j in range(i):
        ans = max(ans,(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1])))

# 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:
import sys
sys.setrecursionlimit(2000)

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:
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)
X=set(range(N))

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
        Y=set()
        while True:
            M=-1
            Old_Old_I=Old_I
            Old_I=I
            for i in X:
                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

        X-=Y
        D.append(dist(P[Old_I],P[J]))

print(max(D))

Submission status: Time Limit Exceeded

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

lg = 0
for i in range(a):
  for j in range(i,a):
    tl = abs(b[i][0] - b[j][0]) + abs(b[i][1] - b[j][1])
    lg = tl if tl > lg else lg

print(lg)

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())
  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:
import numpy as np
N = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(N)])

ans = 0
for i, (x1, y1) in enumerate(xy[:-1]):
    x_list = xy[i+1:,0]
    y_list = xy[i+1:,1]
    x_list = np.abs(x_list-x1)
    y_list = np.abs(y_list-y1)
    ans = max(ans, np.max(x_list+y_list))
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np  
from scipy.spatial.distance import euclidean, cityblock  

N = int(input())

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

m_max = 0
for i in range(len(XY)):
  a= np.array(XY[i])
  for j in range(i+1,len(XY)):
    b = np.array(XY[j])
    m = cityblock(a, b)
    m_max = max(m,m_max)
print(m_max)

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):
    ss = abs(pair[0][0] - pair[1][0])+abs(pair[0][1] - pair[1][1])
    #ans.append(abs(pair[0][0] - pair[1][0])+abs(pair[0][1] - pair[1][1]))
    ans.append(ss)

print(max(ans))