AtCoder Beginner Contest 178 E – Dist Max をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 178 E – Dist Max

マンハッタン距離の最大値に関する基礎問題。この方法を知ってるのと知らないとでは大きく違ってくる。

# AtCoder Beginner Contest 178 E - Dist Max
# https://atcoder.jp/contests/abc178/tasks/abc178_e
# tag: グリッド マンハッタン距離 最大距離 基礎問題

# 点 (x1, y1), (x2, y2) の距離は、x1 と x2, y1 と y2 の
# 大小関係から、次の 4 通りのうち最大のものになる。

# 1. (x1 - x2) + (y1 - y2)
# 2. (x2 - x1) + (y1 - y2)
# 3. (x1 - x2) + (y2 - y1)
# 4. (x2 - x1) + (y2 - y1)

# ところで、各 (x, y) の
# x + y = A, x - y = S とおいて上記の式を置き換えてみると、

# 1. (x1 + y1) - (x2 + y2) = A1 - A2
# 2. -(x1 - y1) + (x2 - y2) = S2 - S1
# 3. (x1 - y1) - (x2 - y2) = S1 - S2
# 4. -(x1 + y1) + (x2 + y2) = A2 - A1

# となるので、結局は A の差分 or S の差分、ということになる。

# つまり、各点ごとの x + y, x - y の値から距離を計算できる。
# これをあらかじめ計算し、それぞれの最大値から最小値を
# 引くことで、その差分の最大値を容易に計算可能。

# この値は、各点の座標軸に対して45度傾いた直線上への写像と捉える
# こともできる。これは、実際にグリッド上に x+y, x-y の値を
# 書き込んでいけば、すぐに分かると思う。

def main():
    N = int(input())
    points = [list(map(int, input().split())) for _ in range(N)]

    # x+y, x-y をリストに。
    rot1 = [x+y for x, y in points]
    rot2 = [x-y for x, y in points]

    # 最大値から最小値を引いたものを比較する。
    print(max(max(rot1)-min(rot1), max(rot2)-min(rot2)))

main()

abc178_e.py view raw

関連

コメントを残すコメントをキャンセル