Codeforces 40C

点Aを中心とする半径1,2,3,...,Nの同心円と、点Bを中心とする半径1,2,3,...,Mの同心円がある。点Aと点Bの距離がDのとき、これらの同心円によっていくつの面が作られるか答えよ、という問題。

取り敢えずM個の同心円があるとして、N個の同心円を点Aを中心に書いていくことを考える。円を書いていく過程で、M個の同心円といくつ交点を持つか計算してやると、交点の数だけ面の数が増えていくことが分かる。交点があるかどうかは、新しく書く円の半径と相手の円の半径とDについて、三角形ができるかどうか。なので、M個の円について三角形ができるものがいくつかはすぐ分かる。それと、接するケースがあるのだけれど、新しく書く円が完全に中に入っているケースは面が増えるが、外側で接している場合には面が増えないという点に注意が必要。

後はループしてやるだけ。intが溢れるように作ってあるのがかなりの嫌がらせ。(気付かない方が悪いが。)