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

for j in range(100):
    s = dist.index(max(dist))
    for i in range(N):
        dist[i] = abs(xy[i][0] - xy[s][0]) + abs(xy[i][1] - xy[s][1])
print(max(dist))

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[]
Y=[]
for i in range(n):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
fX=[]
fY=[]
for i in range(n):
    fX.append(X[i]+Y[i])
    fY.append(X[i]-Y[i])
xmax=0
xmin=2**62
ymax=0
ymin=2**62
for i in range(n):
    xmax=max(xmax,fX[i])
    xmin=min(xmin,fX[i])
    ymax=max(ymax,fY[i])
    ymin=min(ymin,fY[i])
print(max(xmax-xmin,ymax-ymin))

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = []
for _ in range(N):
    x,y = map(int, input().split())
    s = x+y
    t = x-y
    d = max(s,t)
    ls.append(d)
print(max(ls) - min(ls))

Submission status: Wrong Answer

Solution code:
n=int(input())
ma=2
mi=10**9
mu=2
me=10**9
for i in range(n):
    x,y=map(int,input().split())
    l=x+y
    s=-x+10**9+y
    ma=max(ma,l)
    mi=min(mi,l)
    mu=max(mu,s)
    me=min(me,s)
print(max(ma-mi,mu-me))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
XY = []
xAve = 0
yAve = 0
for _ in range(N):
    x,y=map(int,input().split())
    XY.append([x,y])
    xAve += x
    yAve += y
xAve = xAve//N
yAve = yAve//N
XYnorm = [0]*4
for x,y in XY:
    nX = x-xAve
    nY = y-yAve
    if nX>=0 and nY>=0:#第1象限
        XYnorm[0]=max(XYnorm[0],nX+nY)
    if nX <=0 and nY >=0:#第2象限
        XYnorm[1]=max(XYnorm[1],-nX+nY)
    if nX <=0 and nY <=0:#第3象限
        XYnorm[2]=max(XYnorm[2],-nX-nY)
    if nX >=0 and nY <=0:#第4象限
        XYnorm[3]=max(XYnorm[3],nX-nY)
print(max(XYnorm[2]+XYnorm[0],XYnorm[3]+XYnorm[1]))

Submission status: Wrong Answer

Solution code:
n = int(input())

dist = []

for i in range(n):
    x, y = map(int, input().split())
    dist.append(x + y)

dist.sort()

print(abs(dist[0] - dist[-1]))

Submission status: Wrong Answer

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

minS = float("INF")
maxS = -1
for i in range(N):
    x, y = Point[i][0], Point[i][1]
    if x+y < minS:
        minS = x+y
        minI = i
    if x+y > maxS:
        maxS = x+y
        maxI = i

ans = abs(Point[maxI][0] - Point[minI][0]) + abs(Point[maxI][1] - Point[minI][1])
print(ans)

Submission status: Wrong Answer

Solution code:
input = input()

Submission status: Wrong Answer

Solution code:
N = int(input())
List = set([])
x,y = map(int,input().split())
for i in range(N-1):
    x1,y1 = map(int,input().split())
    List.add(abs(x-x1)+abs(y-y1))
    x,y= x1,y1
print(max(List))

Submission status: Wrong Answer

Solution code:
N = int(input())

l = [None] * N

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

minX = min([e[0] for e in l])
minY = min([e[1] for e in l])
maxX = max([e[0] for e in l])
maxY = max([e[1] for e in l])

p = [None] * 8
p[0] = [minX, min([e[1] for e in l if e[0] == minX])]
p[1] = [minX, max([e[1] for e in l if e[0] == minX])]

p[2] = [min([e[0] for e in l if e[1] == minY]), minY]
p[3] = [max([e[0] for e in l if e[1] == minY]), minY]

p[4] = [maxX, min([e[1] for e in l if e[0] == maxX])]
p[5] = [maxX, max([e[1] for e in l if e[0] == maxX])]

p[6] = [min([e[0] for e in l if e[1] == maxY]), maxY]
p[7] = [max([e[0] for e in l if e[1] == maxY]), maxY]

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
dist = [None] * N
for i in range(N):
    dist[i] = abs(xy[i][0] - xy[0][0]) + abs(xy[i][1] - xy[0][1])

for j in range(50):
    s = dist.index(max(dist))
    for i in range(N):
        dist[i] = abs(xy[i][0] - xy[s][0]) + abs(xy[i][1] - xy[s][1])
print(max(dist))

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = [0]*n
for i in range(n):
    a,b = map(int,input().split())
    ans[i] = a+b

print(abs(max(ans)-min(ans)))

Submission status: Wrong Answer

Solution code:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

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

p, q, r, s = [0,0,1000000000,1000000000]
for x in l:
    p = max(p, x[0] + x[1])
    q = max(q, x[0] - x[1])
    r = min(r, x[0] + x[1])
    s = min(s, x[0] - x[1])

print(max(abs(p-r), abs(q-s)))

Submission status: Wrong Answer

Solution code:
X = []
Y = []
maxX = 0
minX = 10**9
maxY = 0
minY = 10**9

N = int(input())
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  maxX, minX = max(maxX, x), min(minX, x)
  maxY, minY = max(maxY, y), min(minY, y)
maxXmaxY = 0
maxXminY = 10**9
minXmaxY = 0
minXminY = 10**9
maxYmaxX = 0
maxYminX = 10**9
minYmaxX = 0
minYminX = 10**9
for i in range(N):
  if X[i]==maxX:
    maxXmaxY = max(maxXmaxY, Y[i])
    maxXminY = min(maxXminY, Y[i])
  if X[i]==minX:
    minXmaxY = max(minXmaxY, Y[i])
    minXminY = min(minXminY, Y[i])
  if Y[i]==maxY:
    maxYmaxX = max(maxYmaxX, X[i])
    maxYminX = min(maxYminX, X[i])
  if Y[i]==minY:
    minYmaxX = max(minYmaxX, X[i])
    minYminX = min(minYminX, X[i])
ans1 = max(maxX + maxXmaxY, maxY + maxYmaxX) - min(minX + minXminY, minY + minYminX)
ans2 = max(maxX - maxXminY, minYmaxX - minY) + max(minXmaxY - minX, maxY - maxYminX)
print(max(ans1, ans2))

Submission status: Wrong Answer

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

ansx=sorted(ansx)
ansy=sorted(ansy)
ans=0
for i in range(n-1):
    ans=max(ans,ansx[i+1][0]-ansx[0][0]+abs(ansx[0][1]-ansx[i+1][1]))
for i in range(n-1):
    ans=max(ans,ansy[i+1][0]-ansy[0][0]+abs(ansy[0][1]-ansy[i+1][1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
mx = - float("inf")
nums=[]

for _ in range(N):
  nums.append(list(map(int,input().split())))
mixmiy=nums[0]
maxmiy=nums[0]
mixmay=nums[0]
maxmay=nums[0]
for i in nums[1:]:
  if mixmiy[0] > i[0] or mixmiy[1] > i[1]:
    mixmiy = i if (abs(mixmiy[0])+abs(mixmiy[1])) < (abs(i[0])+abs(i[1])) else mixmiy
  if maxmiy[0] < i[0] or maxmiy[1] > i[1]:
    maxmiy = i if (abs(maxmiy[0])+abs(maxmiy[1])) < (abs(i[0])+abs(i[1])) else maxmiy
  if mixmay[0] > i[0] or mixmay[1] < i[1]:
    mixmay = i if (abs(mixmay[0])+abs(mixmay[1])) < (abs(i[0])+abs(i[1])) else mixmay
  if maxmay[0] < i[0] or maxmay[1] < i[1]:
    maxmay = i if (abs(maxmay[0])+abs(maxmay[1])) < (abs(i[0])+abs(i[1])) else maxmay

mx = max(
  abs(maxmay[0]-mixmiy[0])+abs(maxmay[1]-mixmiy[1]),
  abs(maxmiy[0]-mixmay[0])+abs(maxmiy[1]-mixmay[1]))
print(mx)

Submission status: Wrong Answer

Solution code:
N=int(input())

P=[tuple(map(int,input().split())) for _ in [0]*N]
goodP=P[0]
res=-1

while 1:
    r=-1
    for x,y in P:
        nr=abs(x-goodP[0])+abs(y-goodP[1])
        if nr>r:
            r=nr
            ngoodP=(x,y)
    goodP=ngoodP
    if r==res:
        break
    else:
        res=r
print(res)

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])
x1,y1=xy[0]
xn,yn=xy[-1]
ans=abs(x1-xn)+abs(y1-yn)
xy=sorted(xy,key=lambda x:x[1])
x1,y1=xy[0]
xn,yn=xy[-1]
ans2=abs(x1-xn)+abs(y1-yn)
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
t=int(input())
z=[]
for i in range(t):
      a,b=map(int,input().split())
      z.append([a,b])
i=0
j=i+1
k=[0]
while(i<len(z) and j<len(z)):
      p=(z[i])[0]
      q=(z[j])[0]
      r=(z[i])[1]
      s=(z[j])[1]
      k.append(abs(q-p)+abs(s-r))
      i=i+1
      j=j+1
print(max(k))

Submission status: Wrong Answer

Solution code:

from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

Y=[]
Z=[]
N=int(input())
INF=10**12
init(N,Y,-INF,lambda x,y:max(x,y))
init(N,Z,INF,lambda x,y:min(x,y))
X=[list(map(int,input().split())) for i in range(N)]
P=0
for i in range(N):
  if i:
    P=max(P,X[i][0]+X[i][1]-Y[0],X[i][0]-X[i][1]-Z[0])
  upd(Y,i,X[i][0]+X[i][1])
  upd(Z,i,X[i][0]-X[i][1])
print(P)

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[:750] + X[-750:] + Y[:750] + Y[-750:]
    for a, b in combinations(A, 2):
        ans = max(ans, dist(a, b))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

ans = 0
for i in range(5):
  x1,y1 = cand[i]
  for j in range(6):
    x2,y2 = cand[j]
    ans = max(ans, abs(x1-x2)+abs(y1-y2))
print(ans)

Submission status: Wrong Answer

Solution code:
def man_dist(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

# print('input >>')
N = int(input())
xys = []
for _ in range(N):
    xys.append(tuple(map(int,(input().split()))))

xys_x = sorted(xys, key=lambda xy: xy[0])
xys_y = sorted(xys, key=lambda xy: xy[1])

cand = []

cand.append(man_dist(xys_x[0], xys_x[-1]))
cand.append(man_dist(xys_x[0], xys_y[0]))
cand.append(man_dist(xys_x[0], xys_y[-1]))
cand.append(man_dist(xys_x[-1], xys_y[0]))
cand.append(man_dist(xys_x[-1], xys_y[-1]))
cand.append(man_dist(xys_y[0], xys_y[-1]))

# print('-----output-----')
print(max(cand))

Submission status: Wrong Answer

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
mx = 0
mn = 10**9+5
mxx = [0,0]
mnx = [10**9+5,10**9+5]
mxy = [0,0]
mny = [10**9+5,10**9+5]
for i in range(n):
    x,y = inm()
    if mxx[0] <= x:
        mxx[0] = x
        mxx[1] = y
    if mxy[1] <= y:
        mxy[0] = x
        mxy[1] = y
    if mnx[0] >= x:
        mnx[0] = x
        mnx[1] = y
    if mny[1] >= y:
        mny[0] = x
        mny[1] = y
    mx = max(mx,x+y)
    mn = min(mn,x+y)

ans = mx-mn
for x1,y1 in [mxx,mnx,mxy,mny]:
    for x2,y2 in [mxx,mnx,mxy,mny]:
        ans = max(ans,abs(x1-x2)+abs(y1-y2))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    X = []
    a = 0 # x + y の最大
    b = float('inf') # x + y の最小
    c = float('inf') # x - y の最小
    d = 0 # x - y の最大

    for _ in range(N):
        x, y = map(int, input().split())
        a = max(a, x + y)
        b = min(b, x + y)
        c = min(c, x - y)
        d = max(d, x - y)

    ans = a - b
    ans = max(ans, -c+d)
    ans = max(ans, d-c)
    ans = max(ans, -a+b)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

edge=[0]*8
tate = 0
yoko = 0
summ = 10**10
sumn = 0

for i in range(n):
    x = ab[i][0]
    y = ab[i][1]
    if x+y <= summ :
        edge[0] = x
        edge[1] = y
        summ = x+y
    if x+y >= sumn :
        edge[2] = x
        edge[3] = y
        sumn = x+y
    if x-y <= tate:
        edge[4] =x
        edge[5] =y
        tate = x-y
    if y-x <= yoko:
        edge[6] =x
        edge[7] =y
        yoko = y-x

a = abs(edge[0]-edge[2]) +abs(edge[1]-edge[3])
b = abs(edge[0]-edge[4]) +abs(edge[1]-edge[5])
c = abs(edge[0]-edge[6]) +abs(edge[1]-edge[7])
d = abs(edge[2]-edge[4]) +abs(edge[3]-edge[5])
e = abs(edge[2]-edge[6]) +abs(edge[3]-edge[7])
f = abs(edge[4]-edge[6]) +abs(edge[5]-edge[7])

print(max(a,b,c,d,e,f))

Submission status: Wrong Answer

Solution code:
N=int(input())
migisita=[0,10^9]
migiue=[0,0]
hidarisita=[10^9,10^9]
hidariue=[10^9,0]
for i in range(0,N):
    a,b=list(map(int,input().split()))
    if migiue[0]<a and migiue[1]<b:
        migiue=[a,b]
    if migisita[0]<a and migisita[1]>b:
        migisita=[a,b]
    if hidariue[0]>a and hidariue[1]<b:
        hidariue=[a,b]
    if hidarisita[0]>a and hidarisita[1]>b:
        hidarisita=[a,b]

one=abs(migiue[0]-hidarisita[0])+abs(migiue[1]-hidarisita[1])
two=abs(hidariue[0]-migisita[0])+abs(hidariue[1]-hidarisita[1])
print(max(one,two))

Submission status: Wrong Answer

Solution code:
import math
import collections
import itertools

def resolve():
    N=int(input())
    X=[0]*N
    Y=[0]*N
    Max=0
    Min=10**10
    for i in range(N):
        X[i],Y[i]=map(int,input().split())
        Max=max(Max,X[i]+Y[i])
        Min=min(Min,X[i]+Y[i])
    
    print(Max-Min)


resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
# n = 2*10**5

min_x = float('inf')
max_x = -float('inf')
min_y = float('inf')
max_y = -float('inf')

min_x_pos = []
max_x_pos = []
min_y_pos = []
max_y_pos = []

for i in range(n):
    x, y = map(int, input().split())
    # x, y = (10**9 , 10**9)
    if x < min_x:
        min_x = x
        min_x_pos = [(x, y)]
    elif x == min_x:
        min_x_pos.append((x, y))

    if y < min_y:
        min_y = y
        min_y_pos = [(x, y)]
    elif y == min_y:
        min_y_pos.append((x, y))

    if x > max_x:
        max_x = x
        max_x_pos = [(x, y)]
    elif x == max_x:
        max_x_pos.append((x, y))
    if y > max_y:
        max_y = y
        max_y_pos = [(x, y)]
    elif y == max_y:
        max_y_pos.append((x, y))


def calc_dist(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])


min_x_of_max_y = max(min_x_pos, key=lambda pos: pos[1])
min_x_of_min_y = min(min_x_pos, key=lambda pos: pos[1])

min_y_of_max_x = max(min_y_pos, key=lambda pos: pos[0])
min_y_of_min_x = min(min_y_pos, key=lambda pos: pos[0])

max_x_of_max_y = max(max_x_pos, key=lambda pos: pos[1])
max_x_of_min_y = min(max_x_pos, key=lambda pos: pos[1])

max_y_of_max_x = max(max_y_pos, key=lambda pos: pos[0])
max_y_of_min_x = min(max_y_pos, key=lambda pos: pos[0])

candidate_pos = [min_x_of_max_y, min_y_of_max_x,
                 min_y_of_min_x, min_y_of_max_x,
                 max_x_of_min_y, max_x_of_max_y,
                 max_y_of_min_x, max_y_of_max_x]

answer = 0
for i in range(len(candidate_pos)):
    for j in range(len(candidate_pos)):
        dis = calc_dist(candidate_pos[i], candidate_pos[j])
        answer = max(answer, dis)

print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p.sort()
x1, y1 = p[0]
x2, y2 = p[1]
if x1 <= x2 and y1 <= y2:
    print(abs((x1 + y1) - (x2 + y2)))
elif x1 <= x2 and y1 >= y2:
    print(abs((x1 - y1) - (x2 + y2)))
elif x1 >= x2 and y1 >= y2:
    print(abs((x1 + y1) - (x2 + y2)))
elif x1 >= x2 and y1 <= y2:
    print(abs((x1 - y1) - (x2 + y2)))

Submission status: Wrong Answer

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


def solve(N: int, x: "List[int]", y: "List[int]"):
    s = [0] * N
    for i in range(N):
        s[i] = x[i] + y[i]
    big = max(s)
    small = min(s)
    maxIndex = s.index(big)
    minIndex = s.index(small)
    print(abs(x[maxIndex] - x[minIndex])+  abs(y[maxIndex] - y[minIndex]))




    return


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

Solution code:
#E
N=int(input())
x=[0]*N
y=[0]*N
z=[0]*N

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

z.sort(key=lambda x:x[0])
a= sorted(z,key=lambda x:x[1])[0]
b= sorted(z,key=lambda x:x[1],reverse=True)[0]

z.sort(key=lambda x:x[0],reverse=True)
c= sorted(z,key=lambda x:x[1])[0]
d= sorted(z,key=lambda x:x[1],reverse=True)[0]

z.sort(key=lambda x:x[1])
e= sorted(z,key=lambda x:x[0])[0]
f= sorted(z,key=lambda x:x[0],reverse=True)[0]

z.sort(key=lambda x:x[1],reverse=True)
g= sorted(z,key=lambda x:x[0])[0]
h = sorted(z,key=lambda x:x[0],reverse=True)[0]

al = [a,b,c,d,e,f,g,h]
ans=0

#print(al)

for i in range(8):
    for j in range(i,8):
        #print(i,j)
        tmp = abs(al[i][0]-al[j][0]) + abs(al[i][1]-al[j][1])
        ans = max(ans,tmp)
        
print(ans)

Submission status: Wrong Answer

Solution code:
X = []
Y = []
maxX = 0
minX = 10**9
maxY = 0
minY = 10**9

N = int(input())
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  maxX, minX = max(maxX, x), min(minX, x)
  maxY, minY = max(maxY, y), min(minY, y)
maxXmaxY = 0
maxXminY = 10**9
minXmaxY = 0
minXminY = 10**9
maxYmaxX = 0
maxYminX = 10**9
minYmaxX = 0
minYminX = 10**9
for i in range(N):
  if X[i]==maxX:
    maxXmaxY = max(maxXmaxY, Y[i])
    maxXminY = min(maxXminY, Y[i])
  if X[i]==minX:
    minXmaxY = max(minXmaxY, Y[i])
    minXminY = min(minXminY, Y[i])
  if Y[i]==maxY:
    maxYmaxX = max(maxYmaxX, X[i])
    maxYminX = min(maxYminX, X[i])
  if Y[i]==minX:
    minYmaxX = max(minYmaxX, X[i])
    minYminX = min(minYminX, X[i])
ans1 = max(maxX + maxXmaxY, maxY + maxYmaxX) - min(minX + minXminY, minY + minYminX)
ans2 = max(maxX - maxXminY, minYmaxX - minY) + max(minXmaxY - minX, maxY - maxYminX)
print(max(ans1, ans2))

Submission status: Wrong Answer

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

def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())
    ru = None
    rd = None
    lu = None
    ld = None

    for i in range(n):
        row = [int(x) for x in input().rstrip().split(" ")]
        if i == 0:
            ru = row
            rd = row
            lu = row
            ld = row
            continue

        if ru[0] + ru[1] < row[0] + row[1]:
            ru = row
        if rd[0] - rd[1] < row[0] - row[1]:
            rd = row
        if -lu[0] + lu[1] < -row[0] + row[1]:
            lu = row
        if -ld[0] - ld[1] < -row[0] - row[1]:
            ld = row

    ans = 0
    points = [ru, rd, lu, ld]
    for i in range(4):
        for j in range(i+1, 4):
            tmp = dist(points[i], points[j])
            if ans < tmp:
                ans = tmp

    print(ans)

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 i in range(1,N-1):
    nowxy=xy[i]
    if (Manhattan([nowxy,nowans[1]])>nowManhattan):
        nowans=[nowxy,nowans[1]]
        nowManhattan=Manhattan(nowans)
    elif (Manhattan([nowans[0],nowxy])>nowManhattan):
        nowans=[nowans[0],nowxy]
        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))

print(mdct)

Submission status: Wrong Answer

Solution code:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

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

p, q, r, s = [0,0,1000000000,1000000000]
for x in l:
    p = max(p, x[0] + x[1])
    q = max(q, x[0] - x[1])
    r = min(r, x[0] + x[1])
    s = min(s, x[0] - x[1])

print(p,q,r,s)
print(max(abs(p-r), abs(q-s)))

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(3, 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:
import random
N = int(input())
lismoto = "0"*N*2
lis = list(lismoto)
for i in range(0,len(lis),2):
    lis[i],lis[i+1] = map(int,input().split())

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

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

print(ma)

Submission status: 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)]
z = []
for i in range(0,len(x)):
  z.append(x[i]+y[i])
max = max(z)
min = min(z)
print(max-min)

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

result = [0]
for i in range(n - 1):
  for j in range(n - 1):
    if i != j:
      result.append(abs(x[i] - x[j]) + abs(y[i] - y[j]))

print(max(result))

Submission status: Wrong Answer

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

N = int(input())

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

# 右上 - 左下
[x, y] = XY[0]
max_xy = y - x
max_pos = (x, y)
min_xy = y - x
min_pos = (x, y)
for [x, y] in XY[1:]:
    x_plus_y = x + y
    if x_plus_y > max_xy:
        max_xy = x_plus_y
        max_pos = (x, y)
    if x_plus_y < min_xy:
        min_xy = x_plus_y
        min_pos = (x, y)

# 右上と左下の点のマンハッタン距離を求める
(max_x, max_y) = max_pos
(min_x, min_y) = min_pos
right_up_left_down_man = abs(max_x - min_x) + abs(max_y - min_y)

# 左上 - 右下
[x, y] = XY[0]
max_xy = y - x
max_pos = (x, y)
min_xy = y - x
min_pos = (x, y)
for [x, y] in XY[1:]:
    y_minus_x = y - x
    if y_minus_x > max_xy:
        max_xy = y_minus_x
        max_pos = (x, y)
    if y_minus_x < min_xy:
        min_xy = y_minus_x
        min_pos = (x, y)

# 左上と右下の点のマンハッタン距離を求める
(max_x, max_y) = max_pos
(min_x, min_y) = min_pos
left_up_right_down_man = abs(max_x - min_x) + abs(max_y - min_y)

# 2つのマンハッタン距離の大きいほうを採用
man = max(right_up_left_down_man, left_up_right_down_man)

print(man)

Submission status: Wrong Answer

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

edge=[0]*8
tate = 0
yoko = 0
summ = 10**10
sumn = 0

for i in range(n):
    x = ab[i][0]
    y = ab[i][1]
    if x+y <= summ :
        edge[0] = x
        edge[1] = y
        summ = x+y
    if x+y >= sumn :
        edge[2] = x
        edge[3] = y
        sumn = x+y
    if x-y <= tate:
        edge[4] =x
        edge[5] =y
        tate = x-y
    if y-x <= yoko:
        edge[6] =x
        edge[7] =y
        yoko = y-x

a = abs(edge[0]-edge[2]) +abs(edge[1]-edge[3])
b = abs(edge[0]-edge[4]) +abs(edge[1]-edge[5])
c = abs(edge[0]-edge[6]) +abs(edge[1]-edge[7])
d = abs(edge[2]-edge[4]) +abs(edge[3]-edge[5])
e = abs(edge[2]-edge[6]) +abs(edge[5]-edge[7])
f = abs(edge[4]-edge[6]) +abs(edge[5]-edge[7])

print(max(a,b,c,d,e,f))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0]*n
y = [0]*n
max = 0
s = []
for i in range(n):
	x[i],y[i] = map(int,input().split())
for j in range(n):
	if max <= abs(x[0] - x[j]) + abs(y[0] - y[j]):
		max = abs(x[0] - x[j]) + abs(y[0] - y[j])
		s.append(j)
	if max < abs(x[0] - x[j]) + abs(y[0] - y[j]):
		s = []
		s.append(j)
for p in s:
	for k in range(n):
		if max < abs(x[p] - x[k]) + abs(y[p] - y[k]):
			max = abs(x[p] - x[k]) + abs(y[p] - y[k])
print(max)

Submission status: Wrong Answer

Solution code:
(n,),*e=[[*map(int,i.split())]for i in open(0)]
a=sorted(e)
b=sorted(e,key=lambda x: x[1])
c=a[:10]+a[:10]+b[10:]+b[:10]
ans=0
for i,j in c:
    for ii,jj in c:
        ans=max(ans,abs(i-ii)+abs(j-jj))

Submission status: Wrong Answer

Solution code:

from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

Y=[]
Z=[]
N=int(input())
INF=10**12
init(N,Y,-INF,lambda x,y:max(x,y))
init(N,Z,INF,lambda x,y:min(x,y))
X=[list(map(int,input().split())) for i in range(N)]
P=0
for i in range(N):
  if i:
    P=max(P,X[i][0]-X[i][1]-Y[0],X[i][0]+X[i][1]-Z[0])
  upd(Y,i,X[i][0]-X[i][1])
  upd(Z,i,X[i][0]+X[i][1])
print(P)

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
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))
            
print(max(abs(ans1+ans3), abs(ans2+ans4)))