phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC021 B. Holes

問題

平面上にN個穴があいている。
今、原点を中心とした半径Rの円に無作為にすぬけさんを置く。すぬけさんはユークリッド距離で最も近い穴に落ちる。
すべての穴について、すぬけさんが落ちる確率を求めよ。

制約

  • 2 <= N <= 100
  • 穴の座標はすべて整数、すべて異なる、|x_i|,|y_i|<=10^6
  • R = 10^10^10^10

解法

穴がある位置は、円の中心付近で、円全体からして十分に小さいので細かい部分は無視できる。
どちらかというと、穴の集まる原点付近よりもはなれたの部分に置かれる割合が大きく、そのようなケースだけを考えればよい。

O(NlogN)解

十分離れたところにすぬけさんを置いた場合、すぬけさんが落ちる穴は、穴の集まりの中でも外側にある穴のどれかになる。
穴の集まりの中で、内側の方の穴に落ちるには「凸包内、かつ、他の穴より近い位置」じゃないといけないため、落ちる確率は円の大きさ的に無視できるほど小さくなる。
したがって、穴の凸包を求めて、凸包をなす穴についてだけ考える。


凸包のある穴pと両方に隣り合う穴q,rについて考える。
穴pに落ちるには、両隣の穴q,rとの二等分線を円の外側に向かって伸ばした線より穴p側に設置されていれば穴pに落ちる。(正確には、穴の近くでは他の穴の方が近くてそっちに落ちる可能性があるが、すぬけさんがそこに設置される確率はかなり小さいので無視してよい。(たとえば下の図の二等分線始まり付近に設置されたら内側の穴に落ちる))
凸包の点すべてについて、どの角度で両隣の穴との二等分線が外側に向かって伸びているかがわかれば、角度の割合から落ちる確率が求められる。


凸包を求めるのにO(NlogN)程度なので、答えもO(NlogN)。

O(N^2 logN)解

凸包を使わなくてもよい。


f:id:phyllo_algo:20180225105441p:plain
ある穴pに注目する。
穴pから他のすべての穴への角度を求め、ソートしておく。穴pを中心として穴qの角度はatan2(q_y - p_y,q_x - p_x)で求められる。
ソートした角度において、両隣との角度の差がθで、その最大となる角度がmaxθであるとする。(ソート後の最初と最後の角度の差を求めるときは処理が少し変わるので注意)

もし、maxθがPI(180度)よりも小さい場合は、他の穴に囲まれているため、凸包の内部の点で、答えは「0.0」になる。
もし、maxθがPI(180度)よりも大きい場合は、穴pに落ちる角度は赤い二等分線がなす角度なので、答えはmaxθから両側90度分を引いた「maxθ-PI」になる。

各点について、他の点との角度のソートが必要なのでO(N*NlogN)=O(N^2 logN)。

O(NK)解

求められる精度が少し荒いようなため、穴をすべて内包する十分大きな円の周上を等間隔でK点用意し、各点から落ちる穴を見つける、という方法でも通せるらしい。
ただ、Kや円の大きさなどのパラメータでの答えの精度の見積もりが難しい。

反省

普通に忘れてた、、、

負値の切り捨て

億劫がって、小数で保存してた変数から整数の変換時に微小な変化無視するために「+0.5とかしてからintキャスト」とかしてしまってハマった。
負値の場合は、

  • intキャストは、0に近づく
  • floor()は、小さい整数に近づく

なので、負値で+0.5してintキャストすると1ずれてしまう。
もう使わない。

偏角

theta = atan2(y,x)で-PI <= theta <= PI。