Submission #36189038

---

Source Code Expand

n = int(input())
l = [map(int, input().split()) for _ in range(n)]
xl, yl = [list(i) for i in zip(*l)]

# 発電所が(a,b)にあったとすると、求める不便さFは
# F = abs(x[0]-a) + abs(y[0]-b) + ... + abs(x[n-1]-a) + abs(y[n-1]-b)
#   = (abs(x[0]-a) + ... + abs(x[n-1]-a)) + (abs(y[0]-b) + ... + abs(y[n-1]-b))
# つまり不便さFはxとyで独立に考える事ができる
# xによる不便さをFx, yによる不便さをFyとすることにする。

# xについて数直線を考えて、発電所がどこにあると良さげか考える。
# -------------------------->
# x1    x2    a     x3    x4
# aは端っこだと効率が悪そう…
# aが真ん中付近にあると効率が良さそう…
# 考察を進めると、aよりも左にあるx点はすべてaが右に動くと+1増える。
# aよりも右にあるx点はすべてaが右に動くと-1減る。
# つまり、aからみたときに、偶数点なら左と右にx点の数が同じだとよい。ついでに、ちょうど真ん中だとよい。
# 奇数点なら真ん中点そのままだと良さそう。
# つまり、aはxの中央値だと良さそう。
# xyは独立なので、bはyの中央値だと良い。
# よって、Fxはxの中央値からの各点の距離の総和、Fyはyの中央値からの各点の距離の総和になれば良い。

xl.sort()
yl.sort()

if n%2==0:
  x_median = (xl[n//2-1]+xl[n//2])/2
  y_median = (yl[n//2-1]+yl[n//2])/2
else:
  x_median = xl[n//2]
  y_median = yl[n//2]

f = 0
for i in range(n):
    f += abs(x_median-xl[i])+abs(y_median-yl[i])
  
print(int(f))

Submission Info

Judge Result