結果

問題 No.1998 Manhattan Restaurant
コンテスト
ユーザー googol_S0
提出日時 2022-07-01 22:13:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 398 ms / 2,000 ms
コード長 727 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 353 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 96,448 KB
最終ジャッジ日時 2024-11-26 05:23:19
合計ジャッジ時間 7,685 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
  X[i]=[X[i][0]+X[i][1],X[i][0]-X[i][1]]
L,R=0,10**13
while L<R:
  M=(L+R)>>1
  l1,l2,r1,r2=X[0][0],X[0][1],X[0][0],X[0][1]
  for i in range(N):
    l1=min(l1,X[i][0])
    l2=min(l2,X[i][1])
    r1=max(r1,X[i][0])
    r2=max(r2,X[i][1])
  C=0
  for i in range(N):
    if abs(l1-X[i][0])<=2*M and abs(l2-X[i][1])<=2*M:
      C+=1
    elif abs(r1-X[i][0])<=2*M and abs(r2-X[i][1])<=2*M:
      C+=1
  if C==N:
    R=M
    continue
  C=0
  for i in range(N):
    if abs(l1-X[i][0])<=2*M and abs(r2-X[i][1])<=2*M:
      C+=1
    elif abs(r1-X[i][0])<=2*M and abs(l2-X[i][1])<=2*M:
      C+=1
  if C==N:
    R=M
  else:
    L=max(L+1,M)
print(L)
0