test/aizu-online-judge/0323.test.cpp

• View this file on GitHub
• Last update: 2020-12-08 18:18:19+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/0323

Depends on

• Binary Search (src/opt/binary_search.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0323"
#define ERROR 1e-3

#include <cmath>
#include <cstdio>

#include "src/opt/binary_search.hpp"

int main() {
  int n;
  double x[1 << 17], r[1 << 17];

  scanf("%d", &n);
  for (auto i = 0; i < n; ++i) scanf("%lf%lf", x + i, r + i);

  auto isc = [&](const double d) -> bool {
    double lft = -1e6, rgt = 2e6;
    for (auto i = 0; i < n; ++i) {
      if (r[i] < d) return false;
      lft = std::max(lft, x[i] - sqrt(r[i] * r[i] - d * d));
      rgt = std::min(rgt, x[i] + sqrt(r[i] * r[i] - d * d));
    }
    return lft < rgt;
  };

  printf("%lf\n", workspace::binary_search(.0, 1e6, 1e-3, isc));
}

#line 1 "test/aizu-online-judge/0323.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0323"
#define ERROR 1e-3

#include <cmath>
#include <cstdio>

#line 2 "src/opt/binary_search.hpp"

/*
 * @file binary_search.hpp
 * @brief Binary Search
 */

#include <cassert>
#include <limits>
#include <tuple>
#include <vector>

namespace workspace {

/*
 * @fn binary_search
 * @brief binary search on a discrete range.
 * @param ok pred(ok) is true
 * @param ng pred(ng) is false
 * @param pred the predicate
 * @return the closest point to (ng) where pred is true
 */
template <class Iter, class Pred>
typename std::enable_if<
    std::is_convertible<decltype(std::declval<Pred>()(std::declval<Iter>())),
                        bool>::value,
    Iter>::type
binary_search(Iter ok, Iter ng, Pred pred) {
  assert(ok != ng);
  typename std::make_signed<decltype(ng - ok)>::type dist(ng - ok);
  while (1 < dist || dist < -1) {
    const Iter mid(ok + dist / 2);
    if (pred(mid))
      ok = mid, dist -= dist / 2;
    else
      ng = mid, dist /= 2;
  }
  return ok;
}

/*
 * @fn binary_search
 * @brief binary search on the real number line.
 * @param ok pred(ok) is true
 * @param ng pred(ng) is false
 * @param eps the error tolerance
 * @param pred the predicate
 * @return the boundary point
 */
template <class Real, class Pred>
typename std::enable_if<
    std::is_convertible<decltype(std::declval<Pred>()(std::declval<Real>())),
                        bool>::value,
    Real>::type
binary_search(Real ok, Real ng, const Real eps, Pred pred) {
  assert(ok != ng);
  for (auto loops = 0; loops != std::numeric_limits<Real>::digits &&
                       (ok + eps < ng || ng + eps < ok);
       ++loops) {
    const Real mid{(ok + ng) / 2};
    (pred(mid) ? ok : ng) = mid;
  }
  return ok;
}

/*
 * @fn parallel_binary_search
 * @brief parallel binary search on discrete ranges.
 * @param ends a vector of pairs; pred(first) is true, pred(second) is false
 * @param pred the predicate
 * @return the closest points to (second) where pred is true
 */
template <class Array,
          class Iter = typename std::decay<
              decltype(std::get<0>(std::declval<Array>()[0]))>::type,
          class Pred>
typename std::enable_if<
    std::is_convertible<
        decltype(std::declval<Pred>()(std::declval<std::vector<Iter>>())[0]),
        bool>::value,
    std::vector<Iter>>::type
parallel_binary_search(Array ends, Pred pred) {
  std::vector<Iter> mids(std::size(ends));
  for (;;) {
    bool all_found = true;
    for (size_t i{}; i != std::size(ends); ++i) {
      const Iter &ok = std::get<0>(ends[i]);
      const Iter &ng = std::get<1>(ends[i]);
      const Iter mid(
          ok + typename std::make_signed<decltype(ng - ok)>::type(ng - ok) / 2);
      if (mids[i] != mid) {
        all_found = false;
        mids[i] = mid;
      }
    }
    if (all_found) break;
    const auto res = pred(mids);
    for (size_t i{}; i != std::size(ends); ++i) {
      (res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
    }
  }
  return mids;
}

/*
 * @fn parallel_binary_search
 * @brief parallel binary search on the real number line.
 * @param ends a vector of pairs; pred(first) is true, pred(second) is false
 * @param eps the error tolerance
 * @param pred the predicate
 * @return the boundary points
 */
template <class Array,
          class Real = typename std::decay<
              decltype(std::get<0>(std::declval<Array>()[0]))>::type,
          class Pred>
typename std::enable_if<
    std::is_convertible<
        decltype(std::declval<Pred>()(std::declval<std::vector<Real>>())[0]),
        bool>::value,
    std::vector<Real>>::type
parallel_binary_search(Array ends, const Real eps, Pred pred) {
  std::vector<Real> mids(std::size(ends));
  for (auto loops = 0; loops != std::numeric_limits<Real>::digits; ++loops) {
    bool all_found = true;
    for (size_t i{}; i != std::size(ends); ++i) {
      const Real ok = std::get<0>(ends[i]);
      const Real ng = std::get<1>(ends[i]);
      if (ok + eps < ng || ng + eps < ok) {
        all_found = false;
        mids[i] = (ok + ng) / 2;
      }
    }
    if (all_found) break;
    const auto res = pred(mids);
    for (size_t i{}; i != std::size(ends); ++i) {
      (res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
    }
  }
  return mids;
}

}  // namespace workspace
#line 8 "test/aizu-online-judge/0323.test.cpp"

int main() {
  int n;
  double x[1 << 17], r[1 << 17];

  scanf("%d", &n);
  for (auto i = 0; i < n; ++i) scanf("%lf%lf", x + i, r + i);

  auto isc = [&](const double d) -> bool {
    double lft = -1e6, rgt = 2e6;
    for (auto i = 0; i < n; ++i) {
      if (r[i] < d) return false;
      lft = std::max(lft, x[i] - sqrt(r[i] * r[i] - d * d));
      rgt = std::min(rgt, x[i] + sqrt(r[i] * r[i] - d * d));
    }
    return lft < rgt;
  };

  printf("%lf\n", workspace::binary_search(.0, 1e6, 1e-3, isc));
}

Back to top page