2006/Contest/国内予選

Problem F: Secrets in Shadows †

問題概要 †

解法 †

まず，全ての円の組み合わせの共通接線の傾きで場合分けする．

すると，それぞれの範囲内では太陽の角度thに対して幅が

f(th) = a * sin(th) + b * cos(th) + c

の形になり，各範囲のa, b, cを求めることができる．

この範囲の最大値と最小値の候補は両端と，

f(th) = A cos(th - d) + c

の形に変換したときのd, d + PIであるので，これら全てのf(th)を計算し，最大値と最小値を求める．(寺島; Jul 7, 2006)

議論 †

黄金分割法でやろうとしていたが，これだとf(th)の精度が足らない．

思い浮かべば立式や実装に時間がかかるわけではないが，即座に解法をひらめくのはかなり難しい気がする．(寺島; Jul 7, 2006)

ファイルを添付する †

terashima_F.cpp