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())
c = [[int(i) for i in input().split()] for i in range(n)]
x_0 = c[0][0]
y_0 = c[0][1]
x_1 = c[1][0]
y_1 = c[1][1]
l = abs(x_0 - x_1) + abs(y_0 - y_1)
for i in range(1,n):
    x = c[i][0]
    y = c[i][1]
    l0 = abs(x_0 - x) + abs(y_0 - y)
    if l < l0:
        l = l0
        x_0 = x
        y_0 = y
print(l)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def getParent(self):
        return [self.find(i) for i in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

class Edge:

    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost

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

sortX = sorted(vertex.items(), key=lambda x:x[1][0])
sortY = sorted(vertex.items(), key=lambda x:x[1][1])

edges = []

for i in range(N-1):
    v1 = sortX[i]
    v2 = sortX[i+1]
    edges.append(Edge(v1[0]-1, v2[0]-1, abs(v1[1][0] - v2[1][0])))

for i in range(N-1):
    v1 = sortY[i]
    v2 = sortY[i+1]
    edges.append( Edge(v1[0]-1, v2[0]-1, abs(v1[1][1] - v2[1][1])))

edges.sort(key = lambda x: x.cost, reverse=True)
uf = UnionFind(N)

G = [[] for _ in range(N)]

cost = 0
for e in edges:
    if not uf.isSame(e.u, e.v):
        uf.unite(e.u, e.v)
        G[e.u].append(e.v)
        G[e.v].append(e.u)
        cost += e.cost

print(cost + 1)

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()
ans = abs(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:
        print(A)
        ans = max(ans, max(A) - min(A))
        A = [K[i][1]]
print(ans)

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][0]+a5[0][1]):
        a5.append([a,b])

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

    if(a+b == a6[0][0]+a6[0][1]):
        a6.append([a,b])

    if(a+b > a6[0][0]+a6[0][1]):
        a6 = [[a,b]]


ans = -1
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))

    for j in a5:
        ans = max(ans, abs(j[0]-a) + abs(j[1]-b))

    for j in a6:
        ans = max(ans, abs(j[0]-a) + abs(j[1]-b))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
hw = [[int(i) for i in input().split()] for _ in range(N)]

minD = 2 * 10**9
min = 0
maxD = 0
max = 0

for i in range(N):
    if (minD > math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])):
        minD = math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])
        min = i
    elif (maxD < math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])):
        maxD = math.sqrt(hw[i][0]*hw[i][0] + hw[i][1]*hw[i][1])
        max = i

print(abs(hw[max][0] - hw[min][0]) + abs(hw[max][1] - hw[min][1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
tmp1 = []
tmp2 = []
tmp3 = []
tmp4 = []
for i in range(N):
    x,y = map(int,input().split())
    if x >= 0 and y >= 0:
        tmp1.append([x,y,abs(x)+abs(y)])
    if x >= 0 and y <= 0:
        tmp2.append([x,y,abs(x)+abs(y)])
    if x <= 0 and y <= 0:
        tmp3.append([x,y,abs(x)+abs(y)])
    if x <= 0 and y >= 0:
        tmp4.append([x,y,abs(x)+abs(y)])

ans = 0

if len(tmp1) > 0:
    tmp = []
    for i in range(len(tmp1)):
        tmp.append(tmp1[i][2])
    ans = max(ans,max(tmp)-min(tmp))
if len(tmp2) > 0:
    tmp = []
    for i in range(len(tmp2)):
        tmp.append(tmp2[i][2])
    ans = max(ans,max(tmp)-min(tmp))
if len(tmp3) > 0:
    tmp = []
    for i in range(len(tmp3)):
        tmp.append(tmp1[i][2])
    ans = max(ans,max(tmp)-min(tmp))
if len(tmp4) > 0:
    tmp = []
    for i in range(len(tmp4)):
        tmp.append(tmp1[i][2])
    ans = max(ans,max(tmp)-min(tmp))
    
print(ans)

Submission status: Wrong Answer

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


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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

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

minx = sorted(l, key=lambda x: x[0])
maxx = sorted(l, key=lambda x: x[0], reverse=True)
miny = sorted(l, key=lambda x: x[1])
maxy = sorted(l, key=lambda x: x[1], reverse=True)

ans=0
c=0
for imaxx in maxx:
  for iminx in minx:
    dist=(abs(imaxx[0]-iminx[0]) + abs(imaxx[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==1000:
      c=0
      break

  else:
    continue
  break

for imaxx in maxx:
  for iminy in miny:
    dist=(abs(imaxx[0]-iminy[0]) + abs(imaxx[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==1000:
      c=0
      break

  else:
    continue
  break

for imaxy in maxy:
  for iminy in miny:
    dist=(abs(imaxy[0]-iminy[0]) + abs(imaxy[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==1000:
      c=0
      break

  else:
    continue
  break


for imaxy in maxy:
  for iminx in minx:
    dist=(abs(imaxy[0]-iminx[0]) + abs(imaxy[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==1000:
      c=0
      break

  else:
    continue
  break

print(ans)

Submission status: Wrong Answer

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

x_ = sorted(x_y, key=lambda x: x[0])

#print(x_)
ans = 0
for l in range(n):
	for r in range(n-1,l,-1):
#		print(l,r)
		kyori = (x_[r][0] - x_[l][0]) * (x_[r][1] - x_[l][1])
		if kyori < 0:
			kyori = -kyori
		if kyori > ans:
			ans = kyori
print(ans)

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(20):
    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 itertools

n = int(input())
ps = list({
    tuple(map(int, input().split()))
    for _ in range(n)
})

g0 = sum([p[0] for p in ps]) / len(ps)
g1 = sum([p[1] for p in ps]) / len(ps)

maxd = 0
maxp = ps[0]
for p in ps:
    d = abs(g0 - p[0]) + abs(g1 - p[1])
    if d > maxd:
        maxp = p
        maxd = d

maxd = 0
for p in ps:
    maxd = max(maxd, abs(maxp[0] - p[0]) + abs(maxp[1] - p[1]))
print(maxd)

Submission status: Wrong Answer

Solution code:
import sys
import random

random.seed(2)

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(100)])
#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 numpy as np

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

# xとyの最小と最大を求めることで、一致すると、基準となり得る
# XとYを足せば良い
# 最大値は関係ない
# Xmax+Ymax-|Xmin|-|Ymin|
# 何かの数字を利用して候補を減らす


# XmaxとXmin, YmaxとYmin, (X+Y)max, (X+Y)minの４点を調べる
# XmaxとXmin, YmaxとYminの４点で最大と最小を求める

def manhattan(p1, p2):
    return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])
n4 = []
n4.append(pos[np.argmax(x)])
n4.append(pos[np.argmax(y)])
n4.append(pos[np.argmin(x)])
n4.append(pos[np.argmin(y)])


# 上記４点間でmanhattan最大値を求める
d = []
for i in range(3):
    for j in range(i+1, 4):
        d.append(manhattan(n4[i], n4[j]))
        # print(d)
print(max(d))

Submission status: Wrong Answer

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

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

ans = 0

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

x, y = xy[0]

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

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

x, y = xy[0]

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

for i in range(N):
    xy[i].append(sum(xy[i]))

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

x, y, tmp = xy[0]

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

print(ans)

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)):
    xi, yi = p[a[i][1]]
    xj, yj = p[a[N - i -1][1]]
    ans = max(ans, abs(xi - xj) + abs(yi - yj))
print(ans)

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]**2 + x[1]**2))

a = []
for i in range(min(n, 1000)):
  for j in range(min(n, 1000)):
    a.append(abs(p[-(i+1)][0] - p[j][0]) + abs(p[-(i+1)][1] - p[j][1]))
    
print(max(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
a,c,b,d=0,10**10,0,10**10
for i in range(n):
    x,y=r[i]
    a=max(a,x+y)
    c=min(c,x+y)
    b=max(b,x-y)
    d=min(d,x-y)
print(max(abs(a-c),abs(b-d)))

Submission status: Wrong Answer

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

# main

N = int(input())
xy = int_mtx(N)

x = xy[:,0]
y = xy[:,1]

xmin_p = set(list(*np.where(x == np.min(x))))
xmax_p = set(list(*np.where(x == np.max(x))))
ymin_p = set(list(*np.where(y == np.min(y))))
ymax_p = set(list(*np.where(y == np.max(y))))

ans = 0

for xmin in xmin_p:
    for xmax in xmax_p:
        ans = max(ans,abs(xy[xmin,0]-xy[xmax,0])+abs(xy[xmin,1]-xy[xmax,1]))
    for ymin in ymin_p:
        ans = max(ans,abs(xy[xmin,0]-xy[ymin,0])+abs(xy[xmin,1]-xy[ymin,1]))
    for ymax in ymax_p:
        ans = max(ans,abs(xy[xmin,0]-xy[ymax,0])+abs(xy[xmin,1]-xy[ymax,1]))

for xmax in xmax_p:
    for ymin in ymin_p:
        ans = max(ans,abs(xy[xmax,0]-xy[ymin,0])+abs(xy[xmax,1]-xy[ymin,1]))
    for ymax in ymax_p:
        ans = max(ans,abs(xy[xmax,0]-xy[ymax,0])+abs(xy[xmax,1]-xy[ymax,1]))

for ymin in ymin_p:
    for ymax in ymax_p:
        ans = max(ans,abs(xy[ymin,0]-xy[ymax,0])+abs(xy[ymin,1]-xy[ymax,1]))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def f(x,y):
    return (x-y, x+y)
d=[]
x1, y1 = f(*list(map(int, input().split())))
for _ in range(N-1):
    x, y = f(*list(map(int, input().split())))
    d.append(max(abs(x-x1),abs(y-y1)))
print(max(d))

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,4000)):
  for j in range(i+1,min(n,4000)):
    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:
n = int(input())

manhat_list = []

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

print(max(manhat_list) - min(manhat_list))

Submission status: Wrong Answer

Solution code:
import sys
import math,bisect
sys.setrecursionlimit(10 ** 5)
from collections import defaultdict
from itertools import groupby,accumulate
from heapq import heapify,heappop,heappush
from collections import deque,Counter,OrderedDict
def I(): return int(sys.stdin.readline())
def neo(): return map(int, sys.stdin.readline().split())
def Neo(): return list(map(int, sys.stdin.readline().split()))
n = I()
A = []
for i in range(n):
    a,b = neo()
    A += [[a,b]]
A.sort()
Ans = 0
p,q = A[0][0],A[0][1]
for i,j in A[1:]:
    Ans = max(Ans,abs(p-i)+abs(q-j))
print(Ans)

Submission status: Wrong Answer

Solution code:

import copy as cp
N=int(input())
A=[list(map(int, input().split()))]

temp1=cp.deepcopy(A[0])
temp2=cp.deepcopy(A[0])
for i in range(N-1):
    f=0
    x,y=map(int, input().split())
    if abs(temp1[0]-x)+abs(temp1[1]-y):
        temp2[0]=x
        temp2[1]=y
        f=1
    if f==1:
        for i,j in A:
           if max(abs(temp2[0]-i)+abs(temp2[1]-j),abs(temp2[0]-temp1[0])+abs(temp2[1]-temp1[1])):
               temp1[0]=i
               temp2[1]=j
    A.append([x,y])


print(abs(temp2[0]-temp1[0])+abs(temp2[1]-temp1[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)

first_jibuns = set([random.randint(0, n-1) for i in range(50)])
#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:
n = int(input())
l = []
for num in range(n):
  l += [list(map(int,input().split()))]
maxn = -1
maxx = -1
maxy = -1
for num in range(n):
  if maxx < l[num][0]:
    maxx = l[num][0]
  if maxy < l[num][1]:
    maxy = l[num][1]
for num in range(n):
  if maxx == l[num][0] or maxy == l[num][1]:
    for j in range(n):
      if (num != j):
        if abs(l[num][0]-l[j][0])+abs(l[num][1]-l[j][1]) > maxn:
          maxn = abs(l[num][0]-l[j][0])+abs(l[num][1]-l[j][1])
print(maxn)

Submission status: Wrong Answer

Solution code:
n = int(input())
min_dis = 10 ** 10
max_dis = 0
for i in range(n):
    x, y = map(int, input().split())
    tmp1 = x + y
    min_dis = min(tmp1, min_dis)
    max_dis = max(tmp1, max_dis)

print(abs(max_dis - min_dis))

Submission status: Wrong Answer

Solution code:
import time
start = time.time()
n = int(input())
ps = list(map(list, [map(float, input().split()) for i in range(n)]))

def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs)>1 and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs)>t and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs

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

def rotating_calipers(ps):
    qs = convex_hull(ps)
    n = len(qs)
    if n == 2:
        return dist(qs[0], qs[1])
    i = j = 0
    for k in range(n):
        if qs[k] < qs[i]: i = k
        if qs[j] < qs[k]: j = k
    res = 0
    si = i; sj = j
    while i != sj or j != si:
        if time.time() - start >= 1.8:
            return res
        res = max(res, dist(qs[i], qs[j]))
        if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
            i = (i + 1) % n
        else:
            j = (j + 1) % n
    return res

print(int(rotating_calipers(ps)))

Submission status: Wrong Answer

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

minx = sorted(l, key=lambda x: x[0])
maxx = sorted(l, key=lambda x: x[0], reverse=True)
miny = sorted(l, key=lambda x: x[1])
maxy = sorted(l, key=lambda x: x[1], reverse=True)

ans=0
c=0
for imaxx in maxx:
  for iminx in minx:
    dist=(abs(imaxx[0]-iminx[0]) + abs(imaxx[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==100:
      c=0
      break

  else:
    continue
  break

for imaxx in maxx:
  for iminy in miny:
    dist=(abs(imaxx[0]-iminy[0]) + abs(imaxx[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==100:
      c=0
      break

  else:
    continue
  break

for imaxy in maxy:
  for iminy in miny:
    dist=(abs(imaxy[0]-iminy[0]) + abs(imaxy[1] - iminy[1]))
    ans=max(ans, dist)
    c+=1
    if c==100:
      c=0
      break

  else:
    continue
  break


for imaxy in maxy:
  for iminx in minx:
    dist=(abs(imaxy[0]-iminx[0]) + abs(imaxy[1] - iminx[1]))
    ans=max(ans, dist)
    c+=1
    if c==100:
      c=0
      break

  else:
    continue
  break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
for i in range(n):
  x.append(list(map(int, input().split())))
a=2*(10**9)
b=0

for j in range(n):
  if sum(x[j])<a:
    a=sum(x[j])
    c=j
  if sum(x[j])>b:
    b=sum(x[j])
    d=j
if c==d:
  print(0)
else:
  print(abs(x[d][0]-x[c][0])+abs(x[d][1]-x[c][1]))

Submission status: Wrong Answer

Solution code:
import os
import heapq

import sys
import bisect
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase
from functools import reduce


def convex_hull_graham(coordinates):
    def change(a, b, c):
        return ((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) < 0

    def left(h, r):
        while len(h) > 1 and change(h[-2], h[-1], r):
            h.pop()
        h.append(r)
        return h

    coordinates.sort()
    lower = reduce(left, coordinates, [])
    upper = reduce(left, reversed(coordinates), [])


    return lower.extend(upper[1:len(upper) - 1]) or lower
def d(one,t):
    return abs(one[0]-t[0])+abs(one[1]-t[1])
def find_max_dist_graham_c1(L):
    L = convex_hull_graham(L)  # Get ordered list of convex hull points
    L.sort()
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        loop_max_dist = 0
        for j in range(i+1, len(L)):
            curr_dist = d(L[i], L[j])
            if curr_dist < loop_max_dist:
                break
            loop_max_dist = curr_dist
            max_dist = max(loop_max_dist, max_dist)

    return max_dist

def main():
    n=int(input())
    arr = []
    for i in range(n):
        x, y = map(int, input().split())
        arr.append([x, y])
    print(find_max_dist_graham_c1(arr))
main()

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

Out.int(max(a,b))


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

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())
l=[]
for i in range(n):
  x,y=map(int, input().split())
  l.append(x+y)
print(max(l)-min(l))

Submission status: Wrong Answer

Solution code:
from sys import stdin

readline = stdin.readline

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

xy = list(set(xy))

xy.sort()

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

Solution code:
def f(x, y):
    return x-y, x+y


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

max_x = 0
min_x = 2000000000
max_y = 0
min_y = 2000000000
for xi, yi in p:
    x_, y_ = f(xi, yi)
    max_x = max(max_x, x_)
    min_x = min(min_x, x_)
    max_y = max(max_y, y_)
    min_y = min(min_y, y_)

print(max(max_x - min_x, max_y - min_y))