三分法

 参考算法学习笔记(62): 三分法 - 知乎

众所周知，二分法主要用来求函数的零点，那么三分法是二分法的变种，主要用来求单峰函数的极值点。

三分法的原理非常简单，每次对一个区间[l,r]求三等分点lsec和rsec：l = l + lsec, r = r - rsec.

 

例题F-牛牛战队的比赛地_牛客2025秋季算法编程训练联赛5-基础组

查看代码

#include<bits/stdc++.h>
using namespace std;
#define ll long longvector<pair<int, int>> v;double clc(double x){double maxn = 0;for(auto& [x1, y1] : v){double d = sqrt((x1 - x) * (x1 - x) + y1 * y1);if(d > maxn) maxn = d;}return maxn;
}void solve(){int n, x, y;cin >> n;for(int i = 1; i <= n; ++i){cin >> x >> y;v.emplace_back(x, y);}double l = -40000, r = 40000;while(r - l >= 1e-8){double lmid = l + (r - l) / 3;double rmid = r - (r - l) / 3;if(clc(lmid) <= clc(rmid)) {//ans = r;r = rmid;}else l = lmid;}cout << clc((l + r) / 2) << endl;return ;
}

题目中出现了“最大的最小”、“最小的最大”等字眼，一般情况都需要二分的写法，本题求最大距离距离的最小值，求的是极小值，我们可以用三分法来求解。

这段代码的核心思路是用三分法求解 “最大距离最小化” 问题。每次取[l, r]之间的三等分点比较

• 比较两点的 “最大距离”（通过clc函数计算）：
• 若clc(lmid) <= clc(rmid)：说明最优解在左区间，缩小右边界r = rmid
• 否则：说明最优解在右区间，缩小左边界l = lmid。

最后答案在更新后的[l, r]区间内。