D問題

めんどくせー。格子点の方向にだけ光線を飛ばせばいいのはすぐにわかった。でも四角との交点の座標が有理数になる。めんどくせえー。
最初はboostの有理数ライブラリを使って、直線と直線の交点を求めたりくそ複雑なコードを書いてみたんだけど、遅すぎるうえに計算が間違ってる。

しかたがないので、めんどくさくない方法を考えて、光線の方向が決まったら有理数が発生しないように空間をスケールしておけばいいじゃん。
ついでに、縦横のスケール比を変えれば８方向だけの移動しかなくなるじゃん。やったー。これで方程式解かなくても一歩ずつぶつかるまで歩いていけばいいじゃん。

https://gist.github.com/2391863

やったー実装できた。しかもかなり速くなったー。