题解 | #【模板】实数域三分#

观察函数，发现函数 F(x) 在区间 [l, r] 上是一个单峰函数，所以可以三分，注意 eps 设置到比给定标准小一点就行

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
const double EPS = 1e-7;
int __t = 1, n;
double l, r;

struct Fx {
    int k, a, b;
};
vector<Fx> fxs;

double f(Fx fx, double x) {
    return abs(fx.k * x + fx.a) + fx.b;
}

double F(double x) {
    double sum = 0;
    for (auto fx : fxs)
        sum += f(fx, x);
    return sum;
}

void solve() {
    cin >> n >> l >> r;
    fxs.clear();
    fxs.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> fxs[i].k >> fxs[i].a >> fxs[i].b;
    while (r - l > EPS) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (F(m1) < F(m2))
            r = m2;
        else
            l = m1;
    }
    cout << fixed << setprecision(7) << F(l) << "\n";
}

int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cin >> __t;
    while (__t--)
        solve();
    return 0;
}