题目解析

问题分析

这是一个多组向量选择问题。我们有 $N$ 组向量，每组包含若干个二维向量。我们需要从每组中选择一个向量，使得所有选中向量的和的模长平方达到最大值。

数学形式化

设：

• 第 $i$ 组有 $G_i$ 个向量
• 第 $i$ 组的第 $j$ 个向量为 $\vec{v}_{ij} = (x_{ij}, y_{ij})$
• 我们需要选择索引 $j_1, j_2, \dots, j_N$，使得目标函数最大化：

$$f(j_1, j_2, \dots, j_N) = \left\|\sum_{i=1}^N \vec{v}_{ij_i}\right\|^2 $$$$= \left(\sum_{i=1}^N x_{ij_i}\right)^2 + \left(\sum_{i=1}^N y_{ij_i}\right)^2 $$

问题的挑战

1. 组合爆炸：如果直接枚举所有可能的组合，方案数为 $\prod_{i=1}^N G_i$，这在 $N$ 较大时完全不可行。

2. 数据规模：$N$ 最大为 $10^5$，向量总数最大为 $2 \times 10^5$，需要高效算法。

3. 几何特性：虽然问题看起来是组合优化，但实际上有很强的几何背景。

核心洞察

几何转化

将问题重新解释为：

• 每组向量对应二维平面上的一个点集 $S_i$
• 从每组选一个向量等价于从每个点集选一个点
• 目标是使选出的 $N$ 个点的向量和离原点最远

关键观察 1：凸包性质

对于任意方向 $\vec{d}$，点积 $\vec{v} \cdot \vec{d}$ 在集合 $S_i$ 中的最大值一定出现在该集合的凸包边界上。

证明： 设 $\vec{v}^* = \arg\max_{\vec{v} \in S_i} (\vec{v} \cdot \vec{d})$。如果 $\vec{v}^*$ 在凸包内部，那么存在凸包上的点 $\vec{v}_1, \vec{v}_2$ 和 $\lambda \in (0,1)$ 使得 $\vec{v}^* = \lambda\vec{v}_1 + (1-\lambda)\vec{v}_2$。但此时：

$$\vec{v}^* \cdot \vec{d} = \lambda(\vec{v}_1 \cdot \vec{d}) + (1-\lambda)(\vec{v}_2 \cdot \vec{d}) $$$$\leq \max(\vec{v}_1 \cdot \vec{d}, \vec{v}_2 \cdot \vec{d}) $$

矛盾。

推论：对于每组向量，我们只需要考虑其凸包上的顶点。

关键观察 2：方向性原理

对于任意固定方向 $\vec{d}$，最优选择策略很明确：每组选择在该方向上投影最远的向量。

定义方向 $\vec{d} = (\cos\theta, \sin\theta)$ 下的最优选择和向量：

$$\vec{s}(\theta) = \sum_{i=1}^N \arg\max_{\vec{v} \in \text{conv}(S_i)} (\vec{v} \cdot \vec{d}) $$

我们的目标是找到 $\theta$ 使得 $\|\vec{s}(\theta)\|^2$ 最大。

关键观察 3：分段常数性

函数 $\vec{s}(\theta)$ 是分段常数的。当 $\theta$ 连续变化时，$\vec{s}(\theta)$ 只在特定方向发生跳变。

跳变条件：当方向 $\vec{d}$ 与某个凸包边垂直时，该组的最优选择可能发生变化。

具体来说，对于凸包上的相邻顶点 $\vec{v}_a$ 和 $\vec{v}_b$，当方向 $\vec{d}$ 满足：

$$(\vec{v}_a - \vec{v}_b) \cdot \vec{d} = 0$$

即 $\vec{d}$ 与该凸包边垂直时，$\vec{v}_a$ 和 $\vec{v}_b$ 在该方向上的投影相等，最优选择可能在这两个顶点之间切换。

算法框架

步骤 1：预处理凸包

对每组 $i = 1$ 到 $N$：

1. 计算点集 $S_i$ 的凸包 $\text{conv}(S_i)$
2. 使用 Andrew 算法（时间复杂度 $O(G_i \log G_i)$）
3. 记录凸包的所有顶点和边

步骤 2：生成候选方向

收集所有可能的关键方向：

• 对于每个凸包的每条边 $\vec{e} = \vec{v}_a - \vec{v}_b$
• 计算法向量 $\vec{n} = (e_y, -e_x)$ 或 $(-e_y, e_x)$
• 归一化得到候选方向 $\vec{d} = \frac{\vec{n}}{\|\vec{n}\|}$

总候选方向数 $K = O(M)$，其中 $M$ 是向量总数。

步骤 3：极角扫描

对每个候选方向 $\vec{d}_k$：

1. 对每组 $i$，找到使 $\vec{v} \cdot \vec{d}_k$ 最大的凸包顶点 $\vec{v}_i^{(k)}$
2. 计算向量和 $\vec{s}_k = \sum_{i=1}^N \vec{v}_i^{(k)}$
3. 计算平方距离 $d_k^2 = \|\vec{s}_k\|^2 = s_{k,x}^2 + s_{k,y}^2$

步骤 4：输出结果

返回 $\max\{d_1^2, d_2^2, \dots, d_K^2\}$

复杂度分析

• 凸包计算：$\sum O(G_i \log G_i) = O(M \log M)$
• 候选方向数：$K = O(M)$
• 每个方向的处理：$O(N)$（假设已预处理每组的凸包顶点）
• 总复杂度：$O(M \log M + MN)$，但通过优化可以达到 $O(M \log M)$

优化技巧

1. 方向排序：将候选方向按极角排序，相邻方向的最优选择变化很小
2. 增量更新：在极角扫描过程中，只有少数组的最优选择会发生变化
3. 避免浮点误差：直接比较点积而不是计算角度

正确性证明

定理：全局最优解必然出现在某个候选方向 $\vec{d}_k$ 上。

证明思路：

1. 目标函数 $\|\vec{s}(\theta)\|^2$ 是 $\theta$ 的连续函数
2. $\vec{s}(\theta)$ 是分段常数函数，断点出现在候选方向处
3. 因此最大值必然出现在某个常数段内，而常数段内的函数值可以通过端点计算

总结

本题展示了如何将组合优化问题通过几何洞察转化为计算几何问题。关键步骤包括：

1. 问题转化：认识到只有凸包顶点是候选解
2. 方向分析：理解最优解的方向特性
3. 离散化：将连续的方向空间离散化为有限个关键方向
4. 高效计算：利用几何性质设计多项式时间算法

这种方法在计算几何和组合优化中具有广泛应用，特别是在处理多集合选择问题时尤为有效。