ABC130 Task F. Minimum Bounding Box

题目链接
题解


最小的 bounding box 一定可以在四个时间段的最左端点和最右端点之间取到。
举例言之,设四个时间段分别是 (2, 5), (7, 10), (4, 9), ( 10, 20);
则最小的 bounding box 一定可以在 (2, 20) 这段时间内取到,我们只需要考虑这段时间就可以了。
进一步,考虑 (2, 4) (4, 5) (5, 7) (7, 9), (9, 10), (10, 20) 这几个小段,在每个小段内 $x_{ ext{max}}$,$x_{ ext{min}}$,$y_{ ext{max}}$,$y_{ ext{min}}$ 的变化率(导数)都是常数。
非官方题解

若 $f$ 和 $g$ 是分段线性的连续函数且函数值非负,则 $fg$ 的最小值必定可以在 $f$ 或 $g$ 的不光滑点(即不可导点)取到。

考虑 $fg$ 的二阶导数。
$(fg)'' = (f'g + fg')' = 2f'g' + f''g + fg''$
由于 $f$ 和 $g$ 是分段线性的,在 $f$ 和 $g$ 都光滑的区间内 $f''$ 和 $g''$ 都是零,$f', g'$ 都是常数。
当 $f'$ 和 $g'$ 都大于等于零或都小于等于零时 $fg$ 是单调的,否则 $fg$ 的二阶导数小于零,$fg$ 是上凸的。无论如何,$fg$ 的最小值都在不可导点取到。

Implementation

原文地址:https://www.cnblogs.com/Patt/p/11853624.html