ABC151 F. Enclose All
問題
平面上のN個の点が与えられる。
これらすべてを内部または周上に含む円の半径の最小値を求めよ。
制約
- 2 <= N <= 50
- 0 <= x_i, y_i <= 1000
- 与えられる点はすべて異なる
解法
いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか?をチェックする。
まず、凸包のある2点が周上にあると考えると、その2点の中点を中心にした2点間の距離の半分が候補の円となる。
次に、凸包のある3点が周上にあると考える。
鈍角三角形の場合は、鈍角ではない2点の中点を中心した2点間の距離の半分が候補の円となるが、上記の2点のときに列挙されているはずなのに無視してよい。
鋭角三角形の場合は、その3点を含む外心や半径はwikipediaの「外接円」のエントリで求め方が載っているので、それを参考に求めれば良い。
円に含まれるかのチェック時には、誤差を考慮して比較することを忘れない。