三分求单峰函数极值题解 | #qcjj寄快递#

用和逐步逼近最小值 如果, 说明是比较大的不能选择, 因此将, 反之就是

实现代码

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<PLD> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;

    auto get = [&](PLD &x, PLD &y) {
        LD d = sqrtl((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
        return d;
    };

    auto calc = [&](LD k, LD e) {
        return 2.0l * k + 2.0l * e / powl(2, k);
    };

    LD ans = 0;
    for (int i = 1; i < n; ++i) {
        PLD x = a[i - 1], y = a[i];
        LD d = get(x, y);
        LD l = 0, r = 100;
        for (int t = 0; t < 100; ++t) {
            LD mid1 = l + (r - l) / 3, mid2 = mid1 + (r - l) / 3;
            if (calc(mid1, d) > calc(mid2, d)) l = mid1;
            else r = mid2;
        }
        ans += calc(l, d);
    }

    cout << fixed << setprecision(15) << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}