脳log[20220628]

2022年06月28日 (火) [AtCoder] 精進。ABC151-F「Enclose All」(ギリギリ青 diff)。初めて見る問題。円をそれ以上小さくできなくなる状態がどういうものか想像すると、複数の点が円周上にあってそれ以上半径を縮めたり中心座標をずらしたりすると点が突き出てしまう均衡状態かな、と。そういう円は３点で決まるような気がしたけど４点になることがあるような気もした。テキトーな実装をする前に外接円について検索して「外接円 - Wikipedia」を読んで「最小包含円 - Wikipedia(en)」というものを知った。そこでアルゴリズムがいくつか紹介されていて、線形時間のアルゴリズムは難しかったので２番目に書かれていた Welzl's algorithm を実装した。■提出 #32821823 (AC / 992 Byte / 59 ms)。Wikipedia の言いなりに実装しただけなのでなんとも。最初の想定の答え合わせをすると、外接円は３点もしくは２点で決まるものを考えればいいのであって、４点を考える必要はなかったらしい。なんでかはわからない。垂直二等分線を引いて２点を満足させる円、３点を満足させる円を考えてみて、それから４点を満足させようとして偶然頼みになることを確認したりしてみればいいんじゃないでしょうか。■他の提出を見てみると最速級のものに「最小包含円 | libalgo」に書かれているのと同じ３重ループが目立つ。アルゴリズム的には自分が参考にした Welzl's algorithm と同じなんだろうか。自分が参考にして書いたのは再帰関数だったけど、再帰呼び出しの最奧の停止条件を初期値にして、再帰呼び出しからのリターンが多重ループへの飛び込みに対応するような、内外を裏返しにした相似構造が見える。