1<=x,y<=30の格子点を中心として、半径1の円柱が、n(<=100)本建っている。
太陽の位置によって円柱は影を生み出す。
影の幅が最大/最小になる太陽の方角を求めよ。
答えは0以上PI未満で、10^-10までの誤差が許されている。
非常に数学的な問題。
解く為には三角関数の加法定理、合成が必要になる。
まず、影がくっつく/離れる、影の右端/左端を作っている柱が変わる、といった事象が起こり得る角度を全て列挙する。
これらの角度は解の候補になり得る。
角度はどれも2つの円の共通接線のなす角度になっている為、これを全部挙げてしまえば良い。(多目に出す分には答えは変わらない)
次に、その影の状態が変わる二つの角度の間で、影の幅が極大、極小を迎える角度を探す。
一つの連結した影に注目し、太陽の為す角度をA、影の右端を作った柱と影の左端を作った柱の中心間を結ぶ線分をLとすると、
この影の長さは、1 + Lの為す影の長さ + 1 で求められる。
Lの為す影の長さは、Lの長さ * sin(A + Lと基準線の為す角)で求まる。
これを加法定理で分解し、パラメータを当てはめてやると、 C1 * sin(A) + C2 * cos(A) という形になる。
よって、各影の長さの総和は、C3 + C4 * sin(A) + C5 * sin(A) と求められるので、
ここで、三角関数の合成を行い、 C3 + C6 * sin(A + C7)
A = -C7 + PI/2の時、 この値は極大となり、 A = -C7 - PI/2の時、この値は極小となる。
この角度が、影の状態が変わる角度の間に収まっている時は、これも解の候補に挙げなくてはならない。
あとは、各候補に対して実際の値を計算してしまえば良い。
始めに列挙した角度、候補数がO(n^2)個で、最大角/最小角/値の計算にO(n*log(n))かかるので、全体として、O(n^3*log(n))で計算できる。
ICPCの国内予選では問題が無いが、PKUではTLEになった為、vectorを配列に落とす最適化を行った。