Points to Cost [第六回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202104-open/tasks/past202104_j

前提知識

• 三分探索

解説

https://atcoder.jp/contests/past202104-open/submissions/22655262

数学の知識と「三分探索」というのを知っているかという問題。
三分探索が分からない場合は別所で勉強してきてほしい。（ここで話すには少し長くなる）

まず、考え始めとして小数での最小値というのを求める方法は結構限られているので、
記憶から解き方を引っ張り出してきて解法を1つ1つ当てはめていくと「三分探索」が引っかかる。

三分探索の前に

数式が与えられている場合はきれいにできないかを考えてみよう。
「(p-X[i])² + (C-Y[i])²」の総和を考えているが、後半部分はどんなpであっても固定なので、とりあえず無視して考える。
（無視しておいても後から足せばいい）
「(p-X[i])²」の総和だが、これは二次関数の総和となっている。
二次関数の総和は二次関数となる。
二次関数ということは「凸性」を持つということになる。
これが重要で、凸性を持つということは三分探索が使えるということである。

三分探索

自分は三分探索用のライブラリを作成しているので、それを通して計算している。
自分の必要なら自分の提出コードから中身を見てみてほしい。

三分探索の範囲は制約から持ってきて、[-10⁵,10⁵]でやろう。
評価関数は先ほど無視した定数部分も入れて、普通にプログラムで指定されているコスト計算式を使えばいい。

int N, C, X[201010], Y[201010];
//---------------------------------------------------------------------------------------------------
double f(double p) {
    double res = 0;
    rep(i, 0, N) res += (p - X[i]) * (p - X[i]) + 1.0 * (C - Y[i]) * (C - Y[i]);
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    double opt = findMinReal(-1e5, 1e5, f);
    printf("%.10f\n", f(opt));
}