幾何修行

AOJ

japljさんが幾何の問題集をVirtual Arenaでセットしていたので、最近ちょこちょこやっている。
まだ途中だけど、とりあえずまとめる。
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=1178&active=status

AOJ 2045 - Turn Polygons

多角形の中にある多角形を、外側の多角形にぶつからないようにどこまで回転できるか。


全ての線分対に対して可能な回転角度を計算し、minをとる。
線分と円の交点が使える。

AOJ 2029 - Light The Room

多角形の中に光源がある。光は壁で1回まで反射で
きる。
このとき光が当たらない壁の長さはいくらか。

  • ある頂点を通る、
  • ある頂点を通って1回反射、
  • 1回反射してある頂点を通る、
  • 頂点で反射、

というパターンについて壁のどこと当たるかを計算し、壁を細分する。
細分された壁それぞれについて、光が当たるか当たらないかを計算する。

AOJ 2038 - The Extreme Slalom

線分がn本与えられるので線分1から線分nまで順番に線分に触れながら進むときの移動距離の最小はいくらか。

  • 最初と最後は、端点に接するか、垂直に接する
  • 途中は通過するか、端点で曲がるか、鏡のように反射する

dp[i][左/右] = i番目の線分の、左/右の端点にいくまでにかかる距離の最小
としてdp
i番目の線分からj番目の線分に行くとき、鏡面反射は2^{j-i-1}通り試す。
ここで、k番目の鏡面反射するならl(l>k)の線分をk番目の線分を対称軸として反転する。

AOJ 2062 - Hide-and-seek

線分によって表される廊下がある。
ある線分上にある点(sx,sy)から最も遠い廊下上の点はどれほど遠いか。


線分アレンジメント＋ダイクストラ
線分の中のほうが答えかもしれないのでそこは適当に。

AOJ 2029 - Walk under a Scorching Sun

2次元多角形、高さで与えられるビルと、線分で与えられる道が与えられる。
太陽は向きθ、仰角Φに位置する。
このとき、道上の点(SX,SY)から(TX,TY)に行くときに、ビルの影になってる部分ではなく、太陽の下を歩かなければならない距離の最小はいくらか。


道は線分アレンジメントする。
ビルの上面の頂点を地面に射影し、ビルの下面の頂点と合わせて凸包を取る。
道の線分を凸包の線分でカットして、細分された線分ごとに太陽に当たるか当たらないかを計算する。そしてグラフの辺のコストを太陽に当たる距離に設定する。
あとはダイクストラ。

AOJ 2023 - Princess, a Strategist

弾丸iは長さliで(xi,0)から時間tiのとき(vxi,vyi)で発射される。
自分は多角形で表されてコマンド列（時間と速度ベクトル）によって平行移動する。
このとき弾丸に当たる回数とそのときの時間は何か。


コマンド列の各速度ベクトルが効いてる時間ごとに分けて考える。
速度v1で動く初期状態s1な線分と，速度v2で動く初期状態s2な線分が交差する時間を求める部分が肝心。
一方を固定して相対距離を考えれば、線分と線分の交点を用いることが出来る。

AOJ 2125 - Land Mark

N個の点が与えられる。ある点にいる人が反時計回り順に見えた点を順に報告する。
このときその人いる場所として考えられる場所の面積はいくらか。


ある2点A,Bに対して、A→Bの場合、視点のスタートする場所は、A-Bに対して反時計回り方向の領域と時計回り方向の領域に分けられる。
そこで、全ての点対に対して領域を2つに分ける処理を凸カットによって行い、最大2^N個の領域が生成される。
このとき最初の領域としては十分大きな正方形を設定する。
細分された各領域に対して、重心に人がいたら報告通りの見え方がありえるかを求め、ありえるなら答えに面積を足し込む。
答えが一定以上大きい場合はInfinity。

AOJ 2226 - Psychic Accelerator

超能力を用いることで物体に加速度をかけることができる。
条件は

  • 加速度の大きの最大 <= amax
  • 動いている物体に対しては、進行方向・進行方向逆・進行方向と垂直な方向に加速度をかけられる
  • 静止している物体には自由な方向に加速度をかけられる

n個の線分が与えられる。線分iと線分i+1は円弧によって結ばれている（i<=n-1)。
このコース上に沿って物体を超能力を用いて移動させるとき最小時間はいくらか。


微妙な方向に加速度をかけられないので、円弧を進めるときは円弧の中心方向に加速度をかけることになる。
a=v^2/rより、v<=sqrt(ra)でなければならない。
ということで、各線分の各端点に対して、速度の上限が決まる。
その上限を超えないように最速で動かせば良い。
線分の途中ではその上限を超えても良いことに注意（出来るだけ超えないと最速にならない）。
幾何というより高校物理な感じだけど、面白い問題だった。