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

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
from itertools import accumulate
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def floor(a, b): return -(-a // b)


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


N = z()
X, Y = [], []
dist = [0]*(N)  # 原点からの距離
for i in range(N):
    x, y = zz()
    x, y = x+y, x-y

    X.append(x)
    Y.append(y)

a = sorted(X)
print(a[-1] - a[0])

Submission status: Wrong Answer

Solution code:
n = int(input())

edge0 = list(map(lambda x: int(x), input().split()))
edge1 = list(map(lambda x: int(x), input().split()))
dis = abs(edge0[0]-edge1[0]) + abs(edge0[1]-edge1[1])

for _ in range(n-2):
    x, y = map(lambda x: int(x), input().split())
    if (x < min(edge0[0], edge1[0])) | (max(edge0[0], edge1[0]) < x) | (y < min(edge0[1], edge1[1])) | (max(edge0[1], edge1[1]) < y):
            dis_from_edge0 = abs(x-edge0[0]) + abs(y-edge0[1])
            dis_from_edge1 = abs(x-edge1[0]) + abs(y-edge1[1])

#             print(dis_from_edge0, dis_from_edge1)
            # 更新なし
            if max(dis_from_edge0, dis_from_edge1) <= dis:
#                 print('#1', edge0, edge1, dis)
                continue
            # どちらも更新
            if min(dis_from_edge0, dis_from_edge1) > dis:
                if dis_from_edge0 < dis_from_edge1:
                    dis  = dis_from_edge1
                    edge0 = [x, y]
                else:
                    dis = dis_from_edge0
                    edge1 = [x, y]
#                 print('#2', edge0, edge1, dis)
                continue
            if dis_from_edge0 > dis_from_edge1:
                dis = dis_from_edge0
                edge1 = [x, y]
#                 print('#3', edge0, edge1, dis)
                continue
            else:
                dis = dis_from_edge1
                edge0 = [x, y]
                continue
            h
print(dis)

    #     x_max = max(x, x_max)
    #     x_min = min(x, x_min)
    #     y_max = max(y, y_max)
    #     y_min = min(y, y_min)

Submission status: Wrong Answer

Solution code:
N = int(input())
i, j, k = 0, 0, 0
x = [0]
y = [0]
while i < N:
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)
    ma = max(x[i]*y[i], x[i-1]*y[i-1])
    mi = min(x[i]*y[i], x[i-1]*y[i-1])
    if ma == x[i]*y[i]:
        cma = i
    if mi == x[i]*y[i]:
        cmi = i
    i += 1
print(abs(x[cma] - x[cmi]) + abs(y[cma] - y[cmi]))

Submission status: Wrong Answer

Solution code:
import math
#N = map(int,input().split())
#AB=[]
N = int(input())
#C = input()
#D, T, S=map(int,input().split())
C = []
D = []
for i in range(N):
    al = list(map(int,input().split()))
    if al not in C:
        C.append(al)
        D.append([al[0]-al[1],al[0]+al[1]])
min0 = 1000000000
max0 = 0
min1 = 1000000000
max1 = 0
for i in D:
    if max0 < i[0]:
        max0 = i[0]
    if min0 > i[0]:
        min0 = i[0]
    if max1 < i[1]:
        max1 = i[1]
    if min1 > i[1]:
        min1 = i[1]

print(max(max0-min0, max1-min1))

Submission status: Wrong Answer

Solution code:
def Manhattan(ans):
    return abs(ans[0][0]-ans[1][0])+abs(ans[0][1]-ans[1][1])
N=int(input())
xy=[]
for i in range(N):
    xy.append(list(map(int,input().split())))
nowans=[[xy[0][0],xy[0][1]],[xy[1][0],xy[1][1]]]
nowManhattan=Manhattan(nowans)
for j in range(3):
    for i in range(0,N-1):
        nowxy=xy[i]
        if (Manhattan([nowxy,nowans[1]])>nowManhattan):
            nowans=[nowxy,nowans[1]]
            nowManhattan=Manhattan(nowans)
        if (Manhattan([nowans[0],nowxy])>nowManhattan):
            nowans=[nowans[0],nowxy]
            nowManhattan=Manhattan(nowans)
print(nowManhattan)

Submission status: Wrong Answer

Solution code:
from sys import stdin

readline = stdin.readline

N = int(readline())
xy = [tuple(map(int, readline().split())) for _ in range(N)]

xy = list(set(xy))

xy.sort()

c = set(xy[:1500])
c = c | set(xy[-1500:])

xy.sort(key=lambda x: x[1])

c = c | set(xy[:1500])
c = c | set(xy[-1500:])

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

Submission status: Wrong Answer

Solution code:
n = int(input())
lst, result = [], []

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

lst = sorted(lst, key=lambda x:x[2])

print(abs(lst[n - 1][0] - lst[0][0]) + abs(lst[n-1][1] - lst[0][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
ru = [0, 0]
rb = [0, 10 ** 9]
lu = [10 ** 9, 0]
lb = [10 ** 9, 10 ** 9]
for i in range(n):
  x, y  = [int(x) for x in input().split()]
  if x >= ru[0] and y >= ru[1]:
    ru[0] = x
    ru[1] = y
  if x >= rb[0] and y <= rb[1]:
    rb[0] = x
    rb[1] = y
  if x <= lu[0] and y >= lu[1]:
    lu[0] = x
    lu[1] = y
  if x <= lb[0] and y <= lb[1]:
    lb[0] = x
    lb[1] = y
print(max(ru[0] - lb[0] + ru[1] - lb[1], rb[0] - lu[0] + lu[1] - rb[1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
x, y = [], []
for i in range(N):
    x_i, y_i = map(int, input().split())
    x.append(x_i)
    y.append(y_i)
max_list = [[x[0], y[0]], [x[1], y[1]]]
max_m = abs(x[0]-x[1]) + abs(y[0]-y[1])
for i in range(2, N):
    a = abs(x[i]-max_list[0][0]) + abs(y[i]-max_list[0][1])
    b = abs(x[i]-max_list[1][0]) + abs(y[i]-max_list[1][1])
    if max(a, b) > max_m:
        max_m = max(a, b)
        if max(a, b) == a:
            max_list[1][0] = x[i]
            max_list[1][1] = y[i]
        else:
            max_list[0][0] = x[i]
            max_list[0][1] = y[i]
print(max_m)

Submission status: Wrong Answer

Solution code:
from sys import *
N = int(stdin.readline())
a = []

for i in range(N):
    tmp = list(map(int, stdin.readline().split()))
    a.append(tmp)
a.sort(key = lambda k: k[0]+k[1])
best = 0
for i in range(N-1):
    best = max(best, abs(a[i][0] - a[-1][0]) + abs(a[i][1] - a[-1][1]))

print(best)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())

listA=[]

while True:
    try:
      a,b=map(int, input().split())
      listA.append(a+b)

    except:
        break;

print(max(listA)-min(listA))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator import itemgetter

n = int(input())
XY = list(set(tuple(int(x) for x in input().split()) for _ in range(n)))
X = sorted(XY, key=itemgetter(0))
Y = sorted(XY, key=itemgetter(1))
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
ans = 0
if len(XY) == 1:
    print(0)
    exit()
if len(XY) < 3000:
    for a, b in combinations(XY, 2):
        ans = max(ans, dist(a, b))
else:
    A = X[:1200] + X[-1200:] + Y[:1200] + Y[-1200:]
    for a, b in combinations(A, 2):
        ans = max(ans, dist(a, b))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
l=[]
for i in range(n):
  l.append(list(map(int,list(input().split()))))
l.sort()
m = sorted(l,key = lambda y:y[1])
x,y=0,0
for i in range(1,n):
  p = abs(l[i][0]-l[0][0])+abs(l[i][1]-l[0][0])
  if p>x:
    x=p
  q = abs(m[i][0]-m[0][0])+abs(m[i][1]-m[0][0])
  if q>y:
    y=q  
    
print(max(x,y))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
ll = []
for _ in range(n):
    x, y = map(int, input().split())
    l.append((x+y, x, y))
    ll.append((x-y, x, y))
l.sort()
ll.sort()
ans1 = 0
ans2 = 0
#print(l)
#print(ll)

cnt = 0
while True:
    a = l[n-1-cnt]
    b = l[cnt]
    #print(a, b)
    if a[1] >= b[1] and a[2] >= b[2]:
        ans1 = abs(b[0]-a[0])
        #print(ans1, a, b)
        break
    if cnt >= n-1:
        break
    cnt += 1

cnt = 0
while True:
    a = l[n-1-cnt]
    b = l[cnt]
    if a[1] >= b[1] and b[2] >= a[2]:
        ans2 = abs(b[0]-a[0])
        #print(ans2, a, b)
        break
    if cnt >= n-1:
        break
    cnt += 1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy=sorted(xy, key=lambda x:x[0])
m=0
mi=-1
Mi=-1
M=0
res=[]
ans=0
for i in range(1,n):
    x,y=xy[i]
    if y<=m:
        mi=i
    if y>=M:
        Mi=i
    res.append([mi,Mi])
for i in range(n-1):
    x,y=xy[i]
    rm,rM=res[i]
    xm,ym=xy[rm]
    xM,yM=xy[rM]
    c=max((abs(x-xm)+abs(y-ym)),(abs(x-xM)+abs(y-yM)))
    ans=max(c,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=0
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):#左下
    local=x[i][0]+x[i][1]
    if local<hidarisita:
        hidarisita=local
for i in range(0,n):#右上
    local=x[i][0]+x[i][1]
    if local>migiue:
        migiue=local
for i in range(0,n):#左上
    local=x[i][0]+10*9-x[i][1]
    if local>hidariue:
        hidariue=local
for i in range(0,n):#右下
    local=10**9-x[i][0]+x[i][1]
    if local<migisita:
        migsita=local

print(max(migiue-hidarisita,hidariue-migisita))

Submission status: Wrong Answer

Solution code:
def Manhattan(ans):
    return abs(ans[0][0]-ans[1][0])+abs(ans[0][1]-ans[1][1])
N=int(input())
xy=[]
for i in range(N):
    xy.append(list(map(int,input().split())))
nowans=[[xy[0][0],xy[0][1]],[xy[1][0],xy[1][1]]]
nowManhattan=Manhattan(nowans)
for j in range(2):
    for i in range(1,N-1):
        nowxy=xy[i]
        if (Manhattan([nowxy,nowans[1]])>nowManhattan):
            nowans=[nowxy,nowans[1]]
            nowManhattan=Manhattan(nowans)
        if (Manhattan([nowans[0],nowxy])>nowManhattan):
            nowans=[nowans[0],nowxy]
            nowManhattan=Manhattan(nowans)
print(nowManhattan)

Submission status: Wrong Answer

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

z.sort()
mdct = 0
lx, ly = z[0]
for x, y in z:
  mdct = max(mdct, abs(x-lx) + abs(y-ly))
  
z.sort(key=lambda k: k[1])
lx, ly = z[0]
for x, y in z:
  mdct = max(mdct, abs(x-lx) + abs(y-ly))
print(mdct)

Submission status: Wrong Answer

Solution code:
n = int(input())
max_t = -float('inf')
min_t = float('inf')
for _ in range(n):
  x, y = map(int, input().split())
  c = x + y
  if c > max_t:
    max_t = c
  if c < min_t:
    min_t = c
print(max_t - min_t)

Submission status: Wrong Answer

Solution code:
N=int(input())
x_numbers=[]
y_numbers=[]
for _ in range(N):
    x,y=map(int,input().split())
    x_numbers.append([x,y])
    y_numbers.append([y,x])
sort_x_numbers=sorted(x_numbers,reverse=True)
sort_y_numbers=sorted(y_numbers,reverse=True)
ans1=[]
ans2=[]
ans3=[]
ans4=[]
x3=sort_x_numbers[0]
x1=sort_x_numbers[-1]
for n in x_numbers:
    ans1.append(abs(n[0]-x1[0])+abs(n[1]-x1[1]))
for n in x_numbers:
    ans3.append(abs(n[0]-x3[0])+abs(n[1]-x3[1]))
ans11=max(ans1)
ans33=max(ans3)
x2=sort_y_numbers[-1]
x4=sort_y_numbers[0]
for n in x_numbers:
    ans2.append(abs(n[0]-x2[1])+abs(n[1]-x2[0]))
for n in x_numbers:
    ans4.append(abs(n[0]-x4[1])+abs(n[1]-x4[0]))
ans22=max(ans2)
ans44=max(ans4)
print(max(ans11,ans22,ans33,ans44))

Submission status: Wrong Answer

Solution code:
n = int(input())
r = [0,0]
l = [10**9+1,10**9+1]
for _ in range(n):
    a, b = map(int, input().split())
    if a >= r[0] and b >= r[1]:
        r = [a, b]
    if a <= l[0] and b <= l[1]:
        l = [a, b]

res = abs(r[0]-l[0])+abs(r[1]-l[1])
print(res)

Submission status: Wrong Answer

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
    maxIndex = -1

    for i in range(N):
        if i != nowIndex:
            ll = getMan(points[nowIndex], points[i])
            if maxscore <= ll:
                maxscore = ll
                maxIndex = i

    return maxIndex, maxscore


now = 0
maxs = 0
while True:
    nextIndex, score = getLengest(now, P)
    if maxs < score:
        maxs = score
        now = nextIndex
    else:
        print(score)
        break

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(N):
  x, y = map(int, input().split())
  if i==0:
    x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6 = x, y, x, y, x, y, x, y, x, y, x, y
    tmax, tmin = x+y, x+y
    xmax, xmaxy, ymaxx, ymax, xmin, xminy, yminx, ymin = x, y, x, y, x, y, x, y
  else:
    if x<x1 and y<y1:
      x1, y1 = x, y
    elif x<x2 and y>y2:
      x2, y2 = x, y
    elif x>x3 and y>y3:
      x3, y3 = x, y
    elif x>x4 and y<y4:
      x4, y4 = x, y
    elif x+y < tmin:
      x5, y5 = x, y
      tmin = x + y
    elif x+y > tmax:
      x6, y6 = x, y
      tmax = x + y
    elif x > xmax:
      xmax = x
      xmaxy = y
    elif y > ymax:
      ymax = y
      ymaxx = x
    elif x < xmin:
      xmin = x
      xminy = y
    elif y < ymin:
      ymin = y
      yminx = x
     
print(max(abs(x1-x3)+abs(y1-y3),abs(x2-x4)+abs(y2-y4),abs(x5-x6)+abs(y5-y6),
         abs(xmax-xmin)+abs(xmaxy-xminy),abs(ymaxx-yminx)+abs(ymax-ymin)))

Submission status: Wrong Answer

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

mm = (10**9)*2
mmn = 0

pm = 10**9
pmn = 0

mp = 10**9
mpn = 0

pp = 0
ppn = 0

for j in range (N):
    if (A[j]+B[j])>pp:

        pp = A[j]+B[j]
        ppn = j
    if (A[j]-B[j])>pm:

        pm = A[j]-B[j]
        pmn = j
    if (B[j]-A[j])>mp:

        mp = B[j]-A[j]
        mpn = j
    if (A[j]+B[j])<mm:

        mm = A[j]+B[j]
        mmn = j
ans1 = abs(A[ppn] - A[mmn]) + abs(B[ppn] - B[mmn])
ans2 = abs(A[pmn] - A[mpn]) + abs(B[mpn] - B[pmn])
ans3 = abs(A[ppn] - A[pmn]) + abs(B[ppn] - B[pmn])
ans4 = abs(A[mmn] - A[mpn]) + abs(B[mmn] - B[pmn])
ans = max(ans1,ans2,ans3,ans4)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
point_sum = []
for i in range(n):
  a,b = map(int, input().split())
  point_sum.append(max(a+b,a-b,b-a))
print(max(point_sum) - min(point_sum))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

m1 = A[0]
m2 = A[1]
mx = abs(A[0][0] - A[1][0]) + abs(A[0][1] - A[1][1])


def calc_length(m1, m2):
    return abs(m1[0] - m2[0]) + abs(m1[1] - m2[1])


for i in range(2, N):
    l1 = calc_length(m1, A[i])
    l2 = calc_length(m2, A[i])
    if l1 > mx and l2 > mx:
        if l1 > l2:
            m2 = A[i]
            mx = l1
        else:
            m1 = A[i]
            mx = l2
    elif l1 > mx:
        m2 = A[i]
        mx = l1
    elif l2 > mx:
        m1 = A[i]
        mx = l2

print(mx)

Submission status: Wrong Answer

Solution code:
n = int(input())
str_list = [list(input().split()) for _ in range(n)]
count = 0
u = 0
for n in str_list:
    if count == 0:
        m = n
        count +=1
        continue
    if abs(int(n[0])-int(m[0])) + abs(int(n[1])-int(m[1])) > u:
        u = abs(int(n[0])-int(m[0])) + abs(int(n[1])-int(m[1]))
    m = n
    count +=1
print(u)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
x1, y1 = map(int, input().split())
centre = [x1, y1]

left_bottom = [x1, y1]
left_bottom_dist = 0

left_top = [x1, y1]
left_top_dist = 0

right_bottom = [x1, y1]
right_bottom_dist = 0

right_top = [x1, y1]
right_top_dist = 0

List = [[x1, y1]]
for i in range(N-1):
  xi, yi = map(int, input().split())
  List += [[xi, yi]]
  if xi <= x1 and yi <= y1:
    if x1 - xi + y1 - yi >= left_bottom_dist:
      left_bottom = [xi, yi]
      left_bottom_dist = x1 - xi + y1 - yi
  if xi <= x1 and yi >= y1:
    if x1 - xi + yi - y1 >= left_top_dist:
      left_top = [xi, yi]
      left_top_dist = x1 - xi + yi - y1
  if xi >= x1 and yi <= y1:
    if xi - x1 + y1 - yi >= right_bottom_dist:
      right_bottom = [xi, yi]
      right_bottom_dist = xi - x1 + y1 - yi 
  if xi >= x1 and yi >= y1:
    if xi - x1 + yi - y1 >= right_top_dist:
      right_top = [xi, yi]
      right_top_dist = xi - x1 + yi - y1

D1 = abs(right_top[0] - left_bottom[0]) + abs(right_top[1] - left_bottom[1])
D2 = abs(right_bottom[0] - left_top[0]) + abs(right_bottom[1] - left_top[1])
D3 = abs(left_top[0] - left_bottom[0]) + abs(left_top[1] - left_bottom[1])
D4 = abs(right_top[0] - right_bottom[0]) + abs(right_top[1] - right_bottom[1])
D5 = abs(left_top[0] - right_top[0]) + abs(left_top[1] - right_top[1])
D6 = abs(left_bottom[0] - right_bottom[0]) + abs(left_bottom[1] - right_bottom[1])

d1 = max(D1, D2, D3, D4, D5, D6)

List.reverse()
x1, y1 = List[0][0], List[0][1]
centre = [x1, y1]

left_bottom = [x1, y1]
left_bottom_dist = 0

left_top = [x1, y1]
left_top_dist = 0

right_bottom = [x1, y1]
right_bottom_dist = 0

right_top = [x1, y1]
right_top_dist = 0

for i in range(N-1):
  xi, yi = List[i + 1]
  if xi <= x1 and yi <= y1:
    if x1 - xi + y1 - yi >= left_bottom_dist:
      left_bottom = [xi, yi]
      left_bottom_dist = x1 - xi + y1 - yi
  if xi <= x1 and yi >= y1:
    if x1 - xi + yi - y1 >= left_top_dist:
      left_top = [xi, yi]
      left_top_dist = x1 - xi + yi - y1
  if xi >= x1 and yi <= y1:
    if xi - x1 + y1 - yi >= right_bottom_dist:
      right_bottom = [xi, yi]
      right_bottom_dist = xi - x1 + y1 - yi 
  if xi >= x1 and yi >= y1:
    if xi - x1 + yi - y1 >= right_top_dist:
      right_top = [xi, yi]
      right_top_dist = xi - x1 + yi - y1

D1 = abs(right_top[0] - left_bottom[0]) + abs(right_top[1] - left_bottom[1])
D2 = abs(right_bottom[0] - left_top[0]) + abs(right_bottom[1] - left_top[1])
D3 = abs(left_top[0] - left_bottom[0]) + abs(left_top[1] - left_bottom[1])
D4 = abs(right_top[0] - right_bottom[0]) + abs(right_top[1] - right_bottom[1])
D5 = abs(left_top[0] - right_top[0]) + abs(left_top[1] - right_top[1])
D6 = abs(left_bottom[0] - right_bottom[0]) + abs(left_bottom[1] - right_bottom[1])

d2 = max(D1, D2, D3, D4, D5, D6)
print(max(d1, d2))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = 0
Xmin = Ymin = 1e9 + 5
Xmax = Ymax = 0
for _ in range(N):
    x, y = map(int, input().split())
    X = x + y
    Y = abs(x - y)
    Xmin = min(Xmin, X)
    Xmax = max(Xmax, X)
    Ymin = min(Ymin, Y)
    Ymax = max(Ymax, Y)
Z = max(Xmax - Xmin, Ymax - Ymin)
print(Z)

Submission status: Wrong Answer

Solution code:
n = int(input())
maxPlus, minPlus, maxMinus, minMinus = 0, 10**9 , 0, 10**9
for _ in range(n):
    x, y = map(int, input().split())
    maxPlus = max(x + y, maxPlus)
    minPlus = min(x + y, minPlus)
    maxMinus = max(x - y, maxMinus)
    minMinus = min(x - y, minMinus)
print(max(abs(maxPlus - minPlus), abs(maxMinus - minMinus)))

Submission status: Wrong Answer

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

if (xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) >= 0:
    defa1 = 1
    defa2 = 2
elif (xlis[2]-xlis[1]) + (ylis[2]-ylis[1]) <= 0:
    defa1 = 2
    defa2 = 1

for i in range(1, n+1):
    new1 = i
    defa1p = (xlis[defa1], ylis[defa1])
    defa2p = (xlis[defa2], ylis[defa2])
    new1p = (xlis[new1], ylis[new1])

    if (new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) >= 0:
        defa2 = new1
    elif (new1p[0]-defa2p[0])+(new1p[1]-defa2p[1]) <= 0 <= (new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]):
        pass
    elif (new1p[0]-defa1p[0])+(new1p[1]-defa1p[1]) <= 0:
        defa1 = new1


print((xlis[defa2]-xlis[defa1]) + (ylis[defa2]-ylis[defa1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
maxx = -10 ** 10

result = [0]
for i in range(n):
  if maxx <= x[i]:
    for j in range(n):
      result.append(abs(x[i] - x[j]) + abs(y[i] - y[j]))
      maxx = x[i]
print(max(result))

Submission status: Wrong Answer

Solution code:
n=int(input())

mhd=lambda x,y: abs(x[0]-y[0])+abs(x[1]-y[1])
dis=0
x,y=map(int,input().split())
c=(x,y)
M,m=c,c
for i in range(n-1):
    x,y=map(int,input().split())
    c=(x,y)
    if x>=M[0] or y>=M[0]:
        if mhd(c,m)>dis:
            M=c
            dis=mhd(c,m)
    if x<=m[0] or y<=m[0]:
        if mhd(c,M)>dis:
            m=c
            dis=mhd(c,M)
print(dis)

Submission status: Wrong Answer

Solution code:
N = int(input())
i = []
j = []
for k in range(N):
    x, y = map(int, input().split())
    i.append(x+y)
    j.append(-x-y)

print(max(max(i)+max(j), abs(min(i)+min(j))))

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=set(tuple([lnii() for i in range(n)]))

if len(l)==1:
  print(0)
  exit()

x_max=0
x_min=10**10
y_max=0
y_min=10**10
for x,y in l:
#  s=abs(x-y)
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

#  t=abs(x+y)
  t=x+y
  y_max=max(y_max,t)
  y_mim=min(y_min,t)


x_max=abs(x_max)
x_min=abs(x_min)
y_max=abs(y_max)
y_min=abs(y_min)
print(x_max,x_min,y_max,y_min)


print(max(x_max-x_min,x_max-y_min,y_max-y_min,y_max-x_min))

Submission status: Wrong Answer

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

if n%2:
    xm, ym = xl_[n//2], yl_[n//2]
else:
    xm, ym = (xl_[n//2-1]+xl_[n//2])//2, (yl_[n//2-1]+yl_[n//2])//2

xm, ym = xm-1e-6, ym-1e-6
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)))

xm, ym = xm+1e-6, ym+1e-6
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))

xm, ym = xm-1e-6, ym+1e-6
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))

xm, ym = xm+1e-6, ym-1e-6
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 = max(ans, int(max(abs(ans1+ans3), abs(ans2+ans4))))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator import itemgetter

n = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(n)]
X = sorted(XY, key=itemgetter(0))
Y = sorted(XY, key=itemgetter(1))
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
ans = 0
if n < 3000:
    for a, b in combinations(XY, 2):
        ans = max(ans, dist(a, b))
else:
    A = X[:1000] + X[-1000:] + Y[:1000] + Y[-1000:]
    for a, b in combinations(A, 2):
        ans = max(ans, dist(a, b))
print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
det = lambda p, q: p[0] * q[1] - p[1] * q[0]
sub = lambda p, q: (p[0] - q[0], p[1] - q[1])


def get_convex_hull(points):
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n - 2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]


mdist = -1
X = get_convex_hull(X)
used = [0] * len(X)
for index, start in enumerate(X):
    if used[index] == 1:
        continue
    sx, sy = start
    maxv = -1
    maxi = -1
    for i, xi in enumerate(X):
        if i == index:
            continue
        x, y = xi
        x, y = x - sx, y - sy
        xx, yy = x + y, x - y
        dist = max(abs(xx), abs(yy))
        # print("dist", dist)
        if maxv < dist:
            maxi = i
            maxv = dist
    # print("index, maxi", index, maxi)
    used[maxi] = 1
    mdist = max(mdist, maxv)

print(mdist)

Submission status: Wrong Answer

Solution code:
N = int(input())
v = [list(map(int, input().split())) for i in range(N)]
v.sort(key = lambda x:abs(x[0]) + abs(x[1]))
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(d)

Submission status: Wrong Answer

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

def main(args):
    n = int(input())
    
    minx = float('inf')
    maxx = 0
    miny = float('inf')
    maxy = 0
    
    place = []
    for i in range(n):
        x, y = map(int,input().split())
        minx = min(minx,x)
        maxx = max(maxx,x)
        miny = min(miny,y)
        maxy = max(maxy,y)
        place.append((x,y))
    
    Minx = []
    Maxx = []
    Miny = []
    Maxy = []
    
    for x, y in place:
        if x == minx:
            Minx.append((x,y))
        elif x == maxx:
            Maxx.append((x,y))
        if y == miny:
            Miny.append((x,y))
        elif y == maxy:
            Maxy.append((x,y))
    
    if not Maxx:
        print(maxy-miny)
        exit()
    if not Maxy:
        print(maxx-minx)
        exit()
    
    ans = 0
    for i in range(len(Maxx)):
        xi, yi = Maxx[i]
        for j in range(len(Minx)):
            xj, yj = Minx[j]
            tmp = abs(xi-xj)+abs(yi-yj)
            ans = max(tmp,ans)
    
    for i in range(len(Maxy)):
        xi, yi = Maxy[i]
        for j in range(len(Miny)):
            xj, yj = Miny[j]
            tmp = abs(xi-xj) + abs(yi-yj)
            ans = max(ans,tmp)
    
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
N=int(input())
x_numbers=[]
y_numbers=[]
for _ in range(N):
    x,y=map(int,input().split())
    x_numbers.append([x,y])
    y_numbers.append([y,x])
sort_x_numbers=sorted(x_numbers)
sort_y_numbers=sorted(y_numbers)
ans1=[]
ans2=[]
ans3=[]
ans4=[]
x3=sort_x_numbers[0]
x1=sort_x_numbers[-1]
for n in x_numbers:
    ans1.append(abs(n[0]-x1[0])+abs(n[1]-x1[1]))
for n in x_numbers:
    ans3.append(abs(n[0]-x3[0])+abs(n[1]-x3[1]))
ans11=max(ans1)
ans33=max(ans3)
x2=sort_y_numbers[-1]
x4=sort_y_numbers[0]
for n in x_numbers:
    ans2.append(abs(n[0]-x2[1])+abs(n[1]-x2[0]))
for n in x_numbers:
    ans4.append(abs(n[0]-x4[1])+abs(n[1]-x4[0]))
ans22=max(ans2)
ans44=max(ans4)
ans=max(ans11,ans22,ans33,ans44)
sort_x_numbers=sorted(x_numbers,reverse=True)
sort_y_numbers=sorted(y_numbers,reverse=True)
ans1=[]
ans2=[]
ans3=[]
ans4=[]
x3=sort_x_numbers[0]
x1=sort_x_numbers[-1]
for n in x_numbers:
    ans1.append(abs(n[0]-x1[0])+abs(n[1]-x1[1]))
for n in x_numbers:
    ans3.append(abs(n[0]-x3[0])+abs(n[1]-x3[1]))
ans11=max(ans1)
ans33=max(ans3)
x2=sort_y_numbers[-1]
x4=sort_y_numbers[0]
for n in x_numbers:
    ans2.append(abs(n[0]-x2[1])+abs(n[1]-x2[0]))
for n in x_numbers:
    ans4.append(abs(n[0]-x4[1])+abs(n[1]-x4[0]))
ans22=max(ans2)
ans44=max(ans4)
print(max(ans,ans11,ans22,ans33,ans44))