Submission #11655276

---

Source Code Expand

#マンハッタン距離 |x| + |y| で 一番近いチェックポイント
#
#この問題では、xy格子上を縦、横に無駄なく歩いた場合の距離がマンハッタン距離。
#人がいる座標 (a, b) N 個、チェックポイントの座標 (c,d) M 個を 「リスト」 に格納。
#各人ごとに M 個 のチェックポイントをテストすることで、各人のマンハッタン距離が
#一番近いチェックポイントを求めることができる


INF = 1000000007

N, M = map(int, input().split())

ab = []

for i in range(N):
    ab.append([int(i) for i in input().split()])

cd = []

for i in range(M):
    cd.append([int(i) for i in input().split()])

for i in range(N):
    ans = 0
    dst = INF
    for j in range(M):
        tmp = abs(cd[j][0] - ab[i][0]) + abs(cd[j][1] - ab[i][1])

        if tmp < dst:
            # 0-indexed
            dst = tmp
            ans = j + 1

    print(ans)

Submission Info

Judge Result