题解 | qcjj寄快递

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using pdd = pair<double,double>;
constexpr double eps = 1e-10;
vector<pdd> num;

double calc(double k,double e) {
    return 2*k+2*e/pow(2,k);
}

double f(double x,double y,double xi,double yi) {
    double ei = sqrt((xi-x)*(xi-x)+(yi-y)*(yi-y));
    //cout << ei << endl;
    double l = 0.0,r = 15.0;
    double lmid,rmid;
    while(r - l > eps) {
        double mid = (l+r)/2;
        lmid = mid - eps;
        rmid = mid + eps;
        if(calc(lmid,ei) < calc(rmid,ei)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    //cout << r << endl;
    return calc((l+r)/2,ei);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;cin >> n;
    num.resize(n);
    for(int i = 0;i<n;i++) {
        cin >> num[i].first >> num[i].second;
    }

    double ans = 0;
    for(int i = 1;i<n;i++) {
        ans += f(num[i-1].first,num[i-1].second,num[i].first,num[i].second);
    }

    cout << std::fixed << std::setprecision(10) << ans << endl;
}

虽然本题求导的方法更优，但是在碰到一些较难求导的函数时，三分法求单峰函数的极值有奇效