CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle
幾何。
問題概要
三角形の頂点が与えられる。
三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。
制約
解法
まず、三角形の内部に半径 の円がかけるとはどういうことかを考えてみる。
円の中心と三角形の辺の距離が 以上であれば、半径 の円がかける。
つまり、三角形の内部で、各辺から 以上離れた場所(図の緑の三角形)に円の中心があれば、その円の円周は三角形の辺上か三角形の内部にあることがわかる。
次に、三角形の内部に半径 の円が重ならないように2つかけるとはどういうことかを考える。
それぞれの円の中心と三角形の辺の距離が 以上であり、2つの円の中心の距離が 以上であれば、半径 の円が重ならないように2つかける。
つまり、三角形の内部で、各辺から 以上離れた場所(図の緑の三角形)にそれぞれの円の中心があり、2つの円の中心間の距離が 以上ならば、その2円の円周は三角形の辺上か三角形の内部にあり、かつ2円は重ならないことがわかる。
ここで、元の三角形の内接円の半径を とすると、元の三角形の内部で各辺から 以上離れた点の集合からなる三角形の内接円の半径は である。よって、2つの三角形の相似比は 。
2つの円の中心間の距離を 以上にするためには、「元の三角形の内部で各辺から 以上離れた点からなる三角形」の少なくとも一辺が 以上であればよい。つまり、与えられた三角形の3辺のうち最も長い辺の長さを とすると、内部の三角形の最も長い辺の長さは になるので、これが 以上ならば、与えられた三角形の内部に半径 の円が重ならないように2つかける。
よって、半径の長さ を二分探索で決め打ちして、それぞれの について、三角形の内部に半径 の円が重ならないように2つかけるかどうかを判定すればよい。
Submission #2118930 - CODE FESTIVAL 2016 Grand Final(Parallel)