test/yukicoder/306/main.ternary.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/306
• Link: View error logs on GitHub Actions

Depends on

• Ternary search (Convex downwards) (Mylib/Algorithm/ternary_search_downwards.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/306"
#define ERROR 1e-6

#include <cmath>
#include <iomanip>
#include <iostream>
#include "Mylib/Algorithm/ternary_search_downwards.cpp"

namespace hl = haar_lib;

int main() {
  int xa, xb, ya, yb;
  std::cin >> xa >> ya >> xb >> yb;

  auto f =
      [&](long double p) {
        return std::hypot(xa, ya - p) + std::hypot(xb, yb - p);
      };

  auto ans = hl::ternary_search_downwards<long double>(-1000, 1000, f);

  std::cout << std::fixed << std::setprecision(12) << ans << std::endl;

  return 0;
}

#line 1 "test/yukicoder/306/main.ternary.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/306"
#define ERROR 1e-6

#include <cmath>
#include <iomanip>
#include <iostream>
#line 2 "Mylib/Algorithm/ternary_search_downwards.cpp"
#include <functional>

namespace haar_lib {
  template <typename T = double, typename Func = std::function<T(T)>>
  T ternary_search_downwards(T lb, T ub, const Func &f, int LOOP_COUNT = 100) {
    T t1 = 0, t2 = 0;

    while (LOOP_COUNT--) {
      t1 = lb + (ub - lb) / 3;
      t2 = lb + (ub - lb) / 3 * 2;

      if (f(t1) < f(t2)) {
        ub = t2;
      } else {
        lb = t1;
      }
    }

    return lb;
  }
}  // namespace haar_lib
#line 8 "test/yukicoder/306/main.ternary.test.cpp"

namespace hl = haar_lib;

int main() {
  int xa, xb, ya, yb;
  std::cin >> xa >> ya >> xb >> yb;

  auto f =
      [&](long double p) {
        return std::hypot(xa, ya - p) + std::hypot(xb, yb - p);
      };

  auto ans = hl::ternary_search_downwards<long double>(-1000, 1000, f);

  std::cout << std::fixed << std::setprecision(12) << ans << std::endl;

  return 0;
}

Back to top page