SRM645 Div1 Med ArmyTeleportation
http://community.topcoder.com/stat?c=problem_statement&pm=13346
[問題]
平面上の整数座標にN個の出発点と、N個の目標点があり、全ての出発点を目標点に移動させる
。そのために、塔が3個ある。塔を使うと、全ての頂点を塔の反対側に移動させる。(塔を中心として全ての頂点を180度回転させる。) 塔は何回使っても良い。
移動が可能なら"possible"、不可能なら"impossible"を返す。
1≤N≤50
-1,000,000≤x,y≤1,000,000
[解法](終了後)
ある点から、頂点を2回使った後の移動先を考える。
上記の図で、黒い点が塔、青い点がある点の移動とする。
2回移動すると、黄色い線を使った三角形と、赤い線を使った三角形は相似形で2倍の大きになる(黄色と赤は平行線)。つまり、ある点について2回移動すると、3つの塔が作る三角形の線分の2倍移動できることになる。
そのため、2n回移動した後の点は以下のような塔3個三角形の2倍の三角形の組み合わせになる。(ちょっとずれてるけど。)
この三角形たちの頂点のいずれかであれば2n回後に移動できる。
頂点かどうかは、三角形のうち二片のベクトルが作る座標を、直行座標に変換して整数かどうかで確認する。これは、2片によるアフィン変換の逆行列から計算する。
2片が平行な場合(行列式が0の場合)、GCDの倍数かどうかで判定する。
頂点は複数あるので、目標点の全てについて、移動した場合に全ての頂点を相似形で移動できるか確認する。
これで2n回後に目標点に行けるかどうかが判定できる。
2n+1回後は、3つの塔のいずれかでの反転先が座標上にあるかで判定する。
[コード](C++)
[感想]
上は説明になっているのだろうか。。。
平行な場合を考えたり、longlongにしたり、などを含めて時間内に動くコードを書くのは難しかった。