ICPC-F

影を動かすアニメーションGIFが面白いかも。あと、先に断っておくけど、この考え方は一般論として通用するかといえば通用しないと思う。サンプルI/Oは通ったけど。

大雑把な方法論としては、範囲を少しずつ狭めて探索。θについて影の長さを求める関数 f(θ) なんてものを考えても、不連続ってことはないし、導関数がでっかい値になる気もしないし。問題なのは最大値(最小値)に近い極大値(極小値)がある場合。きっとそんな問題も用意してるんだろうなぁ。

書いてみたコード

全体の流れ

  1. θが動く範囲を[0,π]に設定。
  2. θが動く範囲がεより広い間は以下を繰り返す
    1. θの刻み幅はループ幅の1/1000(=dθ)(WA食らったら／時間を気にしないなら小さく)でループ
      1. 影の長さを計算する
      2. 最大値かどうか判定→記録
    2. θが動く範囲=[最大値を取るθ-dθ,最大値を取るθ+dθ]に設定して戻る。
  3. 同じ事を最小に関してもやる。

影の長さの計算

  1. 円筒の座標を全部θ回転させる(回転後のY座標さえ分かれば十分)
  2. Y座標でソート
  3. Y座標が小さい順にループ。
    1. yMax＋１＜y座標 なら 影の長さ+=(yMax−yMin) やってから yMinにy座標−１ を設定。
    2. yMaxにy座標＋１ を設定