2006/Staff/牟田

問題概要 †

半径 1 の円が xy 平面上に与えられ，太陽がθ方向から入射している．

この時、円の作る影の幅が最大の時と最小の時の入射方向θを求めよ．

解説 †

見方を変えて †

入射方向が θ というのは扱いづらいので，入射方向はy 軸に平行な方向に固定して 円の座標全体を θ' だけ回転させることとします．

このとき、θ' = θ - PI/2 が成り立ち，定義域は -PI/2 <= θ' <= PI/2

-PI/2 <= θ' <= PI/2 の領域の分割 †

定義域が PI と広く，回転させると円が重なったり，離れたり，左側に出ている円が入れ替わったり，と扱いづらいので定義域を分割する．

任意の二円で以下の角度を計算する

• 円の中心のx座標の差の絶対値が 2 になる回転角（円同士の影が繋がる/離れる回転角の境界）
• 円の中心のx座標の差が一致する回転角（影が左に出ている円と影右に出ている円が入れ替わる回転角の境界）

そして、求めた回転角をソートする．円の位置関係が一切変化しない回転角の区間が得られた．

影が連結している円/影の長さ †

前の説で円の位置関係が変化しない回転角の区間が得られたのでその区間[θ1, θ2]で考える．

影が連結している円の集合の影の長さは左端の円の座標と右端の円の座標のみに依存して決まる．

• 円の位置関係が変わらないので，
  • 新たな円が繋がって増えることが無い．
  • 連結している円の集合が切れて複数の集合に分かれることが無い．
  • 左端/右端の位置には常に同じ円が占め別の円に入れ替わることが無い．

右端の円と左端の円のそれぞれの座標を複素数で pr, pl と表記すると影の長さは

real{ (pr - pl)exp(iθ) } + 2　　[θ1 <= θ <= θ2]

と表すことができる

影の最大/最小の計算 †

各連結している円について

real{ (pr_i - pl_i)exp(iθ) } + 2

を調べ、そのexp(iθ)の係数部分 (pr_i - pl_i) の和をとり θ に関する影の長さの関数を作る。それを区間内での最大/最小を求め、各区間で随時それを計算する