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())
x = [None]*n
y = [None]*n

for i in range(n):
    x[i],y[i] = map(int,input().split())
    
d_from0 = 0
p_far = 0
x_0 = x[0]
y_0 = y[0]

for i in range(n):
    d = abs(x[i]-x_0)+abs(y[i]-y_0)
    if d > d_from0:
        d_from0 = d
        p_far = i

x_p = x[p_far]
y_p = y[p_far]

ans = 0
q = 0
for i in range(n):
    d = abs(x[i]-x_p)+abs(y[i]-y_p)
    if d > ans:
        ans = d
        q = i
        
x_q = x[q]
y_q = y[q]

ans = 0

for i in range(n):
    d = abs(x[i]-x_q)+abs(y[i]-y_q)
    if d > ans:
        ans = d
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
min = 10000000000
max = -10000000000
l = []
r = []
ln = 0
rn = 0
for _ in range(n):
    x, y = map(int,input().split())
    if x+y <= min:
        if x+y == min:
            l.append([x,y])
            ln += 1
        else:
            l.append([x,y])
            ln = 1
        min = x+y
    elif x+y >= max:
        if x + y == max:
            r.append([x, y])
            rn += 1
        else:
            r.append([x, y])
            rn = 1
        max = x+y
res = 0
for i in range(1, ln+1):
    for j in range(1, rn+1):
        dis = abs(l[-i][0]-r[-j][0]) + abs(r[-j][1]-l[-i][1])
        if dis>res:
            res = dis
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

min_x = 10**9
max_x = 1
min_y = 10**9
max_y = 1

for x,y in XY:
    min_x = min(x, min_x)
    max_x = max(x, max_x)
    min_y = min(y, min_y)
    max_y = max(y, max_y)

cand_set = set()
for x,y in XY:
    if x in (min_x, max_x) or y in (min_y, max_y):
        cand_set.add((x, y))

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

Submission status: Wrong Answer

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

z = [0]*n
d = [0]*n
for i,[x,y] in enumerate(x) :
    z[i] = [x-y,x+y]
    d[i] = max(x-y,x+y)
print(max(d)-min(d))

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 = []
for i in range(n - 1):
  for j in range(n - 1):
    result.append(abs(x[i] - x[j]) + abs(y[i] - y[j]))

print(max(result))

Submission status: Wrong Answer

Solution code:
def ii(): return int(input())


def mi(): return map(int, input().split())


def li(): return list(map(int, input().split()))


n = ii()

ps = []

xmin = (1e9, 0)
xmax = (-1e9, 0)
ymin = (0, 1e9)
ymax = (0, -1e9)

for _ in range(n):
    x, y = mi()
    ps.append((x, y))

    if xmin[0] > x:
        xmin = (x, y)
    if xmax[0] < x:
        xmax = (x, y)
    if ymin[1] > y:
        ymin = (x, y)
    if ymax[1] < y:
        ymax = (x, y)


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


ans = 0

for p in [xmin, xmax, ymin, ymax]:
    for q in ps:
        ans = max(ans, d(p, q))

print(ans)

Submission status: Wrong Answer

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

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

for p in P:
    for q in peri:
        ans = max(ans, dist(p, q))
print(ans)

Submission status: Wrong Answer

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

n = int(input())
a = [list(map(int,input().split())) for i in range(n)]

ax = sorted(a, key=lambda x:(x[0], x[1]))
ay = sorted(a, key=lambda x:(x[1], x[0]))

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

Submission status: Wrong Answer

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

xmax = x.index(max(x))
xmin = x.index((min(x)))
ans1 = abs(max(x)-min(x))+abs(y[xmax] - y[xmin])

ymax = y.index(max(y))
ymin = y.index(min(y))
ans2 = abs(max(y)-min(y)) + abs(x[ymax]-x[ymin])
print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
N=int(input())
points=[list(map(int,input().split())) for _ in range(N)]


chebmax0=-float("inf")
chebmin0=float("inf")
chebmax1=-float("inf")
chebmin1=float("inf")

#chebmax0→x-yのmax
for l in points:
    chebmax0=max(chebmax0,l[0]-l[1])
for l in points:
    chebmin0=min(chebmax0,l[0]-l[1])
for l in points:
    chebmax1=max(chebmax1,l[0]+l[1])
for l in points:
    chebmin1=min(chebmin1,l[0]+l[1])
#print(chebmin1,chebmax1,chebmin0,chebmax0)
print(max(chebmax0-chebmin0,chebmax1-chebmin1))

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().strip())
maxv = (0,0)
mixv = (float("inf"),0)
mayv = (0,0)
miyv = (0,float("inf"))
for _ in range(N):
    x,y = map(int,stdin.readline().strip().split())
    if x < mixv[0]:
        mixv = (x,y)
    elif x > maxv[0]:
        maxv = (x,y)
    if y < miyv[1]:
        miyv = (x,y)
    elif y > mayv[1]:
        mayv = (x,y)
results = [maxv,mixv,mayv,miyv]
g_max = 0
for i in range(4):
    for j in range(i+1,4):
        x_diff = abs(results[i][0] - results[j][0])
        y_diff = abs(results[i][1]-results[j][1])
        g_max = max(g_max,x_diff+y_diff)
print(g_max)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

upper = []
lower = []
for _ in range(N):
    x, y = mapint()
    if x<=y:
        upper.append((x, y))
    else:
        lower.append((x, y))
upper.sort(key=lambda x:x[0]+x[1])
lower.sort(key=lambda x:x[0]+x[1])

if len(upper):
    upper_max = abs(upper[0][0]-upper[-1][0]) + abs(upper[0][1]-upper[-1][1])
else:
    upper_max = 0

if len(lower):
    lower_max = abs(lower[0][0]-lower[-1][0]) + abs(lower[0][1]-lower[-1][1])
else:
    lower_max = 0

if len(upper) and len(lower):
    upper.sort(key=lambda x:abs(x[0]-x[1]), reverse=True)
    lower.sort(key=lambda x:abs(x[0]-x[1]), reverse=True)
    upper_lower = abs(upper[0][0]-lower[0][0]) + abs(upper[0][1]-lower[0][1])
else:
    upper_lower = 0

print(max(upper_max, lower_max, upper_lower))

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

x_max, x_min, y_max, y_min = x[ 0 ], x[ 0 ], y[ 0 ], y[ 0 ]
for i in range( n ):
    if x[ i ] > x_max:
        x_max = x[ i ]
    if x[ i ] < x_min:
        x_min = x[ i ]
    if y[ i ] > y_max:
        y_max = y[ i ]
    if y[ i ] < y_min:
        y_min = y[ i ]
    
# print( x_max, x_min, y_max, y_min )

right, top, left, bottom = [], [], [], []
for i in range( n ):
    if x[ i ] == x_max:
        right.append( y[ i ] )
    if y[ i ] == y_max:
        top.append( x[ i ] )
    if x[ i ] == x_min:
        left.append( y[ i ] )
    if y[ i ] == y_min:
        bottom.append( x[ i ] )

ver = [ ( 0, 0 ) for _ in range( 8 ) ]

ver[ 0 ] = ( x_max, max( right ) )
ver[ 1 ] = ( max( top ), y_max )
ver[ 2 ] = ( min( top ), y_max )
ver[ 3 ] = ( x_min, max( left ) )
ver[ 4 ] = ( x_min, min( left ) )
ver[ 5 ] = ( y_min, min( bottom ) )
ver[ 6 ] = ( y_min, max( bottom ) )
ver[ 7 ] = ( x_max, min( right ) )

max_length = 0
for i in range( 8 ):
    for j in range( 8 ):
        length = abs( ver[ i ][ 0 ] - ver[ j ][ 0 ] ) + abs( ver[ i ][ 1 ] - ver[ j ][ 1 ] )
        if length > max_length:
            max_length = length
            # print( ver[ i ], ver[ j ], length )

# print( ver )
print( max_length )

Submission status: Wrong Answer

Solution code:
N=int(input())

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

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

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

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][1]-X[i][0])
  upd(Z,i,X[i][1]+X[i][0])
print(P)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0 for _ in range(n)]
for i in range(n):
    x[i] = list(map(int, input().split()))
xx = sum([i[0] for i in x])/n
yy = sum([i[1] for i in x])/n
for i in x:
    i.append(abs(xx-i[0]) + abs(yy-i[1]))
x.sort(key = lambda s:s[2])
ans = 0
for i in range(1, min(5, n)):
    for j in range(n):
        ans = max(ans, abs(x[-i][0] - x[j][0]) + abs(x[-i][1] - x[j][1]))
print(ans)

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:
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ma = 0
mi = float('inf')
for x,y in xy:
  ma = max(ma,x-y)
  mi = min(mi,x-y)
ans = ma - mi


for x,y in xy:
  ma = max(ma,x+y)
  mi = min(mi,x+y)
  
ans = max(ans, ma - mi)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	E
# CreatedDate:  2020-09-13 21:46:52 +0900
# LastModified: 2020-09-13 22:06:00 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def f(x, y, ver):
    if ver == 0:
        return max(x, y)-min(x, y)
    else:
        return x + y


def main():
    N = int(input())
    ch_0 = []
    ch_1 = []
    trans_max = -1
    for _ in range(N):
        x, y = map(int, input().split())
        ch_0.append(f(x, y, 0))
        ch_1.append(f(x, y, 1))
    if max(ch_0)-min(ch_0) < max(ch_1)-min(ch_1):
        print(max(ch_1)-min(ch_1))
    else:
        print(max(ch_0)-min(ch_0))




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

result = abs(min(xsum)-max(xsum))
print(result)

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[0], xys_y[-1]))
cand.append(man_dist(xys_y[0], xys_y[-1]))

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

Submission status: Wrong Answer

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
N=int(input())
points=[list(map(int,input().split())) for _ in range(N)]


chebmax0=-float("inf")
chebmin0=float("inf")
chebmax1=-float("inf")
chebmin1=float("inf")

#chebmax0→x-yのmax
for l in points:
    chebmax0=max(chebmax0,l[0]-l[1])
for l in points:
    chebmin0=min(chebmax0,l[0]-l[1])
for l in points:
    chebmax1=max(chebmax1,l[0]+l[1])
for l in points:
    chebmin1=min(chebmax1,l[0]+l[1])
#print(chebmin1,chebmax1,chebmin0,chebmax0)
print(max(chebmax0-chebmin0,chebmax1-chebmin1))

Submission status: Wrong Answer

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


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


p_a = xys[0]
p_b = xys[1]
for p_c in xys[2:]:
    d_a_b = m(p_a, p_b)
    d_a_c = m(p_a, p_c)
    d_b_c = m(p_b, p_c)

    if d_a_b > max(d_a_c, d_b_c):
        pass
    else:
        if d_a_c > d_b_c:
            p_b = p_c
        else:
            p_a = p_c
print(m(p_a, p_b))

Submission status: Wrong Answer

Solution code:
N = int(input())

x = [list(map(int, input().split())) for i in range(N)]
ma = x[0][0] * x[0][1] / 2
mai = 0
mii = 0
mi = x[0][0] * x[0][1] / 2
for i in range(1,N):
    a = x[i][0] * x[i][1] / 2
    if ma < a:
        ma = a
        mai = i
    elif mi > a:
        mi = a
        mii = i
print(abs(x[mii][0]-x[mai][0])+abs(x[mii][1]-x[mai][1]))

Submission status: Wrong Answer

Solution code:
import sys
import random

random.seed(1)

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
pairs = [map(int, input().split(" ")) for i in range(n)]

for i, (x, y) in enumerate(pairs):
    xy = x+y
    if i == 0:
        min_x = max_x = x
        min_y = max_y = y
        min_xi = [0]
        max_xi = [0]
        min_yi = [0]
        max_yi = [0]

        min_xyi = [0]
        max_xyi = [0]
        min_xy = max_xy = xy 
    else:
        if x < min_x:
            min_xi = [i]
            min_x = x
        elif x == min_x:
            min_xi.append(i)

        if y < min_y:
            min_yi = [i]
            min_y = y
        elif y == min_y:
            min_yi.append(i)

        if xy < min_xy:
            min_xyi = [i]
            min_xy = xy
        elif xy == min_xy:
            min_xyi.append(i)

        if x > max_x:
            max_xi = [i]
            max_x = x
        elif x == min_x:
            max_xi.append(i)

        if y > max_y:
            max_yi = [i]
            max_y = y
        elif y == min_y:
            max_yi.append(i)

        if xy > max_xy:
            max_xyi = [i]
            max_xy = xy
        elif xy == min_xy:
            max_xyi.append(i)



max_iter = 100

fmax_dist = -2

final_out = 0

#print("min_xi", min_xi, "min_yi", min_yi, "max_xi", max_xi, "max_yi", max_yi, "min_xyi", min_xyi, "max_xyi", max_xyi)

#randoms = [random.randint(0, n-1) for i in range(10)]
randoms = [0]
first_jibuns = set(min_xi + max_xi + min_yi + max_yi + min_xyi + max_xyi + randoms)

True
for first_jibun in first_jibuns:
    jibun = first_jibun
    #for iter_i in range(max_iter):
    max_dist = -1
    while True:
        jx, jy = pairs[jibun]
        for cur_aite in range(n):
            if jibun == cur_aite:
                continue
            ax, ay = pairs[cur_aite]
            cdist = abs(jx-ax) + abs(jy-ay)
            
            if cdist > max_dist:
                next_jibun = cur_aite
                max_dist = cdist

        if fmax_dist == max_dist:
            out = max_dist
            break
        else:
            jibun = next_jibun 
            fmax_dist = max_dist

    final_out = max(final_out, out)
    
    
print(final_out)

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


for i in range(8):
    for j in range(i+1,8):
        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:
charo={}
for i in range(int(input())):
    x,y=list(map(int,input().split()))
    sum1=x+y
    charo[sum1]=[x,y]
min1=min(charo)
max1=max(charo)
a=charo[min1]
b=charo[max1]
print(abs(a[0]-b[0])+abs(a[1]-b[1]))

Submission status: Wrong Answer

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

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

ans = 0
for i in range(min(n,10**3)):
    for j in range(min(n,10**3)):
        ans = max(ans,abs(xsort[i][0]-xsort[-j][0])+abs(xsort[i][1]-xsort[-j][1]))
        ans = max(ans,abs(ysort[i][0]-ysort[-j][0])+abs(ysort[i][1]-ysort[-j][1]))
print(ans)

Submission status: Wrong Answer

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

print(sum)

Submission status: Wrong Answer

Solution code:
import itertools

n=int(input())

lst=[]
lst2=[]
cnt=[]
cnt2=[]

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

minx=min(cnt)
maxx=max(cnt)
miny=min(cnt2)
maxy=max(cnt2)

lst1,lst2,lst3,lst4=[],[],[],[]

for i in lst:
    if i[0]==minx:
        lst1.append(i)
    
    if i[0]==maxx:
        lst2.append(i)
    
    if i[1]==miny:
        lst3.append(i)
    
    if i[1]==maxy:
        lst4.append(i)


sinlst=lst1+lst2+lst3+lst4
ans=0


for zzz in itertools.combinations(sinlst,2):
    ans=max(ans,abs(zzz[0][0]-zzz[1][0])+abs(zzz[0][1]-zzz[1][1]))


print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N)]
import numpy as np
AB=np.array(AB)
_=AB[np.argsort(AB[:, 0])]
x=[]
x.append(_[0])
i=1
while i<N and _[i][0]==_[0][0]:
  x.append(_[i])
  i+=1
x.append(_[-1])
i=N-2
while i>=0 and _[i][0]==_[-1][0]:
  x.append(_[i])
  i-=1

_=AB[np.argsort(AB[:, 1])]
x.append(_[0])
i=1
while i<N and _[i][1]==_[0][1]:
  x.append(_[i])
  i+=1
x.append(_[-1])
i=N-2
while i>=0 and _[i][1]==_[-1][1]:
  x.append(_[i])
  i-=1
ans=0
for xx in x:
  a=np.linalg.norm(AB-xx,ord=1,axis=1)
  ans=max(max(a),ans)
print(int(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
c = 0
d = 0
y = sorted(x)
z = []
for i in range(n):
    z.append([x[i][1],x[i][0]])
a = sorted(z)
for i in range(n-1):
    c = max(abs(y[i][0]-y[i+1][0])+abs(y[i][1]-y[i+1][1]),c)
    d = max(abs(a[i][0]-a[i+1][0])+abs(a[i][1]-a[i+1][1]),c)
print(max(c,d))

Submission status: Wrong Answer

Solution code:
N = int(input())

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for x, y in P:
    X.append(x)
    Y.append(y)
mx = (min(X) + max(X)) // 2
my = (min(Y) + max(Y)) // 2

Q = []
for x, y in P:
    x, y = x-mx, y-my
    Q.append((x+y, x-y))

ans = 0
for x, y in Q:
    ans = max(ans, abs(x) + abs(y))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int,input().split())))
x0,y0 = xy[0]
x1,y1 = xy[1]
mdis = abs(x0-x1)+abs(y0-y1)
for x,y in xy[2:]:
    d0 = abs(x0-x)+abs(y0-y)
    d1 = abs(x1-x)+abs(y1-y)
    if d0 > d1:
        if d0 > mdis:
            mdis = d0
            x1,y1 = x,y
    else:
        if d1 > mdis:
            mdis = d1
            x0,y0 = x,y
print(mdis)

Submission status: Wrong Answer

Solution code:
import sys
#def input():
    #return sys.stdin.readline()[:-1]
N = int(input())
x=[0]*N
y=[0]*N
for i in range(N):
    xy=list(map(int,input().split()))
    x[i]=xy[0]
    y[i]=xy[1]
d=0
mi=x[0]+y[0]
ma=mi
nmi=0
nma=0
for i in range(N):
    mi=min(mi,x[i]+y[i])
    if mi == x[i]+y[i]:
        nmi=i
    ma=max(ma,x[i]+y[i])
    if ma == x[i]+y[i]:
        nma=i

print(int(abs(x[nmi]-x[nma])+abs(y[nmi]-y[nma])))

Submission status: Wrong Answer

Solution code:
N = int(input())
pts = [[0, 0] for i in range(N)]
x_max = 1
x_min = 10**9
y_max = 1
y_min = 10**9
for i in range(N):
    x, y = list(map(int, input().split()))
    pts[i][0], pts[i][1] = x, y
    x_max = max(x, x_max)
    x_min = min(x, x_min)
    y_max = max(y, y_max)
    y_min = min(y, y_min)
l = [pt for pt in pts if pt[0]==x_min]
r = [pt for pt in pts if pt[0]==x_max]
d = [pt for pt in pts if pt[1]==y_min]
u = [pt for pt in pts if pt[1]==y_max]
l.sort(key=lambda x:x[1])
r.sort(key=lambda x:x[1])
d.sort(key=lambda x:x[0])
u.sort(key=lambda x:x[0])
candidates = []
candidates.append(l[0])
candidates.append(l[-1])
candidates.append(r[0])
candidates.append(r[-1])
candidates.append(d[0])
candidates.append(d[-1])
candidates.append(u[0])
candidates.append(u[-1])
def calc(x, y):
    ans = 0
    ans += abs(x[0] - y[0])
    ans += abs(x[1] - y[1])
    return ans
ans = 0
for pt in pts:
    for can in candidates:
        ans = max(ans, calc(pt, can))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ma = 0
mi = float('inf')
for x,y in xy:
  ma = max(ma,abs(x-y))
  mi = min(mi,abs(x-y))
ans = ma - mi

ma = 0
mi = float('inf')
for x,y in xy:
  ma = max(ma,x+y)
  mi = min(mi,x+y)
  
ans = max(ans, ma - mi)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

upper = []
lower = []
for _ in range(N):
    x, y = mapint()
    if x<=y:
        upper.append((x, y))
    else:
        lower.append((x, y))
upper.sort()
lower.sort()

if len(upper):
    upper_max = abs(upper[0][0]-upper[-1][0]) + abs(upper[0][1]-upper[-1][1])
else:
    upper_max = 0

if len(lower):
    lower_max = abs(lower[0][0]-lower[-1][0]) + abs(lower[0][1]-lower[-1][1])
else:
    lower_max = 0

if len(upper) and len(lower):
    upper.sort(key=lambda x:abs(x[0]-x[1]), reverse=True)
    lower.sort(key=lambda x:abs(x[0]-x[1]), reverse=True)
    upper_lower = abs(upper[0][0]-lower[0][0]) + abs(upper[0][1]-lower[0][1])
else:
    upper_lower = 0

print(max(upper_max, lower_max, upper_lower))

Submission status: Wrong Answer

Solution code:
N = int(input())

x = [list(map(int, input().split())) for i in range(N)]
ma = x[0][0] * x[0][1]
mai = 0
mii = 0
mi = x[0][0] * x[0][1]
for i in range(1,N):
    a = x[i][0] * x[i][1]
    if ma < a:
        ma = a
        mai = i
    elif mi > a:
        mi = a
        mii = i
print(abs(x[mii][0]-x[mai][0])+abs(x[mii][1]-x[mai][1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
s_max,s_min=0,float('inf')
t_max,t_min=0,float('inf')
for i in range(N):
    a,b=map(int,input().split())
    
    s,t=a+b,a-b
    s_max,s_min=max(s_max,s),min(s_min,s)
    t_max,t_min=max(t_max,t),min(t_min,t)
    
print(max(s_max-s_min,t_max-t_min))

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)
x = sorted(a, key = lambda k: k[0])
y = sorted(a,key = lambda k: k[1])
things = [x[0], x[-1], y[0], y[-1]]
best = 0
for i in range(4):
    for j in range(i+1, 4):
        best = max(best, abs(things[i][0]- things[j][0]) + abs(things[i][1]- things[j][1]))
print(best)

Submission status: Wrong Answer

Solution code:
n = int(input())
min = 10000000000
max = -10000000000
l = []
r = []
ln = 0
rn = 0
for _ in range(n):
    x, y = map(int,input().split())
    if x+y <= min:
        if x+y == min:
            l.append([x,y])
            ln += 1
        else:
            l.append([x,y])
            ln = 1
        min = x+y
    elif x+y >= max:
        if x + y == max:
            r.append([x,y])
            rn += 1
        else:
            r.append([x,y])
            rn = 1
        max = x+y
res = 0
for i in range(ln):
    for j in range(rn):
        dis = abs(l[i][0]-r[j][0]) + abs(r[j][1]-l[i][1])
        if dis>res:
            res = dis
print(res)