经典问题 4 —— 最小乘积生成树（奇怪凸包上二分技巧）

问题引入： 给一个 \(n\) 个点的完全图 \(G\)，每条边有两个权值 \(a_e,b_e\)，求一个生成树 \(T\)，使得 \((\sum\limits_{e\in T}a_e)\times (\sum\limits_{e\in T}b_e)\) 最小。\(n\le 200,0\le a_e,b_e\le 255\)。

这是一类经典的问题之一，这类问题形如：你要求一个凸包，但是你能做的，只有找到凸包上一个满足某种神秘条件的点。

比如这道题。首先令整体点集为 \((\sum a_e,\sum b_e)\)，那么答案一定在下凸包上，因为反比例函数是下凸的！

我们想找到这个凸包，但是这个点集是枚不过来的，直接做不行！但是发现凸包上的点数至多为 \(O(V^{2/3})=O((nA)^{2/3})\)，所以上面的经典思路就适用了。

思考这题我们可以找到凸包上满足什么条件的点：我们能做的，只有给每条边重新赋一个权值 \(c_e=f(a_e,b_e)\)，然后求 \(\sum c_e\) 的最值。

接下来的问题就是如何利用我们手中唯一的“武器”。

第一步：找到凸包上任意两个点。

发现 \(\sum a_e\) 最小和 \(\sum b_e\) 最小的点分别都满足条件，于是可以将它们拎出来。

第二步：已知凸包上两个点 \(A,B\)（\(A\) 在 \(B\) 左边），求凸包上这两个点之间任意一个点，或报告无解。

经过观察，我们发现有一个很好的性质：全局满足 \(S_{\triangle ABC}\)（有向面积，即 \(-\frac{1}{2} \overrightarrow{AB}\times \overrightarrow{AC}\)）最大的点一定在凸包上！

于是对于每个 \(e\) 令 \(c_e=-\frac{1}{2} \overrightarrow{AB}\times \overrightarrow{AC}\)，其中 \(C(a_e,b_e)\)，即可以用上我们刚才的“武器”了！

最后，求出 \(C\) 后，递归到 \(AC\) 段和 \(CB\) 段即可。时间复杂度 \(O(n^2B)\)，其中 \(B\) 为凸包上的点数，约为 \(O((nA)^{2/3})\)，\(A=\max(a_e,b_e)\)。