test/search/golden_section_search/2.test.cpp

• View this file on GitHub
• Last update: 2021-08-11 13:32:54+09:00
• Problem: https://yukicoder.me/problems/no/306

Depends on

• Golden section search (include/search/golden_section_search.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/306"
#define ERROR 1e-6
#include <cmath>
#include <iomanip>
#include <iostream>

#include "../../../include/search/golden_section_search.hpp"

int main() {
  long double x_a, y_a, x_b, y_b;
  std::cin >> x_a >> y_a >> x_b >> y_b;

  const long double x_a_2 = x_a * x_a;
  const long double x_b_2 = x_b * x_b;

  const auto l = [&](const long double y) -> long double {
    const long double y_a_1 = y - y_a;
    const long double y_b_1 = y - y_b;
    return -std::sqrt(y_a_1 * y_a_1 + x_a_2) - std::sqrt(y_b_1 * y_b_1 + x_b_2);
  };

  std::cout << std::fixed << std::setprecision(10)
            << lib::golden_section_search<false>(-100.0L, 1100.0L, l).first << '\n';
}

#line 1 "test/search/golden_section_search/2.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/306"
#define ERROR 1e-6
#include <cmath>
#include <iomanip>
#include <iostream>

#line 1 "include/search/golden_section_search.hpp"

//! @file golden_section_search.hpp

#ifndef CP_LIBRARY_GOLDEN_SECTION_SEARCH_HPP
#define CP_LIBRARY_GOLDEN_SECTION_SEARCH_HPP

#include <cassert>
#line 9 "include/search/golden_section_search.hpp"
#include <type_traits>
#include <utility>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

//! @brief Function to find the maximum or minimum value of a convex function f(x) when x is in [a, b]
//! @tparam minimize Set to true if you want to minimize the f(x), otherwise set to false.
//! @tparam RealType type of x (deduced from parameters)
//! @tparam Func type of f (deduced from parameters)
//! @param low lower bound (a)
//! @param high upper bound (b)
//! @param f function to minimize or maximize
//! @param diff acceptable error
//! @return std::pair { argmin(f(x)), min(f(x)) } (or argmax & max)
//! @note time complexity: O(log((high - low) / diff * (time needed to calculate f(x))))
template <bool minimize, typename RealType, typename Func>
[[nodiscard]] auto golden_section_search(RealType low, RealType high, const Func& f, const RealType diff = 1e-9L) {
  using F_ResType = decltype(f(std::declval<RealType>()));
  CP_LIBRARY_ASSERT(low <= high);

  using std::sqrt;
  const RealType phi        = (1 + sqrt(RealType(5.0L))) / 2;
  const RealType phi_plus_1 = phi + 1;

  RealType mid_low     = (low * phi + high) / phi_plus_1;
  RealType mid_high    = (low + high * phi) / phi_plus_1;
  F_ResType score_low  = f(mid_low);
  F_ResType score_high = f(mid_high);

  while (high - low > diff) {
    if (minimize ^ (score_low < score_high)) {
      low        = mid_low;
      mid_low    = mid_high;
      score_low  = score_high;
      mid_high   = (low + high * phi) / phi_plus_1;
      score_high = f(mid_high);
    } else {
      high       = mid_high;
      mid_high   = mid_low;
      score_high = score_low;
      mid_low    = (low * phi + high) / phi_plus_1;
      score_low  = f(mid_low);
    }
  }

  return std::pair {low, score_low};
}

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_GOLDEN_SECTION_SEARCH_HPP
#line 8 "test/search/golden_section_search/2.test.cpp"

int main() {
  long double x_a, y_a, x_b, y_b;
  std::cin >> x_a >> y_a >> x_b >> y_b;

  const long double x_a_2 = x_a * x_a;
  const long double x_b_2 = x_b * x_b;

  const auto l = [&](const long double y) -> long double {
    const long double y_a_1 = y - y_a;
    const long double y_b_1 = y - y_b;
    return -std::sqrt(y_a_1 * y_a_1 + x_a_2) - std::sqrt(y_b_1 * y_b_1 + x_b_2);
  };

  std::cout << std::fixed << std::setprecision(10)
            << lib::golden_section_search<false>(-100.0L, 1100.0L, l).first << '\n';
}

Back to top page