Problem:


歩くサンタクロース(Walking Santa)  

昨年末，サンタクロースはJOI 村の子供たちにクリスマスプレゼントを渡すのを忘れてしまった．そこで，お詫びの気持ちとして子供たちにチョコレートケーキを届けることにした．届けるべき日は明日に迫っているので，そろそろ移動計画を考えなければならない．

JOI 村は，南北方向にまっすぐに伸びるW 本の道路と，東西方向にまっすぐに伸びるH 本の道路により，碁盤の目の形に区分けされている. 南北方向のW 本の道路には，西から順に1, 2, ... , W の番号が付けられており，東西方向のH 本の道路には，南から順に1, 2, ... , H の番号が付けられている. 西からx 番目の南北方向の道路と，南からy 番目の東西方向の道路が交わる交差点を(x, y) で表す. JOI 村にはN 軒の家があり，それらはいずれかの交差点に位置している. サンタクロースは道路に沿ってのみ移動することができる. 隣り合う交差点の間を移動するのにかかる時間を1 とする.

JOI 村のすべての家には子供がいるので，サンタクロースはJOI 村のすべての家に1 個ずつチョコレートケーキを届けてまわらなければならない. 大切なチョコレートケーキを持ってトナカイと空を飛びまわるのはやや危険であるので，サンタクロースとトナカイはJOI 村のいずれかの交差点に降り立ち，サンタクロースがそこから歩いてチョコレートケーキを届けることにした. サンタクロースは同時に2 個以上のチョコレートケーキを運んで歩くことはしない．つまり，サンタクロースはチョコレートケーキを1 軒の家に届けるたびに降り立った交差点に戻る．

サンタクロースは，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間が最小になるような移動計画を選ぶことにした．ここで，最後の家にチョコレートケーキを届けてから降り立った交差点に戻るまでの時間は所要時間に含めないことに注意せよ．また，移動にかかる時間以外は考えない．

課題

家の位置の情報が与えられたとき，サンタクロースが降り立つ交差点をうまく選んだ場合の，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間の最小値と，所要時間を最小にするために降り立つべき交差点の位置を求めるプログラムを作成せよ．

制限

1 ≤ W ≤ 1000000000 = 109    南北方向に伸びる道路の本数

1 ≤ H ≤ 1000000000 = 109    東西方向に伸びる道路の本数

1 ≤ N ≤ 100000 = 105    家の数

1 ≤ Xi ≤ W    i 番目の家の位置の, 南北方向に伸びる道路の番号

1 ≤ Yi ≤ H    i 番目の家の位置の, 東西方向に伸びる道路の番号

入力

標準入力から以下の入力を読み込め．

 1 行目には各方向の道路の本数を表す整数 W, H が空白を区切りとして書かれている．

 2 行目には家の数を表す整数N が書かれている．

 続くN 行には，家の位置の情報が書かれている．i + 2 行目(1 ≤ i ≤ N) には整数Xi, Yi が空白を区切りとして書かれており，i 番目の家が交差点(Xi, Yi) に位置していることを表す．これらN 個の交差点はすべて異なる．

出力

標準出力に以下のデータを出力せよ．

 1 行目には所要時間の最小値を表す1 つの整数が書かれていなければならない．

 2 行目には所要時間を最小にするために降り立つべき交差点が(x, y) であるとき，2 つの整数x, y がこの順に空白を区切りとして書かれていなければならない．適切な交差点が複数ある場合は，そのうち最も西にある(つまり，x の値が小さい) 交差点を, それでも1 つに定まらない場合は, さらにそのうちで最も南にある(つまり，y の値が小さい) 交差点を選べ.

注意

この問題では，扱う整数の範囲が32 ビットに収まらない可能性があることに注意せよ．

採点基準

採点用データのうち，配点の40%分については，N ≤ 1000 を満たす．

採点用データのうち，配点の10%分については，W ≤ 50, H ≤ 50, N ≤ 1000 を満たす．

入出力の例

入力例1
  

  

5 4
3
1 1
3 4
5 3

出力例1
  

10
3 3

たとえば，次のような移動計画により所要時間を最小にできる．

 交差点(3; 3) に降り立つ．

 交差点(3; 4) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は1 である．

 交差点(3; 3) に戻る．ここまでの経過時間は2 である．

 交差点(5; 3) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は4 である．

 交差点(3; 3) に戻る．ここまでの経過時間は6 である．

 交差点(1; 1) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は10 である．

入力例2
  

  

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

出力例2
  

21
2 3

家がある交差点に降り立ってもよいことに注意せよ．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 4
3
1 1
3 4
5 3


Sample output:
10
3 3

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20
w, h = map(int, input().split())
n = int(input())
xlst = []
ylst = []
for i in range(n):
  x, y = map(int,input().split())
  xlst.append(x)
  ylst.append(y)

sorted_xlst = sorted(xlst)
sorted_ylst = sorted(ylst)
accx = accy = 0
cum_sum_xlst = []
cum_sum_ylst = []

for i in range(n):
  accx += sorted_xlst[i]
  accy += sorted_ylst[i]
  cum_sum_xlst.append(accx)
  cum_sum_ylst.append(accy)


sx = accx
sy = accy

num = n * 2 - 1

ans = INF
ansx = 10 ** 10
ansy = 10 ** 10

for i in range(n):
  xi = xlst[i]
  yi = ylst[i]
  
  sumx = sx * 2 - xi
  avx1 = sumx // num
  avx2 = avx1 + 1
  
  sumy = sy * 2 - yi
  avy1 = sumy // num
  avy2 = avy1 + 1
  
  px1 = bl(sorted_xlst, avx1)
  px2 = bl(sorted_xlst, avx2)

  lenx1 = (avx1 * px1 - cum_sum_xlst[px1 - 1]) * 2 + (sx - cum_sum_xlst[px1 - 1] - avx1 * (n - px1)) * 2 - abs(xi - avx1)
  lenx2 = (avx2 * px2 - cum_sum_xlst[px2 - 1]) * 2 + (sx - cum_sum_xlst[px2 - 1] - avx2 * (n - px2)) * 2 - abs(xi - avx2)

  py1 = bl(sorted_ylst, avy1)
  py2 = bl(sorted_ylst, avy2)
  
  leny1 = (avy1 * py1 - cum_sum_ylst[py1 - 1]) * 2 + (sy - cum_sum_ylst[py1 - 1] - avy1 * (n - py1)) * 2 - abs(yi - avy1)
  leny2 = (avy2 * py2 - cum_sum_ylst[py2 - 1]) * 2 + (sy - cum_sum_ylst[py2 - 1] - avy2 * (n - py2)) * 2 - abs(yi - avy2)

  if lenx1 <= lenx2:
    avx = avx1
  else:
    avx = avx2
  
  if leny1 <= leny2:
    avy = avy1
  else:
    avy = avy2

  lenx = min(lenx1, lenx2)
  leny = min(leny1, leny2)
  
  lent = lenx + leny
  
  if lent <= ans:
    ans = lent
    if lent == ans:
      if avx < ansx:
        ansx = avx
        ansy = avy
      elif avx == ansx:
        if avy < ansy:
          ansy = avy
    else:
      ansx = avx
      ansy = avy
print(ans)
print(ansx, ansy)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20
w, h = map(int, input().split())
n = int(input())
xlst = []
ylst = []
for i in range(n):
  x, y = map(int,input().split())
  xlst.append(x)
  ylst.append(y)

sorted_xlst = sorted(xlst)
sorted_ylst = sorted(ylst)
accx = accy = 0
cum_sum_xlst = []
cum_sum_ylst = []

for i in range(n):
  accx += sorted_xlst[i]
  accy += sorted_ylst[i]
  cum_sum_xlst.append(accx)
  cum_sum_ylst.append(accy)

#print(cum_sum_xlst)
#print(cum_sum_ylst)
sx = accx
sy = accy

num = n * 2 - 1

ans = INF
ansx = 10 ** 10
ansy = 10 ** 10

def make_lenx(avx, xi):
  px = bl(sorted_xlst, avx)
  if px: 
    lenx = (avx * px - cum_sum_xlst[px - 1]) * 2 + (sx - cum_sum_xlst[px - 1] - avx * (n - px)) * 2 - abs(xi - avx)
  else:
    lenx = (sx - avx * n) * 2 - abs(xi - avx)
#  print("px:",px,"avx:",avx,"lenx:",lenx)
  return lenx
def make_leny(avy, yi):
  py = bl(sorted_ylst, avy)
  if py:
    leny = (avy * py - cum_sum_ylst[py - 1]) * 2 + (sy - cum_sum_ylst[py - 1] - avy * (n - py)) * 2 - abs(yi - avy)
  else:
    leny = (sy - avy * n) * 2 - abs(yi - avy)
#  print("py:",py,"avy:",avy,"leny:",leny)
  return leny

for i in range(n):
  xi = xlst[i]
  yi = ylst[i]
  
  sumx = sx * 2 - xi
  avx1 = sumx // num - 1
  avx2 = avx1 + 1
  avx3 = avx2 + 1

  sumy = sy * 2 - yi
  avy1 = sumy // num - 1
  avy2 = avy1 + 1
  avy3 = avy2 + 1
  
  lenx1, lenx2, lenx3 = make_lenx(avx1, xi), make_lenx(avx2, xi), make_lenx(avx3, xi)
  leny1, leny2, leny3 = make_leny(avy1, yi), make_leny(avy2, yi), make_leny(avy3, yi)

  lenx = min(lenx1, lenx2, lenx3)
  leny = min(leny1, leny2, leny3)
  
  if lenx == lenx1:
    avx = avx1
  elif lenx == lenx2:
    avx = avx2
  else:
    avx = avx3

  if leny == leny1:
    avy = avy1
  elif leny == leny2:
    avy = avy2
  else:
    avy = avy3


#  print(lenx, leny, avx, avy)
  lent = lenx + leny
  
  if lent <= ans:
    if lent == ans:
      if avx < ansx:
        ansx = avx
        ansy = avy
      elif avx == ansx:
        if avy < ansy:
          ansy = avy
    else:
      ansx = avx
      ansy = avy
    ans = lent
print(ans)
print(ansx, ansy)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
INF = 10 ** 20
w, h = map(int, input().split())
n = int(input())
xlst = []
ylst = []
for i in range(n):
  x, y = map(int,input().split())
  xlst.append(x)
  ylst.append(y)

sorted_xlst = sorted(xlst)
sorted_xlst_d = sorted(xlst * 2)
sorted_ylst = sorted(ylst)
sorted_ylst_d = sorted(ylst * 2)
accx = accy = 0
cum_sum_xlst = []
cum_sum_ylst = []

for i in range(n):
  accx += sorted_xlst[i]
  accy += sorted_ylst[i]
  cum_sum_xlst.append(accx)
  cum_sum_ylst.append(accy)

clx = sorted_xlst_d[n - 1]
crx = sorted_xlst_d[n]
cly = sorted_ylst_d[n - 1]
cry = sorted_ylst_d[n]

num = n * 2 - 1

ans = INF
ansx = 10 ** 10
ansy = 10 ** 10
for i in range(n):
  xi = xlst[i]
  yi = ylst[i]
  if xi <= clx:
    cx = crx
  else:
    cx = clx
  if yi <= cly:
    cy = cry
  else:
    cy = cly

  px = bl(sorted_xlst, cx)
  py = bl(sorted_ylst, cy)
 
  if px:
    xlen = (cx * px - cum_sum_xlst[px - 1]) * 2 + (accx - cum_sum_xlst[px - 1] - cx * (n - px)) * 2 - abs(xi - cx)
  else:
    xlen = (accx - cx * n) * 2 - abs(xi - cx)

  if py:
    ylen = (cy * py - cum_sum_ylst[py - 1]) * 2 + (accy - cum_sum_ylst[py - 1] - cy * (n - py)) * 2 - abs(yi - cy)
  else:
    ylen = (accy - cy * n) * 2 - abs(yi - cy)
  
  tlen = xlen + ylen
  if ans > tlen:
    ans = tlen
    ansx = cx
    ansy = cy
  elif ans == tlen:
    if ansx > cx:
      ansx = cx
      ansy = cy
    elif ansx == cx:
      if ansy > cy:
        ansy = cy 
print(ans)
print(ansx, ansy)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  
  for i in range(n):
    x, y = map(int,input().split())
    xlst.append(x)
    ylst.append(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)
  accx = accy = 0
  cum_sum_xlst = []
  cum_sum_ylst = []
  
  for i in range(n):
    accx += sorted_xlst[i]
    accy += sorted_ylst[i]
    cum_sum_xlst.append(accx)
    cum_sum_ylst.append(accy)
  
  if n % 2:
    clx = crx = sorted_xlst[n // 2]
    cly = cry = sorted_ylst[n // 2]
  else:
    clx = sorted_xlst[n // 2 - 1]
    crx = sorted_xlst[n // 2]
    cly = sorted_ylst[n // 2 - 1]
    cry = sorted_ylst[n // 2]
  
  ans = ansx = ansy = INF
  
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    if xi <= clx:
      cx = crx
    else:
      cx = clx

    if yi <= cly:
      cy = cry
    else:
      cy = cly
  
    px = bl(sorted_xlst, cx)
    py = bl(sorted_ylst, cy)
   
    if px:
      csx = cum_sum_xlst[px - 1]
      xlen = (cx * px - csx) * 2 + (accx - csx - cx * (n - px)) * 2 - abs(xi - cx)
    else:
      xlen = (accx - cx * n) * 2 - abs(xi - cx)
  
    if py:
      csy = cum_sum_ylst[py - 1]
      ylen = (cy * py - csy) * 2 + (accy - csy - cy * (n - py)) * 2 - abs(yi - cy)
    else:
      ylen = (accy - cy * n) * 2 - abs(yi - cy)
    
    tlen = xlen + ylen

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  appx = xlst.append
  appy = ylst.append
  for i in range(n):
    x, y = map(int,input().split())
    appx(x)
    appy(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)
  accx = accy = 0
  cum_sum_xlst = []
  cum_sum_ylst = []
  appx = cum_sum_xlst.append
  appy = cum_sum_ylst.append

  for i in range(n):
    accx += sorted_xlst[i]
    accy += sorted_ylst[i]
    appx(accx)
    appy(accy)
  
  if n % 2:
    clx = crx = sorted_xlst[n // 2]
    cly = cry = sorted_ylst[n // 2]
  else:
    clx = sorted_xlst[n // 2 - 1]
    crx = sorted_xlst[n // 2]
    cly = sorted_ylst[n // 2 - 1]
    cry = sorted_ylst[n // 2]
  
  ans = ansx = ansy = INF
  
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    if xi <= clx:
      cx = crx
    else:
      cx = clx

    if yi <= cly:
      cy = cry
    else:
      cy = cly
  
    px = bl(sorted_xlst, cx)
    py = bl(sorted_ylst, cy)

    dx = xi - cx
    if dx < 0:
      dx = -dx

    if px:
      csx = cum_sum_xlst[px - 1]
      xlen = (accx - csx * 2 - cx * (n - px * 2)) * 2 - dx
    else:
      xlen = (accx - cx * n) * 2 - dx
 
    dy = yi - cy
    if dy < 0:
      dy = -dy
   
    if py:
      csy = cum_sum_ylst[py - 1]
      ylen = (accy - csy * 2 - cy * (n - py * 2)) * 2 - dy
    else:
      ylen = (accy - cy * n) * 2 - dy
    
    tlen = xlen + ylen

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  appx = xlst.append
  appy = ylst.append
  for i in range(n):
    x, y = map(int,input().split())
    appx(x)
    appy(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)
  accx = accy = 0
  cum_sum_xlst = []
  cum_sum_ylst = []
  appx = cum_sum_xlst.append
  appy = cum_sum_ylst.append

  for i in range(n):
    accx += sorted_xlst[i]
    accy += sorted_ylst[i]
    appx(accx)
    appy(accy)
  
  if n % 2:
    clx = crx = sorted_xlst[n // 2]
    cly = cry = sorted_ylst[n // 2]
  else:
    clx = sorted_xlst[n // 2 - 1]
    crx = sorted_xlst[n // 2]
    cly = sorted_ylst[n // 2 - 1]
    cry = sorted_ylst[n // 2]
  plx = bl(sorted_xlst, clx)
  prx = bl(sorted_xlst, crx)
  ply = bl(sorted_ylst, cly)
  pry = bl(sorted_ylst, cry)


  
  ans = ansx = ansy = INF
  
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    if xi <= clx:
      cx = crx
      px = prx
    else:
      cx = clx
      px = plx
    if yi <= cly:
      cy = cry
      py = pry
    else:
      cy = cly
      py = ply
  
    dx = xi - cx
    if dx < 0:
      dx = -dx

    if px:
      csx = cum_sum_xlst[px - 1]
      xlen = (accx - csx * 2 - cx * (n - px * 2)) * 2 - dx
    else:
      xlen = (accx - cx * n) * 2 - dx
 
    dy = yi - cy
    if dy < 0:
      dy = -dy
   
    if py:
      csy = cum_sum_ylst[py - 1]
      ylen = (accy - csy * 2 - cy * (n - py * 2)) * 2 - dy
    else:
      ylen = (accy - cy * n) * 2 - dy
    
    tlen = xlen + ylen

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  appx = xlst.append
  appy = ylst.append
  for i in range(n):
    x, y = map(int,input().split())
    appx(x)
    appy(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)
  accx = accy = 0
  cum_sum_xlst = []
  cum_sum_ylst = []
  appx = cum_sum_xlst.append
  appy = cum_sum_ylst.append

  for i in range(n):
    accx += sorted_xlst[i]
    accy += sorted_ylst[i]
    appx(accx)
    appy(accy)
  
  if n % 2:
    clx = crx = sorted_xlst[n // 2]
    cly = cry = sorted_ylst[n // 2]
  else:
    clx = sorted_xlst[n // 2 - 1]
    crx = sorted_xlst[n // 2]
    cly = sorted_ylst[n // 2 - 1]
    cry = sorted_ylst[n // 2]
  plx = bl(sorted_xlst, clx)
  prx = bl(sorted_xlst, crx)
  ply = bl(sorted_ylst, cly)
  pry = bl(sorted_ylst, cry)

  xllen = (accx - cum_sum_xlst[plx - 1] * 2 - clx * (n - plx * 2)) * 2 if plx != 0 else (accx - clx * n) * 2
  xrlen = (accx - cum_sum_xlst[prx - 1] * 2 - crx * (n - prx * 2)) * 2 if prx != 0 else (accx - crx * n) * 2
  yllen = (accy - cum_sum_ylst[ply - 1] * 2 - cly * (n - ply * 2)) * 2 if ply != 0 else (accy - cly * n) * 2
  yrlen = (accy - cum_sum_ylst[pry - 1] * 2 - cry * (n - pry * 2)) * 2 if pry != 0 else (accy - cry * n) * 2


  ans = ansx = ansy = INF
  max_sumd = 0
  
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    if xi <= clx:
      cx = crx
      xlen = xrlen
    else:
      cx = clx
      xlen = xllen
    if yi <= cly:
      cy = cry
      ylen = yrlen
    else:
      cy = cly
      ylen = yllen
  
    dx = xi - cx
    if dx < 0:
      dx = -dx

    dy = yi - cy
    if dy < 0:
      dy = -dy

    if max_sumd > dx + dy:
      continue
    else:
      max_sumd = dx + dy
    
    tlen = xlen + ylen - max_sumd

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  appx = xlst.append
  appy = ylst.append

  for i in range(n):
    x, y = map(int,input().split())
    appx(x)
    appy(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)

  clx = sorted_xlst[n // 2 if n % 2 else n // 2 - 1]
  crx = sorted_xlst[n // 2]
  cly = sorted_ylst[n // 2 if n % 2 else n // 2 - 1]
  cry = sorted_ylst[n // 2]
 
  plx = bl(sorted_xlst, clx)
  prx = bl(sorted_xlst, crx)
  ply = bl(sorted_ylst, cly)
  pry = bl(sorted_ylst, cry)

  sumx = sum(xlst)
  sumy = sum(ylst)

  xllen = (sumx - sum(sorted_xlst[:plx]) * 2 - clx * (n - plx * 2)) * 2
  xrlen = (sumx - sum(sorted_xlst[:prx]) * 2 - crx * (n - prx * 2)) * 2
  yllen = (sumy - sum(sorted_ylst[:ply]) * 2 - cly * (n - ply * 2)) * 2
  yrlen = (sumy - sum(sorted_ylst[:pry]) * 2 - cry * (n - pry * 2)) * 2

  ans = ansx = ansy = INF
  max_sumd = 0
  
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    if xi <= clx:
      cx = crx
      xlen = xrlen
    else:
      cx = clx
      xlen = xllen
    if yi <= cly:
      cy = cry
      ylen = yrlen
    else:
      cy = cly
      ylen = yllen
  
    dx = xi - cx
    if dx < 0:
      dx = -dx
    dy = yi - cy
    if dy < 0:
      dy = -dy

    if max_sumd > dx + dy:
      continue
    else:
      max_sumd = dx + dy
    
    tlen = xlen + ylen - max_sumd

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def main():
  
  w, h = map(int, input().split())
  n = int(input())
  
  xlst = []
  ylst = []
  appx = xlst.append
  appy = ylst.append

  for i in range(n):
    x, y = map(int,input().split())
    appx(x)
    appy(y)
  
  sorted_xlst = sorted(xlst)
  sorted_ylst = sorted(ylst)

  #x, yの中央値の候補
  clx = sorted_xlst[n // 2 if n % 2 else n // 2 - 1]
  crx = sorted_xlst[n // 2]
  cly = sorted_ylst[n // 2 if n % 2 else n // 2 - 1]
  cry = sorted_ylst[n // 2]

  #x, yの中央値の候補のindex
  ilx = bl(sorted_xlst, clx)
  irx = bl(sorted_xlst, crx)
  ily = bl(sorted_ylst, cly)
  iry = bl(sorted_ylst, cry)

  sumx = sum(xlst)
  sumy = sum(ylst)

  #x, yそれぞれについての中央値と各点までの往復距離の総和
  xllen = (sumx - sum(sorted_xlst[:ilx]) * 2 - clx * (n - ilx * 2)) * 2
  xrlen = (sumx - sum(sorted_xlst[:irx]) * 2 - crx * (n - irx * 2)) * 2
  yllen = (sumy - sum(sorted_ylst[:ily]) * 2 - cly * (n - ily * 2)) * 2
  yrlen = (sumy - sum(sorted_ylst[:iry]) * 2 - cry * (n - iry * 2)) * 2

  ans = ansx = ansy = INF
  max_sumd = 0
  
  #各点について復路を省いた場合の距離の和を求める
  for i in range(n):
    xi = xlst[i]
    yi = ylst[i]

    cx, xlen = (crx, xrlen) if xi <= clx else (clx, xllen)
    cy, ylen = (cry, yrlen) if yi <= cly else (cly, yllen)

    dx = xi - cx if xi >= cx else cx - xi
    dy = yi - cy if yi >= cy else cy - yi

    if max_sumd > dx + dy:
      continue
    else:
      max_sumd = dx + dy
    
    tlen = xlen + ylen - max_sumd

    if ans > tlen:
      ans = tlen
      ansx = cx
      ansy = cy
    elif ans == tlen:
      if ansx > cx:
        ansx = cx
        ansy = cy
      elif ansx == cx:
        if ansy > cy:
          ansy = cy 
  
  print(ans)
  print(ansx, ansy)

main()

Submission status: Runtime Error

Solution code:
import numpy

def cal_time(W, H, x, y):
    return 2*(abs(W-x) + abs(H-y))

geo = input("Input W H: ").split()
W = int(geo[0])
H = int(geo[1])

if W<1 or W>1000000000:
    print("wrong W")
    exit()
if H<1 or H>1000000000:
    print("wrong H")
    exit()

N = int(input("N: "))
if N<1 or N>100000:
    print("wrong N")
    exit()

total_time = 0

''' Input houses and calculate time'''
houses = []
x_list = []
y_list = []
for i in range(N):
    co = input("x y: ").split()
    x = int(co[0])
    if x<1 or x>W:
        print("wrong x")
        exit()
    x_list.append(x)
    y = int(co[1])
    if y<1 or y>H:
        print("wrong y")
        exit()
    y_list.append(y)
    if (x,y) in houses:
        print("Coordinate exists")
        exit()
    houses.append((x,y))
    #total_time += cal_time(W, H, x, y)


avg_x = numpy.mean(x_list)
avg_y = numpy.mean(y_list)

# round
target_x = int(round(avg_x))
target_y = int(round(avg_y))

#print(target_x)
#print(target_y)

all_time = []
for co in houses:
    #print(co)
    time = cal_time(target_x, target_y, co[0], co[1])
    #print(time)
    all_time.append(time)
    total_time += time

total_time -= int(max(all_time)/2)
print(total_time)
print(target_x, target_y)

Submission status: Runtime Error

Solution code:
import numpy

def cal_time(W, H, x, y):
    return 2*(abs(W-x) + abs(H-y))

geo = input().split()
W = int(geo[0])
H = int(geo[1])

if W<1 or W>1000000000:
    print("wrong W")
    exit()
if H<1 or H>1000000000:
    print("wrong H")
    exit()

N = int(input())
if N<1 or N>100000:
    print("wrong N")
    exit()

total_time = 0

''' Input houses and calculate time'''
houses = []
x_list = []
y_list = []
for i in range(N):
    co = input("x y: ").split()
    x = int(co[0])
    if x<1 or x>W:
        print("wrong x")
        exit()
    x_list.append(x)
    y = int(co[1])
    if y<1 or y>H:
        print("wrong y")
        exit()
    y_list.append(y)
    if (x,y) in houses:
        print("Coordinate exists")
        exit()
    houses.append((x,y))
    #total_time += cal_time(W, H, x, y)


avg_x = numpy.mean(x_list)
avg_y = numpy.mean(y_list)

# round
target_x = int(round(avg_x))
target_y = int(round(avg_y))

#print(target_x)
#print(target_y)

all_time = []
for co in houses:
    #print(co)
    time = cal_time(target_x, target_y, co[0], co[1])
    #print(time)
    all_time.append(time)
    total_time += time

total_time -= int(max(all_time)/2)
print(total_time)
print(target_x, target_y)

Submission status: Runtime Error

Solution code:
import numpy

def cal_time(W, H, x, y):
    return 2*(abs(W-x) + abs(H-y))

geo = input().split()
W = int(geo[0])
H = int(geo[1])

if W<1 or W>1000000000:
    print("wrong W")
    exit()
if H<1 or H>1000000000:
    print("wrong H")
    exit()

N = int(input())
if N<1 or N>100000:
    print("wrong N")
    exit()

total_time = 0

''' Input houses and calculate time'''
houses = []
x_list = []
y_list = []
for i in range(N):
    co = input().split()
    x = int(co[0])
    if x<1 or x>W:
        print("wrong x")
        exit()
    x_list.append(x)
    y = int(co[1])
    if y<1 or y>H:
        print("wrong y")
        exit()
    y_list.append(y)
    if (x,y) in houses:
        print("Coordinate exists")
        exit()
    houses.append((x,y))
    #total_time += cal_time(W, H, x, y)


avg_x = numpy.mean(x_list)
avg_y = numpy.mean(y_list)

# round
target_x = int(round(avg_x))
target_y = int(round(avg_y))

#print(target_x)
#print(target_y)

all_time = []
for co in houses:
    #print(co)
    time = cal_time(target_x, target_y, co[0], co[1])
    #print(time)
    all_time.append(time)
    total_time += time

total_time -= int(max(all_time)/2)
print(total_time)
print(target_x, target_y)