足跡-sokuseki-

りかの日進月歩の記録

CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle

B - Inscribed Bicycle

幾何。

問題概要

三角形の頂点が与えられる。
三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。

制約
 0 \le x_i, y_i \le 1000


解法

まず、三角形の内部に半径  x の円がかけるとはどういうことかを考えてみる。
円の中心と三角形の辺の距離が  x 以上であれば、半径  x の円がかける。
つまり、三角形の内部で、各辺から  x 以上離れた場所(図の緑の三角形)に円の中心があれば、その円の円周は三角形の辺上か三角形の内部にあることがわかる。
f:id:wk1080id:20180220230806p:plain


次に、三角形の内部に半径  x の円が重ならないように2つかけるとはどういうことかを考える。
それぞれの円の中心と三角形の辺の距離が  x 以上であり、2つの円の中心の距離が  2x 以上であれば、半径  x の円が重ならないように2つかける。
つまり、三角形の内部で、各辺から  x 以上離れた場所(図の緑の三角形)にそれぞれの円の中心があり、2つの円の中心間の距離が  2x 以上ならば、その2円の円周は三角形の辺上か三角形の内部にあり、かつ2円は重ならないことがわかる。
f:id:wk1080id:20180220230751p:plain


ここで、元の三角形の内接円の半径を  r とすると、元の三角形の内部で各辺から  x 以上離れた点の集合からなる三角形の内接円の半径は  r - x である。よって、2つの三角形の相似比は  r : r - x

2つの円の中心間の距離を  2x 以上にするためには、「元の三角形の内部で各辺から  x 以上離れた点からなる三角形」の少なくとも一辺が  2x 以上であればよい。つまり、与えられた三角形の3辺のうち最も長い辺の長さを  A とすると、内部の三角形の最も長い辺の長さは  A \times \frac{r - x}{r} になるので、これが  2x 以上ならば、与えられた三角形の内部に半径  x の円が重ならないように2つかける。


よって、半径の長さ  x を二分探索で決め打ちして、それぞれの  x について、三角形の内部に半径  x の円が重ならないように2つかけるかどうかを判定すればよい。

Submission #2118930 - CODE FESTIVAL 2016 Grand Final(Parallel)