1301 - Malfatti Circles

AOJ

問題

三角形の頂点の座標が与えられる。
三角形に図のように内接する３つの円の半径をそれぞれ求めよ。

解法

二分探索による。
1つの円の半径を決定すると、その円と三角形の2つの辺に接する円の半径、中心座標を求める事が出来る。
他の2つの円を求めたら、その2つの円が交わるか交わらないかによって二分探索すればよい。
つまり、二分探索で用いる条件を、
（2円の中心間の距離）<（2円の半径の和）
とすればよい。


以下、1つの円の半径をrと決めたとき、他の円を１つ求める方法を示す。

図のように、a, b, t, αを決める。上の円の半径がrである。
このとき、左下の円の半径は、
t|a|sinα
となる。
左下の円と上の円の中心座標の距離はそれぞれの半径の和だから、

ta-b = r + t a sinα

が成り立つ。これはtについての二次方程式となり、小さいほうの解が求めたいtとなる。
tが求まったので、左下の円の中心座標と半径が基まった事になる。右下の円についても同様に求める。
注意するべき事は、上の円の半径が大きすぎるときヤバいということ。
上の円が辺に接する部分が三角形より外に出ていたら、二分探索の条件の結果をfalseにする。