「POI2018 R3」两个棋子 Two stones 题解

算法思路分析

这是一个几何优化问题，需要将 $n$ 个移动向量分配给两个棋子，最大化它们最终位置的欧几里得距离的平方。

关键观察

1. 问题转化：为每个向量分配权重 $w_i \in \{-1, 0, 1\}$，使得 $\left\|\sum w_i \vec{v}_i\right\|^2$ 最大
2. 几何性质：最优解中，选择的向量在角度上集中在不超过 $180^\circ$ 的范围内
3. 环状扫描：通过角度排序和滑动窗口找到最优解

核心算法：角度排序 + 滑动窗口

算法步骤

1. 向量预处理

For(i, 1, n) {
    a[i].x = read(), a[i].y = read();
    if(!a[i].x && !a[i].y)  // 去除零向量
        i--, n--;
    else 
        a[i].jiao = atan2(a[i].y, a[i].x);  // 计算极角
}

2. 向量扩展（处理负权重）

For(i, 1, n) {
    a[i+n].x = -a[i].x, a[i+n].y = -a[i].y;  // 创建负向量
    if(a[i].jiao >= 0)
        a[i+n].jiao = a[i].jiao - pi;  // 调整负向量的角度
    else
        a[i+n].jiao = a[i].jiao + pi;
}
n *= 2;  // 现在n个向量代表原始向量和它们的负向量

数学原理：权重 $w_i = -1$ 等价于使用负向量

3. 角度排序

sort(a+1, a+n+1, [&](node x, node y) {
    return x.jiao < y.jiao;  // 按极角排序
});

4. 环状数组构造

For(i, n+1, n+n) 
    a[i] = a[i-n], a[i].jiao += 2*pi;  // 复制一份并调整角度

5. 滑动窗口扫描

int r = 1;
ll dx = 0, dy = 0, ans = 0;
For(i, 1, n) {
    // 扩展右边界，保持窗口内角度差 < π
    while(r < i + n/2 && a[r].jiao - a[i].jiao < pi) {
        dx += a[r].x, dy += a[r].y;
        ans = max(ans, dx*dx + dy*dy);
        r++;
    }
    // 移动左边界
    dx -= a[i].x, dy -= a[i].y;
    ans = max(ans, dx*dx + dy*dy);
}

算法正确性证明

关键定理

最优解对应的向量在角度排序后必然形成一个连续的区间（模 $2\pi$），且区间长度不超过 $\pi$。

证明思路：

• 如果选择的向量在角度上分散超过 $180^\circ$，可以通过调整权重使它们更集中，从而增大合向量的模长
• 滑动窗口保证检查所有可能的连续区间

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自排序
• 空间复杂度：$O(n)$，存储扩展后的向量数组

算法标签

主要分类

• 计算几何 ⭐⭐⭐⭐⭐
• 滑动窗口 ⭐⭐⭐⭐
• 极角排序 ⭐⭐⭐⭐

技术子标签

• 环状数组 ⭐⭐⭐⭐
• 向量运算 ⭐⭐⭐⭐
• 连续区间优化 ⭐⭐⭐⭐

问题类型

• 组合优化 ⭐⭐⭐⭐
• 最大模长 ⭐⭐⭐⭐
• 权重分配 ⭐⭐⭐⭐

关键算法技巧

1. 负向量处理

通过创建负向量，将三值权重 $\{-1, 0, 1\}$ 问题转化为二值权重 $\{0, 1\}$ 问题

2. 环状扫描

// 构造环状数组，便于处理角度环绕
For(i, n+1, n+n) a[i] = a[i-n], a[i].jiao += 2*pi;

3. 角度约束

保持窗口内角度差严格小于 $\pi$，确保向量方向相对集中

4. 实时更新

在窗口扩展和收缩时动态维护向量和，并更新最优解

样例验证

对于样例输入：

3
-1 3
-1 -2  
4 0

算法过程：

1. 创建负向量，得到6个向量
2. 按角度排序
3. 滑动窗口扫描，找到最优组合
4. 输出最大距离平方 $41$

算法优势

1. 最优性保证：基于几何性质，找到全局最优解
2. 高效性：$O(n \log n)$ 处理 $n \leq 2 \times 10^5$ 的数据
3. 简洁性：通过巧妙的向量扩展简化问题
4. 鲁棒性：处理各种向量分布情况

该解法通过几何洞察和滑动窗口技术，成功解决了大规模向量分配问题，展现了计算几何在组合优化中的强大应用。