原神大王系列怎么没有这道题？

考虑把 $(\sum a, \sum b)$ 作为一个生成树的坐标，那么这个点的贡献就是它和原点围成的面积。

这样的问题有一个经典结论是有可能成为答案的点一定构成一个下凸包。

然后有这么一个算法叫 QuickHull。具体地，先求出 $\sum a$ 最小的点 $A$ 和 $\sum b$ 最小的点 $B$，然后找一个离 $A, B$ 最远的点 $C$。$A, B$ 可以直接最小生成树求。

这个条件可以看成 $S_{\triangle ABC}$ 最大化，用向量叉乘的式子画一画发现要最小化 $(x_B - x_A)y_C + (y_A - y_B)x_C$ 加上一堆常量，那令一条边的权值是 $b\times (x_B - x_A) + a\times (y_A - y_B)$ 跑最小生成树即可。当求出来的这个值 $\ge 0$ 的时候说明直线左下方没有点了，停止；否则递归处理 $(A, C), (C, B)$ 之间的情况。

据说这样凸包上点的期望个数是 $\mathcal O((na)^{\frac{2}{3}})$ 个。