kyopro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub dyktr06/kyopro_library

:warning: lib/others/golden_section_search.hpp

Code

#pragma once

// l <= r, ret: min
template <typename T>
pair<long long, long long> golden_section_search(long long l, long long r, T check){
    long long a = l - 1, x, b;
    {
        // fibonacci
        long long s = 1, t = 2;
        while(t < r - l + 2){
            s += t;
            swap(s, t);
        }
        x = a + t - s;
        b = a + t;
    }
    long long fx = check(x), fy;
    while(a + b != x * 2){
        long long y = a + b - x;
        if(r < y || fx < (fy = check(y))){
            b = a;
            a = y;
        }else{
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}
#line 2 "lib/others/golden_section_search.hpp"

// l <= r, ret: min
template <typename T>
pair<long long, long long> golden_section_search(long long l, long long r, T check){
    long long a = l - 1, x, b;
    {
        // fibonacci
        long long s = 1, t = 2;
        while(t < r - l + 2){
            s += t;
            swap(s, t);
        }
        x = a + t - s;
        b = a + t;
    }
    long long fx = check(x), fy;
    while(a + b != x * 2){
        long long y = a + b - x;
        if(r < y || fx < (fy = check(y))){
            b = a;
            a = y;
        }else{
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}
Back to top page