other_algorithms/test/bisect_yuki2352.test.cpp

• View this file on GitHub
• Last update: 2025-05-06 20:50:55+09:00
• Problem: https://yukicoder.me/problems/no/2352

Depends on

• Binary search （二分探索） (other_algorithms/bisect.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/2352"
#define ERROR 1e-5
#include "../bisect.hpp"

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(10);
    int R, K;
    cin >> R >> K;
    const double pi = acos(-1);

    for (int i = 1; i < K + 1; ++i) {
        double tgt = pi / (K + 1) * i;

        auto res = bisect<double>(0, pi, [&](double c) { return c - sin(c * 2) / 2 < tgt; });
        cout << -cos(res.ng) * R << '\n';
    }
}

#line 1 "other_algorithms/test/bisect_yuki2352.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2352"
#define ERROR 1e-5
#line 2 "other_algorithms/bisect.hpp"
#include <bit>
#include <functional>
#include <numeric>

// Calculate next point to check in floating point "binary" search
double bisect_mid_fp(double a, double b) {
    auto encode = [&](double x) -> unsigned long long {
        auto tmp = std::bit_cast<unsigned long long>(x);
        return x >= 0 ? (tmp ^ (1ULL << 63)) : ~tmp;
    };

    auto decode = [&](unsigned long long x) -> double {
        auto tmp = (x >> 63) ? (x ^ (1ULL << 63)) : ~x;
        return std::bit_cast<double>(tmp);
    };

    unsigned long long tmp = std::midpoint(encode(a), encode(b));

    return decode(tmp);
}

// Binary search
// Maintain f(ok) = true and f(ng) = false and return (ok, ng)
// Final (ok, ng) satisfies |ok - ng| <= abs_tol
template <class T> auto bisect(T ok, T ng, const std::function<bool(T)> &f, T abs_tol = T()) {
    struct Result {
        T ok, ng;
    };

    while (true) {
        T mid = std::is_floating_point<T>::value ? bisect_mid_fp(ok, ng) : std::midpoint(ok, ng);
        if (mid == ok or mid == ng) break;
        (f(mid) ? ok : ng) = mid;
        if (ok - ng <= abs_tol and ng - ok <= abs_tol) break;
    }

    return Result{ok, ng};
}
#line 4 "other_algorithms/test/bisect_yuki2352.test.cpp"

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(10);
    int R, K;
    cin >> R >> K;
    const double pi = acos(-1);

    for (int i = 1; i < K + 1; ++i) {
        double tgt = pi / (K + 1) * i;

        auto res = bisect<double>(0, pi, [&](double c) { return c - sin(c * 2) / 2 < tgt; });
        cout << -cos(res.ng) * R << '\n';
    }
}

Back to top page