和二分非常类似的一个算法，与二分不同的是
二分是单调的，而三分是一个先增后减或者先减后增
三分可以求出峰值。
注意三分一定是严格单调的，不能有相等的情况。
不过貌似只有求函数最值才用到这个东西，没有二分应用范围那么广。
「一本通 1.2 例 3」曲线
画画图可以发现，满足先减后增
图和雅礼集训里Merchant那道题非常的像，只不过那道题是最大值，可以用二分。
这道题是最小值，用三分 雅礼集训
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
double a[MAXN], b[MAXN], c[MAXN];
int n;double f(double x)
{double res = -1e9;REP(i, 0, n)res = fmax(res, a[i] * x * x + b[i] * x + c[i]);return res;
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d", &n);REP(i, 0, n) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);double l = 0, r = 1e3;while(r - l > 1e-11){double m1 = l + (r - l) / 3;double m2 = r - (r - l) / 3;if(f(m1) > f(m2)) l = m1;else r = m2;}printf("%.4lf\n", f(l));}return 0;
}「一本通 1.2 练习 3」灯泡
这道题我主要是推公式推了好久，我一直算错……
首先可以分两种情况
（1）有影子在墙上
（2）没有影子在墙上
没有影子在墙上的时候，通过计算可以得出当光线照在墙角的时候最大。
设人到墙的距离为x
这个时候我们可以得到x的上界h * D / H（相似）
这个时候就可以合并到第一种情况。
第一种情况可以推出影子长度L = x + (D * h - x * H) / (D - x)
不需要化简，只要在程序中可以算出就行了。
这个时候我就猜测，肯定在某个x是最大的。
我就把x等于各种值得情况打印了出来。
果然，有个最值。
那么就三分 。
可以看到，三分的应用是在有浮点数的题目中求最值。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;double H, h, D;
inline double f(double x)
{return x + (D * h - x * H) / (D - x);
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%lf%lf%lf", &H, &h, &D);double l = 0, r = h / H * D;while(r - l > 1e-11){double m1 = l + (r - l) / 3;double m2 = r - (r - l) / 3;if(f(m1) > f(m2)) r = m2;else l = m1;}printf("%.3lf\n", f(l));}return 0;
}bzoj 1857
这是一道省选题。
首先我先观察题目可以发现一个性质。
路径必然是从AB上走一段然后走到CD某个点上然后走到D
首先确定了AB上的一点可以用三分算出最优解
然后我就猜测AB上的点也可以用三分做。
然后就这么做了。
经过长时间的调试。
70分。
然后我就遇到了一些奇怪的问题
sqrt里面要加上EPS，不然相同的点一算为0，浮点数可能弄到负数。10分。
然后我是用参数方程写的，比较复杂，中间有个地方写错了，20分
AC了之后看别人题解发现可以同时维护x坐标的mid和y坐标的mid，且是一一对应的。
我用参数方程就复杂了，思维量和代码量都上升了。
但我懒得改了。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const double EPS = 1e-8;
struct node
{double x, y;void read() { scanf("%lf%lf", &x, &y); }
}a, b, c, d;
double p, q, r;
double cos1, sin1, cos2, sin2;inline double dis(node a, node b)
{return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + EPS);
}double f(double t1, double t2)
{node k1 = node{a.x + t1 * cos1, a.y + t1 * sin1};node k2 = node{c.x + t2 * cos2, c.y + t2 * sin2};return dis(a, k1) / p + dis(k1, k2) / r + dis(k2, d) / q;
}double f1(double t)
{double l = 0, r = dis(c, d);while(r - l > EPS){double m1 = l + (r - l) / 3;double m2 = r - (r - l) / 3;if(f(t, m1) > f(t, m2)) l = m1;else r = m2;}return f(t, l);
}int main()
{a.read(); b.read();c.read(); d.read();scanf("%lf%lf%lf", &p, &q, &r);cos1 = (b.x - a.x) / dis(a, b);sin1 = (b.y - a.y) / dis(a, b);cos2 = (d.x - c.x) / dis(c, d);sin2 = (d.y - c.y) / dis(c, d);double l = 0, r = dis(a, b);while(r - l > EPS){double m1 = l + (r - l) / 3;double m2 = r - (r - l) / 3;if(f1(m1) > f1(m2)) l = m1;else r = m2;}printf("%.2lf\n", f1(l));return 0;
}