Treasure Hunt [Summer Festival Contest 4]

コンテスト: https://hoj.hamako-ths.ed.jp/onlinejudge/contest/106/problems/4
アーカイブ： https://hoj.hamako-ths.ed.jp/onlinejudge/problems/825

必要知識

• 三分探索

解説

https://hoj.hamako-ths.ed.jp/onlinejudge/state/25959

端を取る地点について三分探索をする。
端を掛ける地点は2つあるので、[A,B]の部分に橋を掛けるときのx座標を決めた時の[C,D]の部分に橋をかける時のx座標を決める時は総移動距離のグラフは凹の形になる。
これを三分探索で求める。
あとは、その関数自体が凹の形になることから更に三分探索をすれば答え。
TLが割と厳しく（その代わりに誤差が甘い？）、三分探索の時のループを70回にしたら通った。

template<typename Func>
double findMinReal(double L, double R, Func f) { //[L, R)
    double left = L, right = R;
 
    for (int loop = 0; loop < 70; ++loop) {
        if (f((left * 2 + right) / 3) <= f((left + right * 2) / 3)) {
            right = (left + right * 2) / 3;
        }
        else {
            left = (left * 2 + right) / 3;
        }
    }
    return (right + left) * 0.5;
}
//---------------------------------------------------------------------------------------------------


int N, A, B, C, D;
int P[10101], Q[10101], R[10101], S[10101];
//---------------------------------------------------------------------------------------------------
double x1;
double ans2;
double g(double x) {
    double res = 0;
    rep(i, 0, N) {
        res += sqrt((R[i] - x) * (R[i] - x) + (S[i] - D) * (S[i] - D));
        res += sqrt((x - x1) * (x - x1) + (B - C) * (B - C));
    }
    return res;
}
double f(double x) {
    x1 = x;
    ans2 = findMinReal(0, 10001, g);
 
    double res = g(ans2);
    rep(i, 0, N) {
        res += sqrt((P[i] - x) * (P[i] - x) + (Q[i] - A) * (Q[i] - A));
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B >> C >> D;
    rep(i, 0, N) cin >> P[i] >> Q[i] >> R[i] >> S[i];
 
    double ans1 = findMinReal(0, 10001, f);
    f(ans1);
     
    printf("%.10f %.10f\n", ans1, ans2);
}