AtCoder Beginner Contest 178 E - Dist Max【Python】
https://atcoder.jp/contests/abc178/tasks/abc178_e
AtCoder ProblemsでDifficulty: 1054、Solve Probability: 18%でした。
解けませんでした。
下記の記事の解説がわかりやすかったです。
愚直に2点の距離を求めようとすると2重ループになるため1重ループで済むように式変形をする。
絶対値をmaxで分解するとmax((xi + yi) + (-xj - yj), ...)のようにiとjごとに分けられる。
各要素(xi + yi), (-xj - yj)....が最大なら全体も最大となる。
各要素(xi + yi), (-xj - yj)....を(x + y), (-x - y)....として一重ループで要素ごとの最大値を求めて変形した式に代入。
N = int(input()) XY = [] for i in range(N): XY.append(list(map(int, input().split()))) # x + y a = 0 # -x - y b = 0 # -x + y c = 0 # x - y d = 0 for i in range(N): x, y = XY[i] a = max(a, x + y) b = max(b, -x - y) c = max(c, -x + y) d = max(d, x - y) print(max(a + b, d + c, c + d, b + a))