AOJ 2562/JAG春コンテスト2012H: Rings

JAG春コンテスト2012の問題がAOJに収録されたので，以前書いたコードを投げてみました．
公式の解説によれば

座標変換
平面同士の交線を求める
円と直線の交点を求める

ということをするらしいですが，そんな回りくどいことしなくても解けるということで久しぶりにブログ書いてみます．

まずは記号の定義です．
円1について，中心を $\bf{c}_1$ とし，中心から円周への直交するベクトルを $\bf{u}_1,\bf{v}_1$ とします．
円2についても同様です．

とりあえず円2について考えてみます．まずは2次元で考えましょう．
2次元の円上の点は，角度θを用いて(cosθ,sinθ)と表せます．
これは，直交する単位ベクトル(1,0), (0,1)を用いれば (1,0)cosθ+(0,1)sinθ とも書けます．
もっと言えば，直交する単位ベクトル $\bf{u},\bf{v}$ を用いて $\bf{u}\cos \theta+\bf{v}\sin \theta$ と書けるはずです．
(より一般に， $\bf{u},\bf{v}$ が直交していれば， $\bf{u}\cos \theta+\bf{v}\sin \theta$ は楕円となるはずです．図1参照．)
最早これは2次元に限った話ではなく，当然3次元でも同様の表記が可能です．
すなわち，円2上の点は，角度θを用いて $p_2=\bf{c}_2+\bf{u}_2\cos \theta+\bf{v}_2\sin \theta$ と表すことができます．
f:id:climpet:20140228001054p:plain

次に，円1について考えます．
円1を含む平面S₁について，2つの円が繋がっているのは，次の条件を満たすときです．

S₁と円2の交点が2つ存在する．
2つの交点について，片方が円1の内側，もう片方が円1の外側にある．

さて，S₁の法線ベクトルは $\bf{n}_1=\bf{u}_1 \times \bf{v}_1$ です．
ここで， $\bf{p}_2$ がS₁上にあるならば， $(\bf{p}_2-\bf{c}_1)\cdot \bf{n}_1=0$ が成り立つはずです(図2参照)．
これとさっきの $\bf{p}_2$ の式を合わせて色々整理すると，
a cosθ+b sinθ+d=0 という式になります．
さらにここらへんの式を使うと，
e sin(θ+φ)+d=0
という式になります．a,b,d,e,φについては普通に計算できるはずなので，各自計算してください*1．
この式から，(交点が存在するならば)θを2つ求め，それぞれ $p_2=\bf{c}_2+\bf{u}_2\cos \theta+\bf{v}_2\sin \theta$ にぶちこめば
$p_2$ が求まります．
あとは，それが円1の内側かどうか判定すればよいです．これは， $|\bf{p}_2-\bf{c}_1|<1$ であれば内側，さもなくば外側となります．
f:id:climpet:20140228001103p:plain