問題概要 †半径 1 の円が xy 平面上に与えられ,太陽がθ方向から入射している. この時、円の作る影の幅が最大の時と最小の時の入射方向θを求めよ. 解説 †見方を変えて †入射方向が θ というのは扱いづらいので,入射方向はy 軸に平行な方向に固定して 円の座標全体を θ' だけ回転させることとします. このとき、θ' = θ - PI/2 が成り立ち,定義域は -PI/2 <= θ' <= PI/2 -PI/2 <= θ' <= PI/2 の領域の分割 †定義域が PI と広く,回転させると円が重なったり,離れたり,左側に出ている円が入れ替わったり,と扱いづらいので定義域を分割する. 任意の二円で以下の角度を計算する
そして、求めた回転角をソートする.円の位置関係が一切変化しない回転角の区間が得られた. 影が連結している円/影の長さ †前の説で円の位置関係が変化しない回転角の区間が得られたのでその区間[θ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) の和をとり θ に関する影の長さの関数を作る。それを区間内での最大/最小を求め、各区間で随時それを計算する |