問題
ポイント
「マンハッタン距離って何？」という方は下記記事が参考になります！
マンハッタン距離（Taxicab distance）／ユークリッド距離（Euclidean distance）
各工場から発電所へのマンハッタン距離を最小にすることが本問題のゴールですが、
マンハッタン距離の性質上、x軸とy軸を別々に考えることが可能なので、それぞれの軸上で
距離が最小になるような発電所の座標を考えていきます。
各軸上で考えるということは、直線上でN個の工場からの距離が最小になるような点を考えれば
良いので、この点は中央値となります。
※中央値と最短距離の関係については下記記事を参照
トタデータブログ [統計Day7] 中央値
中央値を求めるにはstatistics.median()が使えます。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
import statistics
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N = int(input())
X, Y = [], []
for _ in range(N):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
# x軸上、y軸上での中央値を求める これが発電所の座標となる
middle_x = statistics.median(X)
middle_y = statistics.median(Y)
# N個の工場から発電所までのマンハッタン距離の総和を計算する
ans = 0
for i in range(N):
ans += abs(middle_x - X[i])
ans += abs(middle_y - Y[i])
print(int(ans))
if __name__ == '__main__':
main()
