きままにものづくり

日々の気付いたことなんかを書いてます。

SRM645Div1Medium

問題

二次元平面上にN個の点が(x1,y1)と(x2,y2)が与えられる。平面上には3つの塔があり、ひとつの塔を指定し魔法を唱えると、その塔を中心に点対象に点を移動できる。(x1,y1)の点を(x2,y2)に移動できるかを判別せよ。

解法

kmjp.hatenablog.jp
上の記事の回答を使用した。
魔法をいくら使用しても点どうしの相対的な位置は変更することができないので、点集合のソートの差分は一意に決まる。その差分をdx,dyとする。
二つの塔を用いて魔法を唱えると、その塔同士の差分ベクトルの2倍分移動することができる。
塔は3つあるので移動できるパターンは以下になる。

  • ±2*(xt[2]-xt[0], yt[2]-yt[0])
  • ±2*(xt[2]-xt[1], yt[2]-yt[1])
  • ±2*(xt[1]-xt[0], yt[1]-yt[0])

3つのベクトルは線形従属の関係にあるので、2つのベクトルを用いることでもうひとつのベクトルを作成することができる。
塔2と塔0を使用した場合の移動をwx0,xy0とし、塔1と塔0を使用した場合の移動をwx1,wy2とする。
wx0 = xt[2]-xt[0], wy0 = yt[2]-yt[0]
wx1 = xt[1]-xt[0], wy1 = yt[1]-yt[0]
塔2と塔0を使用する移動の回数をp、塔1と塔0を使用する移動の回数をqとした時、以下の式が成り立つ。
\left( \begin{array}{cc} wx0 & wx1 \\ wy0 & wy1 \end{array} \right) \left( \begin{array}{c} p \\ q \end{array} \right) = \left( \begin{array}{c} dx \\ dy \end{array} \right)
この式の行列式が0でないならば、逆行列が存在する。p,qが整数解になるかを判別することで答えがもとまる。
行列式が0の場合は、p,qが存在しないか、無数に存在するかのどちらかになる。

計算量

O(N log N)

コード