009 - Three Point Angle（★6）の解説

何の話かと言うと

atcoder.jp

上記の問題をネタに、バイナリーサーチの基本的な書き方を説明します。

問題の考え方

原点となる点を決めて、全体を平行移動した後に、それぞれの点の偏角（x 軸に対する 0 〜 360°の範囲の角度）を求めます。

すると、任意の２点の角度は偏角の差で計算できるので、すべての組み合わせを試せば最大角が決まります。

なのですが・・・

これをこのまま実装すると、中心点についてのループ 回、任意の２点の組み合わせループ 回なので、全体として になります。今の場合 なので、 で間に合いません。

実行時間の見積もりについては、下記の記事も参考にしてください。

enakai00.hatenablog.com

バイナリーサーチで最大角を探す

点 A を決めた時に、これとの角度が最大になる点は、バイナリーサーチで高速に探す事ができます。たとえば、偏角のリストを昇順ソート（これは で可能）したものを deg_list として、点 A の角度が deg_list[0] だったとします。そうすれば、(M=len(deg_list)-1 として）deg_list[1] 〜 deg_list[M] のどこかに答えがあるはずです。

最初に、k = 1 + (M - 1) // 2 を試します。deg_list[k] < deg_list[k+1] であれば、答の範囲は deg_list[k+1] 〜 deg_list[M] に絞り込めます。deg_list[k] < deg_list[k+1] でなければ、deg_list[1] 〜 deg_list[k] に絞り込めます。

このように、答えの範囲の中央を試すことで、範囲を半分ずつにしぼっていき、最後に範囲が 1 つになれば、それが答えです。一般には、こんな感じで実装できます。

low = # 範囲の最小値
high = # 範囲の最大値
while low < high:
  m = low + (high-low) // 2
  if <m より上に答えがある（m 自身は答えではない）>:
    low = m + 1
  else:
    high = m

# ここに来た時の low = high が答え

こうすれば、N 個の点それぞれについて、 で最大角が見つかるので、全部の組み合わせについて ではなくて で確認することができます。原点の選び方とあわせても全体で なので、なんとか間に合います。

なお、上記の点 A が deg_list の先頭にない場合は、角度の周期性を利用して、点 A が仮想的に先頭になるものと考える必要があります。（文章で説明するとややこしいので）下記のコードを参考にしてください。

atcoder.jp

おまけ

点 (x, y) と x 軸の角度を求める際に、 （tan を計算して arctan で角度に戻す）という方法がよく説明されますが、90度のところで発散するのでうまくいきません。上記のコードでは、cos 経由で計算した後に、y の符号で調整しています。

      cos = x / math.sqrt(x*x + y*y)
      deg = math.degrees(math.acos(cos))
      if y < 0:
        deg += (180-deg)*2