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:
X = []
Y = []
maxX = 0
minX = 10**9
maxY = 0
minY = 10**9

minxy =  float("inf")
maxxy =  -float("inf")
minnxy = float("inf")
maxnxy = -float("inf")
N = int(input())
for i in range(N):
  x, y = map(int, input().split())
  minxy = min(minxy, y-x)
  maxxy = min(maxxy, y-x)
  minnxy = min(minnxy, x + y)
  maxnxy = max(maxnxy, x + y)
  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])
ans = maxX - minX  + max(abs(maxXmaxY-minXminY),abs(maxXminY-minXmaxY))
ans = max(ans, maxY - minY  + max(abs(maxYmaxX-minYminX),abs(maxYminX-minYmaxX)))
ans = max(ans, maxYmaxX - minX + maxY - minXminY)
ans = max(ans, maxX - maxYminX + maxY - minXminY)
ans = max(ans, minYmaxX - minX + minXmaxY - minY)
ans = max(ans, maxX - minYminX + maxXmaxY - minY)
ans = max(ans, maxxy-minxy, maxnxy-minnxy)
print(ans)

Submission status: Wrong Answer

Solution code:
# A divide and conquer program in Python3
# to find the smallest distance from a
# given set of points.
import math

# A class to represent a Point in 2D plane
class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

# A utility function to find the
# distance between two points
def dist(p1, p2):
    return abs(p1.x - p2.x) + abs(p1.y - p2.y)

# A Brute Force method to return the
# smallest distance between two points
# in P[] of size n
def bruteForce(P, n):
    min_val = 0
    for i in range(n):
        for j in range(i + 1, n):
            if dist(P[i], P[j]) > min_val:
                min_val = dist(P[i], P[j])

    return min_val

# A utility function to find the
# distance beween the closest points of
# strip of given size. All points in
# strip[] are sorted accordint to
# y coordinate. They all have an upper
# bound on minimum distance as d.
# Note that this method seems to be
# a O(n^2) method, but it's a O(n)
# method as the inner loop runs at most 6 times
def stripClosest(strip, size, d):

    # Initialize the minimum distance as d
    min_val = d

    strip.sort(key = lambda point: point.y)

    # Pick all points one by one and
    # try the next points till the difference
    # between y coordinates is smaller than d.
    # This is a proven fact that this loop
    # runs at most 6 times
    for i in range(size):
        j = i + 1
        while j < size and (strip[j].y - strip[i].y) > min_val:
            min_val = dist(strip[i], strip[j])
            j += 1

    return min_val

# A recursive function to find the
# smallest distance. The array P contains
# all points sorted according to x coordinate
def closestUtil(P, n):

    # If there are 2 or 3 points,
    # then use brute force
    if n <= 3:
        return bruteForce(P, n)

    # Find the middle point
    mid = n // 2
    midPoint = P[mid]

    # Consider the vertical line passing
    # through the middle point calculate
    # the smallest distance dl on left
    # of middle point and dr on right side
    dl = closestUtil(P[:mid], mid)
    dr = closestUtil(P[mid:], n - mid)

    # Find the smaller of two distances
    d = min(dl, dr)

    # Build an array strip[] that contains
    # points close (closer than d)
    # to the line passing through the middle point
    strip = []
    for i in range(n):
        if abs(P[i].x - midPoint.x) > d:
            strip.append(P[i])

    # Find the closest points in strip.
    # Return the minimum of d and closest
    # distance is strip[]
    return max(d, stripClosest(strip, len(strip), d))

# The main function that finds
# the smallest distance.
# This method mainly uses closestUtil()
def closest(P, n):
    P.sort(key = lambda point: point.x)

    # Use recursive function closestUtil()
    # to find the smallest distance
    return closestUtil(P, n)

# Driver code
P = [Point(2, 3), Point(12, 30),
     Point(40, 50), Point(5, 1),
     Point(12, 10), Point(3, 4)]
n = len(P)

N = int(input())
P = [0] * N
for i in range(N):
  s = input().split()
  a = int(s[0])
  b = int(s[1])
  P[i] = Point(a, b)
# print("The smallest distance is",
#                    closest(P, n))
print(P, n)

# This code is contributed
# by Prateek Gupta (@prateekgupta10)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    x, y = XY[i][0], XY[i][1]
    XY[i][0] = x-y
    XY[i][1] = x+y

ans = 0
for i in range(2):
    tmp_1 = 0
    tmp_2 = float("inf")
    for j in range(N):
        tmp_1 = max(tmp_1, XY[j][i])
        tmp_2 = min(tmp_2, XY[j][i])
    ans = max(ans, tmp_1-tmp_2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = []
for i in range(N):
    x, y = map(int,input().split())
    t = x + y
    if x <= 0:
        t -= 4*abs(x)
    if y <= 0:
        t -= 4*abs(y)
    K.append([t, x, y])

K.sort()

if K[0][0]*K[-1][0] < 0:
    ans = abs(K[0][0]) + abs(K[-1][0])
else:
    ans = K[0][0] - K[-1][0]
A = [K[0][1]]
for i in range(N-1):
    if K[i][0] == K[i+1][0]:
        A.append(K[i+1][1])
    else:
        ans = max(ans, max(A) - min(A))
        A = [K[i][1]]
print(ans)

Submission status: Wrong Answer

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

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

n = readInt()
data = []
for i in range(n):
	x,y = readInts()
	data.append([x+y,x,y])
ans = 0
data.sort(key=lambda x:x[0])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[1])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
data.sort(key=lambda x:x[2])
ans = max(ans,abs(data[-1][1]-data[0][1])+abs(data[-1][2]-data[0][2]))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
mind={}
maxd={}
arr=set()
for i in range(N):
    x,y=map(int,input().split())
    arr.add(x)
    if not x in mind:
        mind[x]=y
        maxd[x]=y
    else:
        mind[x]=min(mind[x],y)
        maxd[x]=max(maxd[x],y)

A,B={},{}

for X,Y in mind.items():
    A[X]=X+Y
for X,Y in maxd.items():
    B[X]=X-Y
    
arr=sorted(arr)


ans=0
mA=A[arr[0]]
mB=B[arr[0]]
for i in range(1,len(arr)):
    a,b=A[arr[i]],B[arr[i]]
    ans=max(ans,a-mA,b-mB)
    mA,mB=min(mA,a),min(mB,b)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ru = [0, 0]
rb = [0, 10 ** 9 + 1]
lu = [10 ** 9 + 1, 0]
lb = [10 ** 9 + 1, 10 ** 9 + 1]
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], ru[1] - rb[1], lu[0] - lb[0]))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

ans1 = []
ans2 = []
for i in range(N):
    ans1.append(X[i] + Y[i])
    ans2.append(Y[i] - X[i])
ans1.sort()
ans2.sort()

a = ans1[-1] - ans1[1]
b = ans2[-1] - ans2[1]

print(max(a,b))

Submission status: Wrong Answer

Solution code:
N = int(input())
min_dist_o = 10**10
max_dist_o = 0
min_dist_edge = 10**10
max_dist_edge = 0
for i in range(N):
    x,y = map(int,input().split())
    dist_o = x+y
    dist_edge = 10**9+1-x+y
    if dist_o > max_dist_o:
        max_dist_o=dist_o
    if dist_o < min_dist_o:
        min_dist_o=dist_o
    if dist_edge > max_dist_edge:
        max_dist_edge=dist_edge
    if dist_o < min_dist_o:
        min_dist_edge=dist_edge
print(max(max_dist_o-min_dist_o,max_dist_edge-min_dist_edge))

Submission status: Wrong Answer

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

tmp1 = []
tmp2 = []
for i in range(n):
    tmp1.append([xy[i][0]+xy[i][1], xy[i][0], xy[i][1]])
    tmp2.append([xy[i][0]-xy[i][1], xy[i][0], xy[i][1]])
tmp1.sort()
tmp2.sort()

ans = 0
for i in range(2):
    for j in range(1, 2):
        if (tmp1[-j][2]-tmp1[i][2]) >= (tmp1[-j][1]-tmp1[i][1]):
            tmp = tmp1[-j][0]-tmp1[i][0]
            ans = max(tmp, ans)
        if (tmp2[-j][2]-tmp2[i][2]) <= (tmp2[-j][1]-tmp2[i][1]):
            tmp = tmp2[-j][0]-tmp2[i][0]
            ans = max(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#create date: 2020-09-13 22:30

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    amax = [0, 0]
    amin = [10**20, 10**20]
    for _ in range(n):
        x, y = na()
        amin[0] = min(amin[0], x+y)
        amax[0] = max(amax[0], x+y)
        amin[1] = min(amin[1], (10**10-x)+y)
        amax[0] = max(amax[1], (10**10-x)+y)
    print(max(amax[0]-amin[0], amax[1]-amin[1]))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

p.sort(key=lambda x:(x[0],x[1]))
p_1 = p[0]
p_2 = p[n-1]

p.sort(key=lambda x:(x[1],x[0]))
p_3 = p[0]
p_4 = p[n-1]

def dis(x,y):
  return abs(x[0]-y[0]) + abs(x[1]-y[1])
ans = max(dis(p_1,p_2),dis(p_1,p_4),dis(p_3,p_2),dis(p_3,p_4))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
mi, ma = 1000000000000, 0
for i in range(n):
    x, y = map(int, input().split())
    x, y = abs(x), abs(y)
    mi = min(mi, x + y)
    ma = max(ma, x + y)

print(ma - mi)

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

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

N = In.int()

x = [0]*N
y = [0]*N

for _ in range(N):
    x[_], y[_] = In.ints()

xfirst = sorted(zip(x,y), key=lambda z: (z[0], z[1]))
yfirst = sorted(zip(x,y), key=lambda z: (z[1], z[0]))

a = abs(xfirst[0][0] - xfirst[-1][0]) + abs(xfirst[0][1] - xfirst[-1][1])  
b = abs(yfirst[0][0] - yfirst[-1][0]) + abs(yfirst[0][1] - yfirst[-1][1])  

c = max(a,b)

xfirst = sorted(zip(x,y), key=lambda z: (z[0], -z[1]))
yfirst = sorted(zip(x,y), key=lambda z: (z[1], -z[0]))

a = abs(xfirst[0][0] - xfirst[-1][0]) + abs(xfirst[0][1] - xfirst[-1][1])  
b = abs(yfirst[0][0] - yfirst[-1][0]) + abs(yfirst[0][1] - yfirst[-1][1])  

c = max([c,a,b])

Out.int(c)


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

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
n=int(input())

x=[]
y=[]
for _ in range(n):
    xx,yy=map(int,input().split())
    x.append(xx)
    y.append(yy)

def maxAbsValExpr(arr1, arr2):
    minX, maxX = min(arr1), max(arr1)
    minY, maxY = min(arr2), max(arr2)
    
    ans = 0
    # For all four corners, calculate the max distance differences
    for point in [(minX, minY), (maxX, minY), (minX, maxY), (maxX, maxY)]:
        minD = float('inf')
        maxD = float('-inf')
        for i in range(0, len(arr1)):
            distance = abs(arr1[i]-point[0]) + abs(arr2[i]-point[1]) + i
            minD = min(minD, distance)
            maxD = max(maxD, distance)
            ans = max(ans, maxD - minD)
    return ans


print(maxAbsValExpr(x, y)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = map(int, input().split())
data = [[a,b]]


a1 = [a,b] #左下
a2 = [a,b] #左上
a3 = [a,b] #右上
a4 = [a,b] #右下

a5 = [a,b]
a6 = [a,b]

for i in range(n-1):
    a,b=map(int, input().split())
    data.append([a, b])
    if (a <= a1[0] and b <= a1[1]):
        a1 = [a,b]

    if (a <= a2[0] and b >= a2[1]):
        a2 = [a, b]

    if (a >= a3[0] and b >= a3[1]):
        a3 = [a, b]

    if (a >= a4[0] and b <= a4[1]):
        a4 = [a, b]

    if(a+b < a5[0]+a5[1]):
        a5 = [a,b]

    if(a+b > a6[0]+a6[1]):
        a6 = [a,b]
ans = -1
data = sorted(data)

for i in data:

    a = i[0]
    b = i[1]

    ans = max(ans, abs(a1[0] - a) + abs(a1[1] - b))
    ans = max(ans, abs(a2[0] - a) + abs(a2[1] - b))
    ans = max(ans, abs(a3[0] - a) + abs(a3[1] - b))
    ans = max(ans, abs(a4[0] - a) + abs(a4[1] - b))
    ans = max(ans, abs(a5[0] - a) + abs(a5[1] - b))
    ans = max(ans, abs(a6[0] - a) + abs(a6[1] - b))

print(max(abs(data[0][0]-data[n-1][0])+abs(data[0][1]+data[n-1][1]), ans))

Submission status: Wrong Answer

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

lst.sort(key=lambda x: x[0]+x[1])
print(abs(lst[-1][0]-lst[0][0])+abs(lst[-1][1]-lst[0][1]))

Submission status: Wrong Answer

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

N = int(input().rstrip('\n'))
xys = []
for _ in range(N):
  x,y = (int(x) for x in input().rstrip('\n').split())
  if (x,y) not in xys:
    if len(xys)==0:
      xys.append((x,y))
    elif all(a[0] >= x for a in xys) or all(a[0] <= x for a in xys):
      xys.append((x,y))
    elif all(a[1] >= y for a in xys) or all(a[1] <= y for a in xys):
      xys.append((x,y))
res = 0
for i in range(len(xys)-1):
  i1 = xys[i]
  for i2 in xys[i+1:]:
    a = abs(i1[1]-i2[1])+abs(i2[0]-i1[0])
    if a > res:
      res = a
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

import random

now = random.randint(0, N - 1)
already = [now]
while True:
    nextIndex, score = getLengest(now, P)
    if nextIndex in already:
        print(score)
        break
    else:
        already.append(nextIndex)
    now = nextIndex

Submission status: Wrong Answer

Solution code:
#import random
n=int(input())

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

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

Submission status: Wrong Answer

Solution code:
from random import randint

n = int(input())
XY = list(tuple(int(x) for x in input().split()) for _ in range(n))

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

x0, y0 = XY[0]
x1, y1 = XY[0]
x2, y2 = XY[0]
mdist = -1
for _ in range(100):
    x0, y0 = XY[randint(0,n-1)]
    for x, y in XY:
        if dist((x, y), (x0, y0)) > mdist:
            mdist = dist((x, y), (x0, y0))
            x1, y1 = x, y
    for x, y in XY:
        if dist((x, y), (x1, y1)) > mdist:
            mdist = dist((x, y), (x1, y1))
            x2, y2 = x, y

print(dist((x1, y1), (x2, y2)))

Submission status: Wrong Answer

Solution code:
import sys
import random

random.seed(60)

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)

first_jibuns = set([random.randint(0, n-1) for i in range(130)])
#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:
import copy
n = int(input())

p1 = list(map(int,input().split()))
p2 = copy.copy(p1)
p3 = copy.copy(p1)
p4 = copy.copy(p1)

for i in range(n-1):

    p = list(map(int,input().split()))
    if p1[0]+p1[1]> p[0]+p[1]:
        p1 = copy.copy(p)

    if p4[0]+p4[1] < p[0]+p[1]:
        p4 = copy.copy(p)

    if p2[0]-p2[1] > p[0]-p[1]:
        p2 = copy.copy(p)

    if -p3[0]+p3[1] > -p[0]+p[1]:
        p3 = copy.copy(p)

print(max(p4[0]-p1[0]+p4[1]-p1[1], p2[0]-p3[0]+p3[1]-p2[1]))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())

xy = []

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

    xy.append(x+y)

xy.sort()

print(xy[-1]-xy[0])

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
x_2 = np.abs(x)
x_max = max(x_2)
x_min = min(x_2)
d_x = x_max - x_min
y_2 = np.abs(y)
y_max = max(y_2)
y_min = min(y_2)
d_y = y_max - y_min
print(d_x - d_y)

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(x[0][0]-i[0]) + abs(x[0][1]-i[1]))
x.sort(key = lambda s:s[2])
ans = 0
for i in range(n):
    x[i].append(abs(x[-1][0] - x[i][0]) + abs(x[-1][1] - x[i][1]))
x.sort(key = lambda s:s[3])
for i in range(n):
    ans = max(ans, abs(x[-1][0] - x[i][0]) + abs(x[-1][1] - x[i][1]))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s,p=10**100,10**100
t,q=-1000,-1000

for i in range(n):
  x,y=map(int,input().split())
  s=min(s,x+y)
  t=max(t,x+y)
  p=min(p,x-y)
  q=max(q,x-y)
  
print(max(t-s,q-p))

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
L.sort(key = lambda x: x[0]**2 + x[1]**2, reverse = True)

base_x = L[0][0] 
base_y = L[0][1]
ans = 0
for l in L:
    ans = max(ans, abs(l[0] - base_x) + abs(l[1] - base_y))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

print(md)

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象限
        if XYnorm[0]< nX+nY:
            XYnorm[0] = nX+nY
            XY0 =[x,y]

    if nX <=0 and nY >=0:#第2象限
        if XYnorm[1]< -nX+nY:
            XYnorm[1] = -nX+nY
            XY1 =[x,y]
            
    if nX <=0 and nY <=0:#第3象限
        if XYnorm[2]< -nX-nY:
            XYnorm[2] = -nX-nY
            XY2 =[x,y]
            
    if nX >=0 and nY <=0:#第4象限
        if XYnorm[3]< nX-nY:
            XYnorm[3] = nX-nY
            XY3 =[x,y]

try:
    XY01 = abs(XY0[0]-XY1[0])+abs(XY0[1]-XY1[1])
except:
    XY01=0
    
try:
    XY02 = abs(XY0[0]-XY2[0])+abs(XY0[1]-XY2[1])
except:
    XY02=0
try:
    XY03 = abs(XY0[0]-XY3[0])+abs(XY0[1]-XY3[1])
except:
    XY03=0
try:
    XY12 = abs(XY1[0]-XY2[0])+abs(XY1[1]-XY2[1])
except:
    XY12 = 0
try:
    XY13 = abs(XY1[0]-XY3[0])+abs(XY1[1]-XY3[1])
except:
    XY13 = 0
try:
    XY23 = abs(XY2[0]-XY3[0])+abs(XY2[1]-XY3[1])
except:
    XY23 = 0
print(max([XY01,XY02,XY03,XY12,XY13,XY23]))

Submission status: Wrong Answer

Solution code:
def calc_dist(x1, x2):
    return abs(x1[0]-x2[0]) + abs(x1[1]-x2[1])


def main():

    N = int(input())
    G = []
    for i in range(N):
        G.append(list(map(int, input().split())))
    G1 = sorted(G, key=lambda x:x[0])
    G2 = sorted(G, key=lambda x:x[1])
    print(max((calc_dist(G1[0], G2[0]), calc_dist(G1[1], G2[0]), calc_dist(G1[0], G2[1]), calc_dist(G1[1], G2[1]))))
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
coordinates_x = []
coordinates_y = []
for i in range(N):
    x, y = map(int, input().split())
    coordinates_x.append(x)
    coordinates_y.append(y)
x, y = np.array(coordinates_x), np.array(coordinates_y)
print(cityblock(x,y))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l.sort()
a=sorted([l[i][::-1] for i in range(n)])

points=[l[0]]
for i in range(1,n):
    if l[i][0]!=l[0][0]:
        points.append(l[i-1])
        break
points.append(l[-1])
for i in range(n-1,-1,-1):
    if l[i][0]!=l[-1][0]:
        points.append(l[i+1])
        break
points.append(a[0])
for i in range(1,n):
    if a[i][0]!=a[0][0]:
        points.append(a[i-1])
        break
points.append(a[-1])
for i in range(n-1,-1,-1):
    if a[i][0]!=a[-1][0]:
        points.append(a[i+1])
        break

def f(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
ans=0
for i in l:
    for j in points:
        ans=max(ans,f(i,j))
print(ans)

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
                edge1 = [x, y]
            else:
                dis = dis_from_edge0
                edge0 = [x, y]
#                 print('#2', edge0, edge1, dis)
            continue
        if dis_from_edge0 > dis:
            dis = dis_from_edge0
            edge0 = [x, y]
#           print('#3', edge0, edge1, dis)
            continue
        if dis_from_edge1 > dis:
            dis = dis_from_edge1
            edge1 = [x, y]
            continue
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())


mi, ma = 1000000, 0
for i in range(n):
    x, y = map(int, input().split())
    x, y = abs(x), abs(y)
    mi = min(mi, x + y)
    ma = max(ma, x + y)

print(ma - mi)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = []
xmin , xmax, ymin, ymax= 10 ** 9, 0, 10 ** 9, 0
for _ in range(N):
    x, y = map(int, input().split())
    if x + y <= xmin + ymin:
        xmin = x
        ymin = y
    if x + y >= xmax + ymax:
        xmax = x
        ymax = y

print(xmax - xmin + ymax - ymin)

Submission status: Wrong Answer

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

for i, pos in enumerate(p):
    a.append((sum(pos), i))

a.sort(key=lambda x:x[0])

ans = 0
for i in range(min(1000, N)):
    for j in range(min(1000, N)):
        xi, yi = p[a[i][1]]
        xj, yj = p[a[N - j -1][1]]
    ans = max(ans, abs(xi - xj) + abs(yi - yj))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
(a, b) = map(int, input().split())
xmax = a
xmin = a
ymax = b
ymin = b
co1 = [(a, b)]
co2 = [(a, b)]
co3 = [(a, b)]
co4 = [(a, b)]
for n in range (1, N):
    (a, b) = map(int, input().split())
    if a < xmin:
        xmin = a
        co1 = [(a, b)]
    if a > xmax:
        xmax = a
        co2 = [(a, b)]
    if b < ymin:
        ymin = b
        co3 = [(a, b)]
    if b > ymax:
        ymax = b
        co4 = [(a, b)]
        
    if a == xmin:
        co1.append((a, b))
    if a == xmax:
        co2.append((a, b))
    if b == ymin:
        co3.append((a, b))
    if b == ymax:
        co4.append((a, b))


list = []
for item in co1:
        list.append(item)
for item in co2:
        list.append(item)
for item in co3:
        list.append(item)
for item in co4:
        list.append(item)

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

dist = 0
for n in range(0, len(list)):
    for m in range(n, len(list)):
        dist = max(dist, man(list[n], list[m]))

print(dist)

Submission status: Wrong Answer

Solution code:
N=int(input())
mind={}
maxd={}
arr=set()
for i in range(N):
    x,y=map(int,input().split())
    arr.add(x)
    if not x in mind:
        mind[x]=y
        maxd[x]=y
    else:
        mind[x]=min(mind[x],y)
        maxd[x]=max(maxd[x],y)

A,B={},{}

for X,Y in mind.items():
    A[X]=X+Y
for X,Y in maxd.items():
    B[X]=X-Y
    
arr=sorted(arr)


ans=0
mA=A[arr[0]]
mB=B[arr[0]]
for i in range(1,len(arr)):
    a,b=A[arr[i]],B[arr[i]]
    ans=max(ans,a-mA,b-mB)
    mA,mB=max(mA,a),max(mB,b)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
p = [abs(a[0])+abs(a[1]) for a in xy]
px = max(p)
pn = min(p)
ans =px-pn
print(ans)

Submission status: Wrong Answer

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