https://www.luogu.com.cn/problem/P9521
这题也太宇宙了！
从 \((i,j)\) 走到 \((k,l)\) 有两种方式：
- 先到 \((i,l)\) 再到 \((k,l)\)，花费 \(a_i(l-j)+b_l(k-i)\)；
- 先到 \((k,j)\) 再到 \((k,l)\)，花费 \(a_k(l-j)+b_j(k-i)\)。
移项可得，第一种方式更优等价于 \(\dfrac{b_l-b_j}{l-j}<\dfrac{a_k-a_i}{k-i}\)。把这个式子再写开一项可以发现，对于所有对答案有贡献的 \(a_i\)，\((i,a_i)\) 构成一个凸包，\(b\) 也是同理。所以把 \(a,b\) 的凸包都求出来，然后拿两个指针做类似凸包合并的过程，每次选斜率较小的那个走，就可以得到答案了！