SRM645 div1 500

問題

兵士が(x1[i],y1[i])にいる。
塔が(xt[i],yt[i])に配置されており、塔を起動すると、その塔を中心にすべての兵士が点対称に移動する。塔は何度でもどの順番でも起動することができる。
すべての兵士を(x2[i],y2[i])に配置することができるか？

-10^6 <= x,y <= 10^6
塔の数 = 3
兵士の数 <= 50, distinct

考え方

まず、塔の起動の仕方のパターンを探る。
塔A,B,Cがあり、それぞれ1回だけ起動する場合は、点対称に移動する。
同じ塔を連続で起動すると元の位置に戻る。
2つの別の塔を順番に起動すると、塔間の2倍の平行移動することがわかる。
3つ以上の塔の起動の組み合わせは、0回か1回どこかの塔に対して点対称＋平行移動になる。

点対称はする/しない場合の兵士の位置を初期位置とすると、平行移動だけ考えればよい。
平行移動しかないので、すべての兵士を同じ移動量で平行移動できるかどうかをチェックする。
端っこにいる兵士て対応関係を取って移動量を求めて、すべての兵士がその移動量で移動した先に対応する(x2[i],y2[i])があるか確認すればよい。

平行移動できる場合は、移動量が条件を満たせるかを確認する。
塔A,Bの順で起動すると、移動量は、2*(B-A)だけ移動する。
x,y座標をそれぞれわけて考えると、
xの移動量 = i*(2*(Bx-Ax)) + j*(2*(Cx-Bx)) + k*(2*(Ax-Cx))
yの移動量 = i*(2*(By-Ay)) + j*(2*(Cy-By)) + k*(2*(Ay-Cy))
ただし、3変数i,j,kに対して、2式しかない。

実は、平行移動を考えると、C,Aの順で移動する場合、B,A,C,Bの順で移動する場合と一致する。
なので、変数kはいらなくて、整数の2変数i,jが存在するかを確認すればよい。
上記を書き換えて、
dx = i*p0 + j*p1
dy = i*q0 + j*q1
を満たす整数解(i,j)があるかどうかを確認する。
p0*q1-q0*p1が0でない場合は、普通に連立方程式を解いてi,jが整数になるかどうかを確認。
p0*q1-q0*p1が0になる場合(縮退する場合)は、拡張ユークリッド互除法を使って、満たす整数解(i,j)を見つけて返す。
(負数などがまざるので、適当正の値で求めて符号を後で合わせておく。p0かp1どちらかが0でなければdxの方の式からi,jを求められ、q0かq1どちらかが0でなければdyの方の式からi,jを求められる)