/** * @brief 黄金比分割探索 * @author えびちゃん */ #ifndef H_ternary_search #define H_ternary_search #include #include template std::pair optimize_convex(Fn&& f, Tp xl, Tp xu, Tp err, bool maximize = true) { // Returns {argmin f(x), min f(x)}. Tp const phi = (1 + std::sqrt(static_cast(5))) / 2; int const iter = (std::log(xu-xl) - std::log(err)) / std::log(phi) + 1; Tp xml = (phi * xl + xu) / (1 + phi); Tp xmu = (xl + phi * xu) / (1 + phi); Tp yml = f(xml); Tp ymu = f(xmu); for (int i = 0; i < iter; ++i) { if (!maximize ^ (yml > ymu)) { xu = xmu; xmu = xml; ymu = yml; xml = (phi * xl + xu) / (1 + phi); yml = f(xml); } else { xl = xml; xml = xmu; yml = ymu; xmu = (xl + phi * xu) / (1 + phi); ymu = f(xmu); } } return std::make_pair(xml, yml); } #endif /* !defined(H_ternary_search) */ #include #include int main() { long double xa, ya, xb, yb; scanf("%Lf %Lf %Lf %Lf", &xa, &ya, &xb, &yb); auto f = [&](auto y) { return std::hypot(xa, y-ya) + std::hypot(xb, yb-y); }; long double y = optimize_convex(f, 0.0L, 1e3L, 1e-6L, false).first; printf("%.20Lf\n", y); }