SRM645 Div1 Med ArmyTeleportation

http://community.topcoder.com/stat?c=problem_statement&pm=13346

[問題]

平面上の整数座標にN個の出発点と、N個の目標点があり、全ての出発点を目標点に移動させる

。そのために、塔が３個ある。塔を使うと、全ての頂点を塔の反対側に移動させる。(塔を中心として全ての頂点を180度回転させる。)　塔は何回使っても良い。

移動が可能なら"possible"、不可能なら"impossible"を返す。

1≤N≤50

-1,000,000≤x,y≤1,000,000

[解法](終了後)

ある点から、頂点を２回使った後の移動先を考える。

上記の図で、黒い点が塔、青い点がある点の移動とする。

２回移動すると、黄色い線を使った三角形と、赤い線を使った三角形は相似形で２倍の大きになる(黄色と赤は平行線)。つまり、ある点について２回移動すると、３つの塔が作る三角形の線分の２倍移動できることになる。

そのため、2n回移動した後の点は以下のような塔３個三角形の２倍の三角形の組み合わせになる。(ちょっとずれてるけど。)

この三角形たちの頂点のいずれかであれば2n回後に移動できる。

頂点かどうかは、三角形のうち二片のベクトルが作る座標を、直行座標に変換して整数かどうかで確認する。これは、２片によるアフィン変換の逆行列から計算する。

２片が平行な場合(行列式が0の場合)、GCDの倍数かどうかで判定する。

頂点は複数あるので、目標点の全てについて、移動した場合に全ての頂点を相似形で移動できるか確認する。

これで2n回後に目標点に行けるかどうかが判定できる。

2n+1回後は、3つの塔のいずれかでの反転先が座標上にあるかで判定する。

[コード](C++)

[感想]

上は説明になっているのだろうか。。。

平行な場合を考えたり、longlongにしたり、などを含めて時間内に動くコードを書くのは難しかった。