ABC151 F - Enclose All
問題
$ N個の点が与えられるので、最小包含円の半径を求めてください。 制約
$ 2 \leq N \leq 50
$ 0 \leq x_i \leq 1000
$ 0 \leq y_i \leq 1000
考察
いずれかの2点、あるいは3点の外接円になるはずなのでそれを全探索。
$ O(N^4)
ある点$ (x,y)が与えられたときに、各点への距離の最大値が最小包含円の半径になる。
距離の最大値を最小化する$ (x,y)を三分探索で求めれば良い。 三分探索を回す回数を$ Mとすれば$ O(M^2 N)。
60回まわせば$ x, yの絶対誤差が$ 1000 \times 10^{-10} = 10^{-7}以下になるはず。
シャッフルしてから
点を追加
最小包含円の更新
をしていく。