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: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
p = []
m = []
for i in range(n):
    x,y = map(int,input().split())
    p.append(x+y)
    m.append(x-y)
p.sort()
m.sort()
print(max(p[-1]-p[0],m[-1]-m[0]))

Submission status: Accepted

Solution code:
N = int(input())
XYs = [[],[]]
for _ in range(N):
  x,y = map(int, input().split())
  XYs[0].append(x-y)
  XYs[1].append(x+y)
  
print(max(max(XYs[0])-min(XYs[0]), max(XYs[1])-min(XYs[1])))

Submission status: Accepted

Solution code:
N = int(input())

xyp = []
xym = []

for _ in range(N):
    x, y = map(int, input().split())
    xyp.append(x+y)
    xym.append(x-y)
    
xyp.sort()
xym.sort()

print(max(xyp[-1] - xyp[0], xym[-1] - xym[0]))

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
d1 = [] * n
d2 = [] * n

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

print(max(max(d1) - min(d1), max(d2)-min(d2)))

Submission status: Accepted

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

N = int(input())
l1, l2 = [], []

for _ in range(N):
    x, y = map(int, input().split())
    l1.append(x+y)
    l2.append(x-y)

print(max(max(l1)-min(l1), max(l2)-min(l2)))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xym, xyM, x_ym, x_yM = 10**9, -10**9, 10**9, -10**9
    for _ in range(n):
        x, y = map(int, input().split())
        xy, x_y = x+y, x-y
        xym, xyM, x_ym, x_yM = min(xym, xy), max(xyM, xy), min(x_ym, x_y), max(x_yM, x_y)
    print(max(xyM-xym, x_yM-x_ym))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
z,w = [],[]
for _ in range(n):
  x,y = map(int,input().split())
  z.append(x+y)
  w.append(x-y)
print(max(max(z)-min(z),max(w)-min(w)))

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
q = [[x+y, x-y] for x, y in p]
print(max(max(q)[0] - min(q)[0], max(q, key=lambda x: x[1])[1] - min(q, key=lambda x: x[1])[1]))

Submission status: Accepted

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

def main():
    n=int(input())
    XY=[tuple(map(int,input().split())) for _ in range(n)]
    U,V=[],[]
    for x,y in XY:
        U.append(x+y)
        V.append(x-y)
    print(max(max(U)-min(U),max(V)-min(V)))
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
L=[list(map(int,input().split())) for i in range(N)]
zmax=zmin=L[0][0]+L[0][1]
wmax=wmin=L[0][0]-L[0][1]
for a,b in L:
    z,w=a+b,a-b
    zmax=max(zmax,z)
    zmin=min(zmin,z)
    wmax=max(wmax,w)
    wmin=min(wmin,w)
print(max(zmax-zmin,wmax-wmin))

Submission status: Accepted

Solution code:
N=int(input())
zls=[0 for _ in range(N)]
wls=[0 for _ in range(N)]
for i in range(N):
  x,y=[int(s) for s in input().split()]
  zls[i]=x+y
  wls[i]=x-y
print(max([max(zls)-min(zls),max(wls)-min(wls)]))

Submission status: Accepted

Solution code:
from operator import itemgetter, attrgetter

class P:
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __add__(self, p): return P(self.x + p.x, self.y + p.y)
    def __sub__(self, p): return P(self.x - p.x, self.y - p.y)
    def dot(self, p): return (self.x*p.x + self.y*p.y)
    def cross(self, p): return (self.x*p.y - self.y*p.x)
    def abs(self): return (abs(self.x) + abs(self.y))

def convex_hull(Ps):
    Ps.sort(key=attrgetter('x', 'y'))
    ret1, ret2 = list(), list()
    for i in range(len(Ps)):
        k = len(ret1)
        while k>=2 and (Ps[i]-ret1[k-1]).cross(ret1[k-1]-ret1[k-2]) <= 0:
            ret1.pop()
            k = len(ret1)
        ret1.append(Ps[i])
    for i in range(len(Ps)):
        k = len(ret2)
        while k>=2 and (Ps[i]-ret2[k-1]).cross(ret2[k-1]-ret2[k-2]) >= 0:
            ret2.pop()
            k = len(ret2)
        ret2.append(Ps[i])
    return ret1 + ret2[::-1]

N = int(input())
Ps = list()
for i in range(N):
    x, y = list(map(int, input().split()))
    Ps.append(P(x, y))

# produce convex hull
CPs = convex_hull(Ps)

# brute force
ans = 0
for i in range(len(CPs)):
    for j in range(i, len(CPs)):
        mdis = (CPs[i]-CPs[j]).abs()
#        print(i, j, mdis)
        if ans < mdis: ans = mdis

print (ans)

Submission status: Accepted

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

N = int(readline())
X,Y = [None] * N, [None] * N
for i in range(N):
  x,y = map(int,readline().split())
  X[i],Y[i] = x + y,x - y

print(max(abs(max(X) - min(X)),abs(max(Y) - min(Y))))

Submission status: Accepted

Solution code:
n = int(input())
k = [0] * n
l = [0] * n
for i in range(n):
  x, y = [int(i) for i in input().split()]
  k[i] = x + y
  l[i] = x - y
print(max(max(k)-min(k), max(l)-min(l)))

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess
import zlib


exe_bin = "c%1D#dwf$>nm0+)mPd1f1B#Ch87GXyv9*;~JAyW)!5a(@vG`_U`Us7-O(#vU@>|C`0mf_zbR1`vonc1yH|#7kJG;Z|?jSnKw4kv(1*r;Dv{WhyMMR0nv)S)EkL2by8Fkj*{^jj2_uTJ0=X;*-eD~gS&*_sk$84=eBZ)&N-6kQ__e}<uar~AUi6($6kw(Dzn^L}%4RDsCow_`yNiA~|au{8Smci=sIw`f(C`!GQ`8ak%YAH#k1Rd&HSHQ4!1*Vj86PLT-x!e>wEvIYabZxx7C?!rON<p2)f0Z1sE-R$eGK-fB2K+U6-8qrL>atQwEd||OK$k6j@x#c=g<M`HzpUl@ic<8$&GnwDX;W^luPLbaG`6%Bw3bXOm^P)b*;{xE)yc@)-Z5_xZIAseT!r;xIS%W;(|pr2H$L;bYkk3D>$#a9-hSoSc~4_oA|?9``=d=`q&Vbl$zOHdl0`0I#<1gK_+6g{-wnSj(%|39fd5Md{Dutp!3_8xWxzLNz)z4w1gZ{A`u4^Q?QhM1KbAr6q73-g;WtLQS~3+eZX(YA%<)Akyae&l?60Z*?sqXJrb$lck_K<1v)S+R`JGP5X|J5?tf}?YF7Y(`Ykie-XVrTfYb#w<^|h=nea!>&?)H~>yv@!kS99$Yd!xr+QEXd^%v)QXO|`yeZ=<W;<A2<_v?yKUS=bm9s}?$eI@OOltLq+hx?P@n2^97;0=l}@<#hRLTRncMp|+v9){iyb7C%%0+~8eWi!_q^F`vg@E4h8Ot{P6|_MigGKvgHo;r2GTfbFdN?z5KLoyCQdr8^w<asZu^3#YJa=PimWCH9uWspw2C{ORDA1wTC<4{R(Uq@~vyIBR$u6v6MnA0O4@$hktpaDK}(xtKZgH6o03(l4ZB9vJKK<l)G)i1t@|M&JmY%;A=65Y|e!b9#{<M1S{9U}cjEzn-wNRgLHEb5(I8;C(l<GFwXK96Syx@FNuXJ_UZH0v}P}M=9{975LE#{5b{QpuiisUK)k2c!=?U_avgg7b)<{B(;|F&ykY(5Rdf=yiS4NsK93_@S7BP<^6Dr0<XLubSm&U3VgQ$pQpgffs?s%yZ+T1Op?5!)31&1lLN2hZkOUy7Xm6iu@cT?LK$2kT!$plzBn8c=OB!3iteLuIl^daw3EW$Ll{krZldrl2%~Ay^%TAlVKgb)LE-BWMpL3~6ut&vcZbk(ksKVb-fO+by2x7T2o>zvZkFzL1P4KVS#F;h-abjHk=wH-PC}D{w(jCixqa$Jz{;gVWcfu9LpEp680pWQVQQIx_Q-*-Mh;G00Zp*R<Ua+qC!n=IEQjtHE0?}aR^A0<GYZJ^DzI|K&17|HHZuRD_-yfxj?m~}ppVFbZNO#R?Z728S|*#dGj4uzpltbBvV1<!e0E5#?gDK(<WSbDS5jy9ot7=H$idpRtXMC%FY1unZENMOex2N&D~Dzn<<i&W;NBMF;B?f}(Jnbk!*=30EeAStp|0ga+8%(xF=PU(@3NEm-OBp)vSqIv{8(-;ku}@o(rt2ZsD%tp6YUlJw(<5U{9Xfo=UDwdsJ9Hsp_vyaLWG3!V_1~#m5Jly$d++nQu{c|HZ#-&FmC109F1JsMFJ7%=&*JqbVER&3-ubg{fX`xdGZX}Lu7>xTq}oa4?bvp$hz42eXDcvc5plT@=O=@$ZQQd{4L<Jm4?_q4#ne{oOvA1D|XnS3_h_5erp}UC)ShI{{kc-Yupi<xW3CQ*^191VJ?f0E#UN-KLJS)B|n0~9y~__<y|cXilOcNNWZ@Ays5<^hh}TYgbF0m-%mBmm4jh$jRvayC$QlF2F>%(5Q644vT{4<+jbtJ=6ZSoR-6Z>#cyE175BQygyn49g|dDbI7%P{wWvnuI;$K!Er*tB$mV%*AbaxN<!|_P@@Kt{(oWDzgL)a;E|@^C3nN<!<d7`%%IoSxy~fBv2!SpQwmAW9`~#HIuSHq%SbJ$VS@}E&Zo5$6uWGvhdOeDIokd$9o@ET^e$Yqn19pf6%p9_LK^)pXc@$zAwK)Xc2rfP-Yj(+&?mL6mO`j9Ynr;t-a~-8ETgZyvg3qIqF2~~?s37Pzk?OWULj^XVF2Qcvqk}(oGyTEAAoTKIvE4ikb=YmRUHC=X^REC)h)cVr^93VDSTO7eZgT{WJA$^2k);>oaYwstquic%=eJGLix`8H{ru2FddXpdhVMCoi#JA|pbZyqv}+*F^lScVmK?$S4iIV$>!i8C|3E@3*}Mp@2cm~C*esuMc^Bp21&|jR2`uJ@D)J#_^4`5(DNME;b_8Fe3XKyAg{IyJLhPDOM^HbB%8?Xu=As-&yWRjb(Y@%e;y04!9gqC_0%*{l_gIP;toSojI5ZLP*nzE+q%b1;xZadE@O%*}APC6vgTNO8fh>O=E~2L{Q$Io=28XC9WH*h;As|PHpz<PfnH)#(0}xfmL{YtA+}sZ!7YE}8h5%Xq<|Pny9%Sx@i|8Pn?7_~c6+}W*7xzY|!&UK)=+?_g$J&FJz_E~6v|G*6ouP*&N|BA{sWwl2E5*6cgO>itOIQb;7tBBWGH9a%RSUY|3ho76FPkBD^e?`Qoq8%d2UG`<U6-gx86_ud24<0RCgs|1nGyn+&G(;Yz70+F0xPh)>1AQJO&AR3KLFSnCbD8TG>`t7G23b~VH5~{kwQcV^9kj1IQj{7b4zFO4mtQ)^bZ%PX756q$eZV|S70364Y~E)OPEM!YCwSe)JdZTd0l5dLw=ZLc9Z%}V#zW`UI79*G;S&i3{8FOB}`#6uL3Bt3~RV8!0b-I6`ze%0M<>sS!NhbSvcH-?-7fBHPA&Yl+|Al|6<uX%mtAvY3q+5RR$34t{~o-KFso=pIX<U`|@Xij=(PrznSBq2Acrj*5As3y#E?YFWj#Y%X0H+a0qQ~<p_MR!uuK^yj_rH%Aocw0IIqW(+AKg<dVM%xe)h0H;MJRZDi;W)a3t|BE36_rPBN`v`1|0bvNnRjl@Tx3feb+Yy#*JfMRb$)lOtLZZTtb5`mM*Z$DnefZ|PnViAC1pAn1MOsTA-=S^Vr2{P(=3mSOOVDnQXyz>Y^RcDB$-rVFSzN1>K`~XhwQ^=<e^*Bax6~yufa~qm(MIpfdIN}EpJjr$IVM1)=kwJh?peumPZ#JU4-o%yz6)4Jt())qvII%oy#%ChN4;u6!(*Yq{aD)pIK5+yX9zfC$+@$INs5_u_BOmCTeri52-(X(Pbwp0F)65>`o7mgLQe!S+d;#@7^^(FdfIADPN8U#V#E|r41(K8@zYnNm0sbHJCKO>~JW=bO0bmj{F?IlAQ|~7v+=Ch;Q1uCD+pk48d?38(H!onlS3&)-!Q9FH@DX(sHao@ok_rIu1d{?FcF7|r5cetVNZMhvhxT#RC_zMYQ;b#i@k$KIo(&A-0+F$e%ZXY^_}CF-d=zSYF)dsUu}clqUpUDG5Z^JZ@qUOkpVCI`k~TU*-3KQZdebwA;5&GQB3xMOdWVHULPS3oVI>!6)iF5r=07ur_9t(1EU5<XLo0C|M!qxz4j@Ry^sowGaMu`W=8|3<a+QqRU@x((V-6r*7<E;LkQ!UOi=EUfczF+^gKz}JdWASIy?Phjg+f@w<4}*ihkbJxYjHR}vLCwzb&K^gE*01W$lgJ+Gt}V+z}JT%OnmQag-qWk7$`%ayYGy~O)l&Lt)NBKk*`)o9K(;i`PHa6$h_#<<0hUX%zon91s9$JTwfQ>TW`Rr>J8|Wyq5^=2awHk$U!#?#MohGCZG;85>OcUH-AcPKw}?ygBn6$cv*2&RA9;l#ZfY(8RSE4LEX9az~cl7AIV@v1!fCw3R4)=?D<0K^`ud+=POo^YxceyWfB*#_q@YgLtF=#lfl90Tko^{4%IvEK?6&JKoJAwm+WMBlfk@&SV3ar9x$*QTofuCaQh*#ygO)B&n|Y;AwBzPRg++ocLS~W-eg9)8c6GC6h<5dC>`G<mak<@b_*uEgs)=x$Kg$#g!d!ODseA~VWfeNfqi!#)94|yf{t^EQko8)!1^(r>RHGqA|5!bOmHYus1VC<%;ScMZmTpGk#O_~>rmvpo~45KxlrGL9{EknWAd;^^DTMYFe^2g>2-)w^BY18f+sdn!->!vd9l&dO1N!v0#FKEw}6BX9pRjTo~M4A@nR?}@1+EtjotKO6Mx50(1@}Ear9P>qZa~<^c<zE=nVkENRKq*T1L~(&THW8c8TYSo}DCo6gvVGtJ;aV90_m`d-r1C?_#4E#C0dq%Pw(C@b1c#US4N9^Pvs{^^2vKok!Ti2baksAJzI8BOl`sQcKmIuU5q`l>t9T#VB*73&yu+j~JYI7x19+;P$Fri9x!bS^#78`H?IM?qqfeOWtE60?bKP>=ao6lMOy2V!{FSA>w-Wu*~!2lFgpKZ4Y`GLbYmlQsFP5XwPs(d;TwqV#@hj+8$*-hC4s;-~byC-h!te;yNU{!9kz0X#}_qvvi5i@A!~#(+Dh=97v{2X!zQ&G}Og2A{iVvl2XKuFpi3>xtoN$Qc@gEIYW7m=h75YPalVo#MhV25~+zLQe=V8RcwUfQ?+*;OL@!?mU{3hiQS6O{V~V}5UMm%;f_PXyHNB&DyIm2mJJR7tv!dBs4^x3`j5D_bG{y7V~pRiD1}Ih(B`DVMo@`nJ4HGhVA@iRsE`E;oqF~Aa~PM861POI<vN!4sDM;1l-#?4Co|-eLeDZDQywjZt5fd8Q@D-4^7NDNJ1FKTro(LdKteotuY$4a0=+#asSNfIh>tF4d0h`aoqQ8jCJ#e{CE$rcJ%hn%R#NvWoF3l8_|`%B@BkSj?_(~l+XnDXGUnk<!1a+aWvAuRePqRZAH$pJQ?JlB;Ltex82YZe42lQg^%&>XqM<0fs1}OJG@RG?&>r0XeL2`K2acUyQ0WNiN8)U4DDS6qrg7#=KoB4ImeC}|_`K6h4KQ3JhxF%-IHh?`4i5OQmfQ8eH?pblyv6apq=?1a>04`Ia{g{+myzoAq7m6xhJaq~8q(o3URUIHSreA`5BbLf!yj;lqmf}Ier+><0?nkBo8`dF33!DQ-u}_>az6*4$cK@5JR*Y$VZ8@n4U*$%k<M&q^Jv(7anv2h_jhVv`#;I}#@?QHy-`ebST00=7UA;^Y##lOI9aghZaNophJ6b7BP9#j#@b6?B`foEK)0foEPoc?+n?TxGjm(w?~kINx9y>q%s5RTmu@GkbsAcA`!eI12PBGG)4@>B`R0uu!BL+w2IOCRA`(Ykp`)ndOXaH=s*F4rt{|JkWn}YNd!TbvAUw+5Ay@CUzi{XMD@)#bwPA`Jh-MAuQ9JDIe=t*xg9ihrvh1H7mAg)il0DmuH=x1W+q0gNg9m~Yc@omdPhB8@e{$y*{0@;It=?-nEw7bBS!-p@YjWUxE(!b$R6pC5MONT?0eQs^KOviQ&UR^^wn=0~7HB+Ivz!qJUderMG0tLdXMTU`;&UrC5?OswqCkAdFK#7k3|a>CeX1vGiW%_a&(}(1%|-^4l@qCq{7Pweb|9P$HK;IIb9pEpr%F45U8rnyUK~5J40}pLd+KT}TEvtJOGWkoyVRs8ScaaCSO438Z|=*Z&R@a0C>~tgYOB^z)PHhRr}vYU-)3EOhM}GeZ}?$Im!^wIAWWhU3@L|XLh~~WIIcrrHZlratR`!I0$2ET;NnQK4(G)JomvX~stYHvu`lewZqXe-`oT~#u5;wjqFg!94+GW)U<HocioA2O<xN==l`S91furXb)qOaR3lM$`nvx?2r)b$Xjc(sZ(HTQ3|J?=(g>6!S@S*%!uN<n=*n=!cqIx!e3Il5YXc*7I6Jkus!OM}`2IBF#!40e>&VhDVx8SF(t@Qg=8IW4H;8(`2c#0NL7{6X_#Z&akA%wqyFrK1DT904pw&E!&Q5e61ZpBmd1Dw<Be1U#TdxO&Am;9}GiuQo;_8jm`dj+`!ez_D~c$v+2DztW3`f>L6>0=75JE7SYtbBofvs*^_jzPY7ivGhTgz@vqRy;+k&>hdiZQ2b&hN2%{qCz&0QVVee2O=h=oV9E|AHU_<gKx7mG%=h@Q*pswDDSogFWZA>9hL!_kh(7GBKN)z+*f?)Hx>7a_;TQ+{Mm}&N7ne*cjUl!h}|PCCz8RA-;}m@B;)bScK)rCe%)l>(bWfPjaYPmQT5AG{c=^m(W>7Px7)4!#ii80BGoZr#o%4a-+{SRM&(a)t?pJ_3xomC)E|%IqsD0{ah;0<?!hmyeQ=Lk3#I9NJl+K8q6_gj8npn*@lfsq*LOl$2Du}bn?F|AzHFhSX$3K(b8<U0IYz|enyiiI;_>e)e3ZVuB$;{p?xXQIy)hY#vkl|tkWr82wn?{NbL)+h&DRThTnl9a-Id?h6YIa0EpSlIIlo*y!X#ZQ_#++4m;|<6i+w=YY5@oQo<&;${{(hSxxpCHmK(;e(#ZzX$}Fp4Qb0e)P^6ox8EKegHJGf1@zA8)kUM*n_Gc=TZIpDA#MaDofE~T~HQH)0uGG%T%a+&ZR%eCutFq-lj&6@;B<N)w#dI2rK7||WWWw49w2KVuwK^>^80Q<fk!bS_XqOA)rdDElu0cIl>ud&7D68BsX_a0!6s^pb4JCn`xrQ>Ip~Pw^0{zPkrgEVnjm71_2Xlxrg5z=J>WQz9uaB>fuaB>f|L;Srj}z<R#QHbox@Kkh3toz~Y2*3*Lafos;_HF0=CD|gcP)p-nzL(oDc0YK`>D9cemWHQVky@5inV0-@x^9h4Ou6z7i;V8<cf+lb>n$CPD(w*TDCU6&P?2!Hu6$DH;6T9SMjnbClz0kovL>UmoL@;3i*85dZOLMII~Z~Q9~T==7z>OEc80f;SIe0JcpHQ@4m_-v5s7I%;pB%!%H_Wm-2EYFMrO<-zp!P{*FVeyA;PAvu1tIG-**)OQXNVG`(<YVNt>4777*ru(+hKXo`hlzX)#~c)w)$V>MmTTA3EFll*D%S&2AJ#p@ICnTpR&#BnM<C(*yD_}oNXq~b>;;x83HG7+b#_)&@Rnu;GS6{W@JNt@E*4N_-XJV}iIRJ>6#rp1p*>>o(QUm=bEPCEQIq`n){;m0QOOe%g{BEO{KuS^@?IvC|5AEe@86c?q#C)b^);;$Ko!?chkeH>TgF&}EdpCbQG=H<63&DGMT-IEgZc-)eK&rHt8I3X2(JI60j;TH<IDtsN6TcTK3jK^d2dbmG-&H41H`23!>AKovS^xr|-Um?Adrhn75f193%$Il7MXL$dfq35x~^v}{TyjstzG{|RoJQQfs?>Dg0_2}cJ@v3;hwSlHI@gq|{$#Egl!M&RF`$L-P{)*(d>*eFVHN(D(RmfjEepvqeXUg9oo#y=|?#r71|1D^5RIhv2A^+jydbcM1{)+c9=yM?hzFf=f68pNuyZcyehJ7y-KRk~WX_>uh|Ig5}eo^}$1Ih^cZ{g!h9Cj`9kC8Wjf_F?q27TJJjE`FGstoP_#O>`cGq{%HyE3%z*QVbmGsO8wykEp^#-K~jr$CpU&kP;w$1<+}f_2PbYlij@X5jDDrH?BFk^lPL%wQvr^pzR-NH%AMr`hkE>uN2mZfcU8cR1#kTOCekb4!)ej{8_7=L2{99VJeu$LneI_@!!}zuDj7b{AGl$&EWse}l6cH|R7=PG^nRxuo7(<*Ikq_`SYnr>mt^s`fTC)z|uKYYL}ND=kUi2&H+PE}zf!xU;s=?|WQw`&<pR&YG5nhR1<K0Xb2Xl%`JS?1k33Hm7Y~1@0?y-Z5{H(<XDIT(MAcR@^_&I@dl6>QabnQW12gPQnfIXV1RdR_Uy?mOE@tzWb-FOt~w^SzF`syCkQ5zLRbna<(+rs&@gUQqWyMY(J5Tm9wVV>#TD%*04QJ(`LJx{r36O7x+Al;Nyy0Y)hqzdkcNF?!vS?ov3^@OT|W|WEE~LQf_Zj6Q%BlO4cG(<=j~bC!^`YW5e{FO1DMXTOFPvo6WYg(#dv6sby6)Hz!%7+o{C~_&zDVp{lyMh4xz7Jzr&IicMC3bBkG$8OGl5-CAm8Q#P-;=~l3eyVTgWFcpX4y-GK(rQgt&YPnR{{CI=kRRyKr$I3c!MOigTg^gZ+Z6R1*;CC(I(2~ZM!m1WeeNBO<Mxs!itGP}pta-c<__5OOV>L^`jUI1f3gCn~Uv0e$8}h5BdOwN;@8f0R5-(gp9Ko4-vC!wGW1_IOj*r>88eb9u?$y=K+ScmYCco29T~(MIfQ*N@2AQq~Pc>Xnh7c=KA*7N981w0p*_S^sZ;E++JTmP+7KeHk6`vcGd$`p5drhkL>erBB6}@=h5vBQa=yBfoEWDcvdi6eCakmw(GwRofc@lef7xd!&NtA23!D9cNpcn7i_eiOGdc}K|DDPA`Ozpq#OYGfS(2MsmQHp0Xp}%UIwe+aO-sJ@>-rGdkBqjCNO2h46CNZBT`afG$YEtE^?O)F6%Q-CG14Sw3H<13SH1w+_<=*Dx{EjHaJcu~d{U21(i}y-VwyD}1RpqlPdhz}#O0~aoRpqZ#^x}D0l;x@cq~56g8x_5H?iJ+-ReQDlzmrnOuXw%}<t9~owfsM+=rirJ&m{k^DthrAEy`|Hz^nbaLq#v%w?(Ozryf7O65F3D=GT(@_8F|USKWWdCAMEx(2MuA)`Il<s_F4PFIz#M{J#hs!41n+(FwiQa+}oigKal+_;ci6Qqd>gJNS&07-wpFacKF3pr9A;nd3SA+I6WECKY{-hRIh?fC+kw3ZHJCH_eolBy;*rJdfZoDwKxjj}Z#pmB+d1to(OXr8<7bWT5}et*kVDPX7L1q-#dA"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    points = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        points[i] = (x, y)
    ans = 0
    points.sort(reverse=True)
    topright = points[0][0] + points[0][1]
    bottomright = points[0][0] - points[0][1]
    for i in range(N):
        tr = points[i][0] + points[i][1]
        br = points[i][0] - points[i][1]
        ans = max([ans, abs(topright - tr), abs(bottomright - br)])
        topright = max(topright, tr)
        bottomright = max(bottomright, br)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
  p, q = [int(j) for j in input().split(' ')]
  a[i] = p+q
  b[i] = p-q

a.sort()
b.sort()
print(max(a[-1] - a[0], b[-1] - b[0]))

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline


MOD = 10**9 + 7



def solve():
    N = int(input())
    point = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    pa = max(point,key = lambda x: x[0] + x[1])
    pb = min(point,key = lambda x: x[0] + x[1])
    pc = max(point,key = lambda x: x[0] - x[1])
    pd = min(point,key = lambda x: x[0] - x[1])
    r1 = pa[0] + pa[1] - pb[0] - pb[1]
    r2 = pc[0] - pc[1] + pd[1] - pd[0]
    print(max(r1,r2))
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
z = []
w = []
for i in range(n):
    x,y = map(int,input().split())
    z.append(x+y)
    w.append(x-y)
zmax = max(z)-min(z)
wmax = max(w)-min(w)
print(max(zmax,wmax))

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    n = int(input())

    ls = []
    for i in range(n):
        p = list(map(int, input().split()))
        np = (p[0] + p[1], p[0] - p[1])
        ls.append(np)

    minx = float("inf")
    miny = float("inf")
    maxx = -float("inf")
    maxy = -float("inf")

    for i in range(len(ls)):
        x, y = ls[i]
        minx = min(minx, x)
        miny = min(miny, y)
        maxx = max(maxx, x)
        maxy = max(maxy, y)

    print(max(maxx - minx, maxy - miny))


main()

Submission status: Accepted

Solution code:
n = int(input())
p = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y])
q = []
r = []
for i in range(n):
    q.append(p[i][0]+p[i][1])
    r.append(p[i][0]-p[i][1])
q.sort()
r.sort()
ans = max(abs(q[-1]-q[0]),abs(r[-1]-r[0]))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int, input().split())) for i in range(n)]
z=list(map(lambda x: x[0]+x[1], xy))
w=list(map(lambda x: x[0]-x[1], xy))
print(max(max(z)-min(z), max(w)-min(w)))

Submission status: Accepted

Solution code:
n = int(input())

points = []

for i in range(n) :
    point = list(map(int, input().split(" ")))
    points.append(point)

z = []
w = []

for i in range(len(points)) :
    z.append(points[i][0] + points[i][1])

for i in range(len(points)) :
    w.append(points[i][0] - points[i][1])

max_z = max(z) - min(z)
max_w = max(w) - min(w)

if max_z > max_w :
    print(max_z)
else :
    print(max_w)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    x, y = map(int, input().split())
    a1 = x + y
    a2 = x + y
    b1 = y - x
    b2 = y - x
    N -= 1
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b

# from numba import njit
# @njit('(i8,i8,i8[:])',cache=True)


N = a_int()
XY = read_matrix(N, 2)
X = XY[:, 0]
Y = XY[:, 1]
f0 = X - Y
f1 = X + Y

print(max(f0.max() - f0.min(), f1.max() - f1.min()))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())

x = []
y = []
xy1 = []
xy2 = []

for i in range(N):
    a, b = (int(t) for t in input().split())
    x.append(a)
    y.append(b)
    xy1.append(a + b)
    xy2.append(a - b)

max1 = max(xy1) - min(xy1)
max2 = max(xy2) - min(xy2)
print(max((max1, max2)))

Submission status: Accepted

Solution code:
N=int(input())
xx=[]
yy=[]
for i in range(N):
  x,y=map(int,input().split())
  xx.append(x+y)
  yy.append(x-y)
xx.sort()
yy.sort()
print(max(xx[-1]-xx[0],yy[-1]-yy[0]))

Submission status: Accepted

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


def get_points_and_convert(pts):
    x, y = pts
    return x + y, x - y


def main():
    n = int(input())
    points = [
        get_points_and_convert(map(int, input().split()))
        for _ in range(n)
    ]
    plus_coords, minus_coords = list(zip(*points))
    plus_dist = max(plus_coords) - min(plus_coords)
    minus_dist = max(minus_coords) - min(minus_coords)
    print(max(plus_dist, minus_dist))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
l0 = [[int(i) for i in input().split()] for _ in range(N)]
l1 = [0] * N
l2 = [0] * N
for cnt, val in enumerate(l0):
    l1[cnt] = val[0] + val[1]
    l2[cnt] = val[0] - val[1]
l1.sort()
l2.sort()
print(max(l1[-1] - l1[0], l2[-1] - l2[0]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    pt = []
    for _ in range(n):
        x,y = map(int,input().split())
        pt.append([x,y])
    a,b,c = [],[],[]
    for p in pt:
        a.append(p[0]+p[1])
        b.append(p[0]-p[1])
        c.append(p[1]-p[0])
    ans = 0
    if max(a)-min(a)>ans:
        ans = max(a)-min(a)
    if max(b)-min(b)>ans:
        ans = max(b)-min(b)
    if max(c)-min(c)>ans:
        ans = max(c)-min(c)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

L1 = [0]*N
L2 = [0]*N
for i in range(N):
    L1[i] = L[i][0]+L[i][1]
    L2[i] = L[i][0]-L[i][1]

L1.sort()
L2.sort()
print(max(L1[-1]-L1[0], L2[-1]-L2[0]))

Submission status: Accepted

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

ans = a[-1]-a[0]
c = b[-1]-b[0]
print (max(ans,c))

Submission status: Accepted

Solution code:
def manhattan(n, x, y):
    x2 = [0] * n
    y2 = [0] * n
    for i in range(n):
        x2[i] = x[i] - y[i]
        y2[i] = x[i] + y[i]
    print(max(max(x2) - min(x2), max(y2) - min(y2)))

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

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
from functools import reduce
def main():
    N = I()
    Dots = defaultdict()
    xpyp = []
    xpyn = []
    xnyp = []
    xnyn = []
    for i in range(N):
        x, y = MI()
        Dots[i] = (x, y)
        xpyp.append(x + y)
        xpyn.append(x - y)
        xnyp.append(- x + y)
        xnyn.append(- x - y)
    xpyp_max = max(xpyp) - min(xpyp)
    xpyn_max = max(xpyn) - min(xpyn)
    xnyp_max = max(xnyp) - min(xnyp)
    xnyn_max = max(xnyn) - min(xnyn)
    print(max(xpyp_max, xpyn_max, xnyp_max, xnyn_max))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
a=10**9
z_max=-1*a
z_min=a
w_max=-1*a
w_min=a
for x,y in l: #点のx座標とy座標の和の最大値と最小値の差か座標の差の最大値と最小値の差が答え
  z_max=max(z_max,x+y)
  z_min=min(z_min,x+y)
  w_max=max(w_max,x-y)
  w_min=min(w_min,x-y)
print(max(z_max-z_min,w_max-w_min))

Submission status: Accepted

Solution code:
n = int(input())

xy = []
for index in range(n):
  x, y = map(int, input().split())
  xy.append([x, y])

pos_max = xy[0][0]+xy[0][1]
pos_min = xy[0][0]+xy[0][1]
neg_max = xy[0][0]-xy[0][1]
neg_min = xy[0][0]-xy[0][1]
for item in xy:
  pos_v = item[0] + item[1]
  neg_v = item[0] - item[1]
  pos_max = pos_v if pos_v > pos_max else pos_max
  pos_min = pos_v if pos_v < pos_min else pos_min
  neg_max = neg_v if neg_v > neg_max else neg_max
  neg_min = neg_v if neg_v < neg_min else neg_min

pos_result = pos_max - pos_min
neg_result = neg_max - neg_min
print(pos_result if pos_result >= neg_result else neg_result)

Submission status: Accepted

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

th = pow(10, 9)
z_max = -th
z_min = th
w_max = -th
w_min = th

for x, y in xy_array:
    z_max = max(x + y, z_max)
    z_min = min(x + y, z_min)
    w_max = max(x - y, w_max)
    w_min = min(x - y, w_min)

ans = max(z_max - z_min, w_max - w_min)
print(ans)

Submission status: Accepted

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

th = pow(10, 9)
right_up_max = -th
left_down_min = th
left_up_max = -th
right_down_min = th

for x, y in xy_array:
    right_up_max = max(x + y, right_up_max)
    left_down_min = min(x + y, left_down_min)
    left_up_max = max(x - y, left_up_max)
    right_down_min = min(x - y, right_down_min)

ans = max(right_up_max - left_down_min, left_up_max - right_down_min)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lis = []
d1 = []
d2 = []
for i in range(N):
    x,y = map(int,input().split())
    lis.append([x,y])
    d1.append(x-y)
    d2.append(x+y)
ans = max(d1) - min(d1)
ans = max(ans,max(d2) - min(d2))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [[] for i in range(4)]
for i in range(n):
    x, y = map(int, input().split())
    l[0].append(x+y)
    l[1].append(x-y)
    l[2].append(-x+y)
    l[3].append(-x-y)
for i in range(4):
    l[i].sort()
ans = 0
for i in range(4):
    ans = max(ans, l[i][-1] - l[i][0])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x + y)
        Y.append(x - y)
    X.sort()
    Y.sort()
    print(max(X[-1] - X[0], Y[-1] - Y[0]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a,b = [], []
for i in range(N):
  x,y = map(int, input().split())
  a.append(x-y)
  b.append(x+y)
a.sort()
b.sort()
ans = max(a[-1] - a[0], b[-1] - b[0])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
j=k=0
def s(a):
    return a[0]+a[1]
def ss(a):
    return a[0]-a[1]
for i in range(n):
    f=list(map(int,input().split()))
    a.append(f)
aa=min(map(s,a))
b=max(map(s,a))
c=min(map(ss,a))
d=max(map(ss,a))
print(max(abs(d-c),abs(b-aa)))

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.buffer.readline())
z, w = [0]*n, [0]*n
for i, a in enumerate(sys.stdin.buffer.readlines()):
    x, y = map(int, a.split())
    z[i] = x+y
    w[i] = x-y
print(max(abs(max(z)-min(z)), abs(max(w)-min(w))))

Submission status: Accepted

Solution code:
N = int(input())
XY = [[int(_) for _ in input().split()] for _ in range(N)]
ans = -1
for dx, dy in ((1, 1), (-1, 1), (-1, -1), (1, -1)):
    xy2 = [x * dx + y * dy for x, y in XY]
    ans = max(ans, max(xy2) - min(xy2))
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

N = int(input())
V = set()
for s in sys.stdin.readlines():
    x, y = map(int, s.split())
    V.add((x + y, x - y))

y_max = max(V, key=itemgetter(1))[1]
y_min = min(V, key=itemgetter(1))[1]
x_max = max(V, key=itemgetter(0))[0]
x_min = min(V, key=itemgetter(0))[0]

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

Submission status: Accepted

Solution code:
import numpy as np

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

xy45 = [[xy[i][0] - xy[i][1], xy[i][0] + xy[i][1]] for i in range(N)]
xy45 = np.array(xy45)

print(max(max(xy45[:, 0]) - min(xy45[:, 0]), max(xy45[:, 1]) - min(xy45[:, 1])))

Submission status: Accepted

Solution code:
import numpy as np
def solve(n, x, y):
    x = np.asarray(x)
    y = np.asarray(y)
    z = x + y
    w = x - y
    return max(np.max(z) - np.min(z), np.max(w) - np.min(w))

n = int(input())
x, y = zip(*[map(int, input().split()) for i in range(n)])
print(solve(n, x, y))

Submission status: Accepted

Solution code:
def solve(n, x, y):
    z = [u + v for u, v in zip(x, y)]
    w = [u - v for u, v in zip(x, y)]
    return max([max(z) - min(z), max(w) - min(w)])

n = int(input())
x, y = zip(*[map(int, input().split()) for i in range(n)])
print(solve(n, x, y))

Submission status: Accepted

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

hoge = [sum(a) for a in A]
fuga = [a[0] - a[1] for a in A]
print(max(max(hoge) - min(hoge), max(fuga) - min(fuga)))

Submission status: Accepted

Solution code:
def get_ints():
    return list(map(int,input().split()))

n = int(input())
a, b = [], []
for i in range(n):
    x, y = get_ints()
    a.append(x-y)
    b.append(x+y)

a.sort()
b.sort()
ans = max(a[-1] - a[0], b[-1] - b[0])
print(ans)

Submission status: Accepted

Solution code:
def get_ints():
  return list(map(int,input().split()))

n = int(input())
a,b = [],[]
for i in range(n):
  x,y = get_ints()
  a.append(x+y)
  b.append(x-y)

a.sort()
b.sort()
ans = max(a[-1]-a[0], b[-1]-b[0])
print(ans)

Submission status: Accepted

Solution code:
import sys


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


N = int(input())

plus = []
minus = []
for _ in range(N):
    x, y = map(int, input().split())
    plus.append(x+y)
    minus.append(x-y)

print(max(max(plus)-min(plus), max(minus)-min(minus)))