AOJ 1323 - Encircling Circles

AOJ

for アジア地区

問題

n個の円が与えられる。
i番目の円は、中心(x[i],y[i])、半径r[i]である。
全ての円を内包するような半径Rの円を動かしたときにできる領域の外周の長さを求めよ。

制約

1<=n<=100
円はoverlapしうる。

解法

求める外周は

  • 1つの円に接するような半径2*R-r[i]の大円の一部
  • ２つの円に接するような半径Rの円の一部

を連結したもの。

前者を求める方法

１つの円に注目し、その円を円iとする。
円iに接するような大円で、全ての円を含むような大円の角度（円iの中心から、大円の中心方向の角度）の区間を求める。
円iに接するような大円については、この区間の長さの和*(2*R-r[i])が周の長さとなる。

後者を求める方法

（怪しいけど通った）
前者を求めるときに求めた区間の端点（角度）に対応する大円を書いたとき、それに接する円を求める（円iと、少なくとももう１つの円が接するはず）。
複数の円に接している図が下図。
茶色が円i。

ここで、接している円それぞれに対してθを求め、θ<π+EPSであり、θが一番小さいものを選ぶ。(不等式の境目が怪しめ)
そのようなθが無かったら、その端点は無視。
そのようなθがあったら、答えにθ*Rを足す。

感想

サンプルが親切なおかげで無理やり解けた。