競プロ典型 90 問 009 - Three Point Angle（★6）

導入

atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。

使用しているアルゴリズム

• 全探索
• 偏角ソート（atan2 → degree → %360）
• 二分探索（bisect_left）
• 幾何（最大角度差の探索）

解法のポイント

この問題では、任意の2点を結んだ直線のなす角度のうち、最大の角度差を求めるという、幾何的性質を用いた探索問題です。

方針としては、「ある点を中心にして、他の点との偏角（角度）を求め、それらの中から最も鋭角でないもの＝最も広い角度」を探します。

1. 各点を中心 (x, y) として全探索します。
2. 他の全ての点との偏角（ベクトル (x-dx, y-dy) の角度）を atan2 を使って求め、度数に直してリスト tmp に格納します。
3. tmp をソートして、各角度に対して180°反対側に最も近い角度を探します。
   • ここで二分探索 bisect_left を使うことで効率よく反対側の角度候補を得られます。
4. 180°との差が小さい方が最大角度になる可能性があるので、(tmp[i] - tmp[idx])%360 と (tmp[i] - tmp[idx-1])%360 の2通りを比較して最大値を更新していきます。
5. 全体の最大値が答えになります。

最終的に r に最も大きな角度（180度以下の最大角度）が格納され、それを出力します。

ACサンプル

import bisect
import math

def to180(degree):
  degree %= 360
  return degree if degree <= 180 else 360 - degree

N = int(input())
nodes = [(x,y) for x,y in (map(int,input().split()) for _ in range(N))]
r = 0

for x,y in nodes:
  tmp = []
  for dx, dy in nodes:
    if (x,y) == (dx, dy):
      continue
    
    tmp.append(math.degrees(math.atan2(y - dy, x - dx)) % 360)
  
  tmp.sort()
  for i in range(N - 1):
    target = (tmp[i] + 180) % 360
    idx = bisect.bisect_left(tmp, target)
    a = to180(tmp[i] - tmp[idx % (N - 1)])
    b = to180(tmp[i] - tmp[idx - 1])
    r = max(r,a,b)

print(r)

リンク

ACサンプル集(アルゴリズム逆引き)

問題へのリンク