問題

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_b

$3$ つの座標が与えられる。 $3$ 点が三角形をなすとき、三角形に内部に存在する同じ半径をもつ $2$ つの円の最大の半径を求めよ。 $2$ つの円は重なってはいけない。

制約

$0 \le x_i, y_i \le 1000$

考え方

円の長さを $x$ とする。また三角形ABCの内心円の半径を $r$ とする。

三角形ABCの内部に半径 $x$ の円が $1$ つかけるとは

各辺から円の中心までの距離が $x$ 以上ある点の集合内であればかくことができる。実はこれはもとの三角形ABCと相似になっている。これを三角形DEFとしておこう。

三角形ABCの内部に半径 $x$ の円が $2$ つかけるとは

三角形DEFにおいて、最大の辺の長さが $2x$ 以上であれば $2$ つの円を重なることなく書くことができる。三角形ABCと三角形DEFは相似で、三角形ABCの最大の長さの辺を AB としておくと、三角形DEFにおける最大の辺を DE とすると、DEの長さは $\displaystyle DE = AB * (1 - \frac{x}{r})$ となる。あとは $2x \le DE$ を満たす最大の半径 $x$ を二分探索で求めればよい。