コンテスト: 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); }