CF2063D Game With Triangles

即使小 John 也需要钱买房。但他最近失业了，现在该如何赚钱呢？当然是玩能获得金钱奖励的游戏！不过可能不是你想的那种游戏。平面上有 $n + m$ 个互不相同的点 $(a_1, 0), (a_2, 0), \ldots, (a_n, 0), (b_1, 2), (b_2, 2), \ldots, (b_m, 2)$。初始时你的得分为 $0$。你可以通过以下操作增加得分： - 选择三个不共线的不同点； - 将得分增加这三个点形成三角形的面积； - 从平面中删除这三个点。  游戏示例，其中执行了两次操作。设 $k_{\max}$ 表示可执行操作的最大次数。例如若无法执行任何操作，则 $k_{\max} = 0$。另外定义 $f(k)$ 为恰好执行 $k$ 次操作时可能达到的最大得分。此处 $f(k)$ 对所有满足 $0 \le k \le k_{\max}$ 的整数 $k$ 均有定义。 请找出 $k_{\max}$ 的值，并分别计算所有 $x=1,2,\ldots,k_{\max}$ 对应的 $f(x)$ 值。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 3 \cdot 10^4$）。接下来描述各个测试用例。 每个测试用例： - 第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 2 \cdot 10^5$）。 - 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$——位于 $y=0$ 直线上的点（$-10^9 \le a_i \le 10^9$）。 - 第三行包含 $m$ 个互不相同的整数 $b_1, b_2, \ldots, b_m$——位于 $y=2$ 直线上的点（$-10^9 \le b_i \le 10^9$）。 保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $2 \cdot 10^5$。

对于每个测试用例，若最大操作次数为 $k_{\max}$，则最多输出两行： - 第一行输出 $k_{\max}$ 的值； - 第二行输出 $k_{\max}$ 个整数，表示 $f(1), f(2), \ldots, f(k_{\max})$。若 $k_{\max} = 0$ 可省略此行。 注意根据题目约束，可以证明所有 $f(x)$ 的值均为不超过 $10^{16}$ 的整数。

在第一个测试用例中，共有 $1+3=4$ 个点：$(0,0)$、$(0,2)$、$(1,2)$、$(-1,2)$。 可以证明无法执行两次或更多操作。此时 $k_{\max} = 1$，只需输出 $f(1)$ 的值。选择 $(0,0)$、$(-1,2)$ 和 $(1,2)$ 作为三角形的三个顶点。操作后得分增加该三角形的面积 $2$，随后这三个点被删除。可以证明单次操作后的最大得分为 $2$，因此 $f(1) = 2$。 第五个测试用例中共有 $8+2=10$ 个点。可以证明无法执行三次或更多操作。此时 $k_{\max} = 2$，需要输出 $f(1)$ 和 $f(2)$ 的值。 要最大化单次操作的得分，可选择三点 $(198\,872\,582,0)$、$(-1\,000\,000\,000,2)$ 和 $(1\,000\,000\,000,2)$。操作后这三个点被删除。可以证明此时最大得分为 $2\,000\,000\,000$，因此 $f(1) = 2\,000\,000\,000$。 要最大化两次操作的总得分，可按以下步骤执行： 1. 选择三点 $(-509\,489\,796,0)$、$(553\,177\,666,0)$ 和 $(-1\,000\,000\,000,2)$，删除这三个点； 2. 选择三点 $(-400\,714\,529,0)$、$(564\,040\,265,0)$ 和 $(1\,000\,000\,000,2)$，删除这三个点。 两次操作后总得分为 $2\,027\,422\,256$。可以证明这是两次操作后的最大得分，因此 $f(2) = 2\,027\,422\,256$。 翻译由 DeepSeek R1 完成