ABC289 F問題 Teleporter Takahashi

問題設定を整理

点 $(x,y)$ を中心として、点 $(p,q)$ と対称な位置を $(r,s)$ とします。
すると、
$\frac{1}{2}\left( p+r \right) = x$
$\frac{1}{2}\left( q+s \right) = y$
より、
$r = 2x - p$
$s = 2y - q$
となります。この式から、 $p$ が偶数のとき $r$ は偶数、 $p$ が奇数のとき $r$ は奇数ということがわかります。 $s,q$ についても同じです。
そのため、スタート地点とゴール地点の座標の偶奇が違う場合はゴールに移動できないことがわかります。

移動を 2回行う場合を考えます。1回目が点 $(x_1,y_1)$ を中心、2回目が点 $(x_2,y_2)$ を中心とした移動の場合、点 $(p,q)$ は
点 $\left( 2x_2 - (2x_1-p) , 2y_2 - (2y_1-q) \right) = \left( 2(x_2-x_1)+p , 2(y_2-y_1)+q \right)$ に移動します。
つまり、 $\left( 2(x_2-x_1) , 2(y_2-y1) \right)$ 　の変化量の移動になります。

2回移動を1セットとして、スタート地点からゴール地点に近づけていくことができます。

以下、 $x$ 座標について考えます。

$a=b$ の場合、 $x_1=x_2=a$ しか選べないため、スタート地点の $s_x$ と $2a-s_x$ にしか移動できません。
$t_x = s_x$ の場合、偶数回の移動であればよく、 $t_x = 2a - s_x$ の場合、奇数回の移動であればよいです。
奇数回の移動については、スタート地点から 1回移動した状態をあらためてスタート地点と考えれば、あとは偶数回の移動であればよくなります。

$a\lt b$ の場合、 $x_1 = a, x_2 = b$ とすれば 2回の移動で座標は $s_x \to s_x + 2(b-a)$ と変化し、
$x_1 = b, x_2 = a$ とすれば $s_x \to s_x - 2(b-a)$ と変化します。
問題の制約から、 $s_x$ と $t_x$ の差は最大でも $2\times 10^5$ であるため、2回の移動で 2ずつ近づいていく場合でも
$2\times 10^5$ 回の移動になり、 $10^6$ 回以下という条件は満たします。そのため、移動回数の上限の制約でゴールに届かないということはありません。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  sx, sy = readInts()
  tx, ty = readInts()
  a,b,c,d = readInts()

  dx = tx - sx
  dy = ty - sy

  if dx % 2 != 0 || dy % 2 != 0
    # 移動しても 奇数座標は奇数座標、偶数座標は偶数座標 のままなので、
    # 偶奇が異なる先には移動できない
    println("No")
    return
  end

  move1step = false

  # 偶数回移動だけゴールに到達できない場合、1回移動する
  if (a == b && sx != tx) || (c == d && sy != ty)
    sx = 2a - sx
    sy = 2c - sy
    move1step = true

    # 残り偶数回移動だけゴールに到達できない場合
    if (a == b && sx != tx) || (c == d && sy != ty)
      println("No")
      return
    end

  end

  # ここまで問題なければ、ゴールに到達可能
  println("Yes")

  # 1回移動していた場合、"Yes" 出力後に移動を出力
  if move1step
    println(a," ",c)
  end

  # あとは2回の移動を1セットとしてゴールに近づいていく

  while sx != tx || sy != ty

    if sx < tx
      x1 = a
      x2 = min(b, a + div(tx - sx,2))
    else
      x1 = b
      x2 = max(a, b - div(sx - tx,2))
    end

    if sy < ty
      y1 = c
      y2 = min(d, c + div(ty - sy,2))
    else
      y1 = d
      y2 = max(c, d - div(sy - ty,2))
    end

    println(x1," ",y1)
    println(x2," ",y2)

    sx += 2*(x2-x1)
    sy += 2*(y2-y1)

  end

end  # function solve

# main
solve()