naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #514 (Div. 2) - D. Nature Reserve

agwたんから

D. Nature Reserve

  • 全ての点が y\ge0 または y\le0 にあること
  • y=0 な点は高々1つであること

それさえ満たしていれば解は出る、のかな

全ての点が y\ge0 にあるなら上下反転してもよさげ

凸包を作って周囲をなぞっていく?とか考えたけど
すべての点を含む円の中心が(cx,cy)にあるとすると(円の半径r = cy)、

  • cxに関しては下に凸な関数だから三分探索(ないし黄金分割探索)で
  • cy (=r) に関しては小さければ小さいほど良くて、ある一点を境に可能・不可能が決まるので二分探索で

で行けるかな
区間が短くなる速度は三分探索だと1ステップに2/3=0.666倍、黄金分割探索だと1ステップに(1+√5)/2=0.618倍なので黄金分割探索を使っていこう。

→TLE
http://codeforces.com/contest/1059/submission/43874944

  • 必要な精度から黄金分割探索と二分探索のループ数を計算して (64,77)

→TLE
http://codeforces.com/contest/1059/submission/43875191

  • ループ数もうちょい減らす (56, 67)
  • hypot使うのやめて二乗どうしで比較しよう
  • long double使わなくてもよくね?

→AC
http://codeforces.com/contest/1059/submission/43875724