max/min 斜率问题

现在已知一堆点 \((t_i,a_i)\)。要求所有点对组成直线的 Max/min 斜率。（绝对值）

Max

我们考虑找一道类似的题目：P11021。

这道题求的是 max，支持修改。此时结论为：答案来自于所有 \(t_i\) 相邻的点。如此我们直接 set 维护修改就做完了。

考虑正确性。对于 \((i,i+1)\)，我们想找到更优的 \(j>i+1\)，使得 \(k_{(i,j)}>k_{(i,i+1)}\)。这是容易构造的，直接把 \(j\) 的 y 值弄得特别大就行了。

但是此时一定有 \(k_{(i+1,j)}>k_{(i,j)}\)。并且具有传递性。证明类似斜优。所以最后答案一定被 \(k_{(j-1,j)}\) 取到。

Bonus：求 min？

Min

问题是对称的，我们把坐标系的 xy 翻转即可，所以结论是：答案来自于所有 \(y_i\) 相邻的点。