phyllo’s algorithm note

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

ABC151 F. Enclose All

問題

平面上のN個の点が与えられる。
これらすべてを内部または周上に含む円の半径の最小値を求めよ。

制約

  • 2 <= N <= 50
  • 0 <= x_i, y_i <= 1000
  • 与えられる点はすべて異なる

解法

いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか?をチェックする。

まず、凸包のある2点が周上にあると考えると、その2点の中点を中心にした2点間の距離の半分が候補の円となる。

次に、凸包のある3点が周上にあると考える。
鈍角三角形の場合は、鈍角ではない2点の中点を中心した2点間の距離の半分が候補の円となるが、上記の2点のときに列挙されているはずなのに無視してよい。
鋭角三角形の場合は、その3点を含む外心や半径はwikipediaの「外接円」のエントリで求め方が載っているので、それを参考に求めれば良い。


円に含まれるかのチェック時には、誤差を考慮して比較することを忘れない。