BZOJ1857, HDU3400 – 传送带问题（三分套三分）

OI中有种暴力的解法就是把区间离散化，是可以过部分数据的。
在搞清这题的AC算法之前先要搞清一个问题，如何求单峰函数的极值。

假设我们要求一个单峰函数 $ f(x) $ 在区间 $ [a,b] $ 上的极值，如图所示。函数图像上两点 $ P(x_p,y_p) , Q(x_q,y_q) $ 保证 $ [x_p,y_p] ⊂ [a,b] $。因为函数是单峰的，如果有 $ y_p > y_q $，则可以断定极值点一定不在 $ P $ 左边。这一点很重要。这意味着我们可以缩小区间范围。缩小范围的方法就是把区间不断三分，比较两个分点，舍去三个区间其中一个子区间。当区间长度小于一个绝对小的数的时候，我们可以认为找到了这个极值点，当然这个绝对小的数也是人为定义的，它可以是1E-4等等。
那么我们再来看这一题。为了达到最少的时间，首先不能出现来回走的路径，所以我们的路径一定是这样的：经过AB上一点S，经过CD上一点T，整个路径就是A->S->T->D，下面我们考虑如何让这条路径最优（时间最短）。


假设S是一个定点，那么我们只要考虑路径S->T->D最优，通过画图可以发现这条路径所用的时间关于T点位置的函数是单峰的，也就是说T点的位置如果从C到D一一枚举，耗费的时间会经过一个先递减再递增的过程（这里的单峰有猜测的因素，不过也可以给出严格的证明），那么要找到这条路径的最优解，需要对CD线段进行三分。
同理，S作为动点时，路径A->S->T->D耗费的时间关于S点位置的函数也是单峰的。所以我需要对AB线段进行三分，确定最优的S点。因此，水到渠成，三分套三分。