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)


ファイルを添付する

fileterashima_F.cpp 929件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileterashima_F.cpp 929件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:38 (4575d)