POI2018 R1「棋子 Stone」题解

题目大意

在无限网格的 $(0,0)$ 点有一个棋子，有 $n$ 个移动向量 $[x_i, y_i]$，每个向量最多使用一次，可以按任意顺序使用。目标是让棋子最终位置离原点 $(0,0)$ 的欧几里得距离平方最大。

问题分析

关键观察

• 交换律性质：最终位置只取决于选择了哪些向量，与使用顺序无关
• 目标函数：最大化 $(\sum x_i)^2 + (\sum y_i)^2$
• 问题转化：从 $n$ 个向量中选子集，使得和向量的模长平方最大

核心结论

定理：存在一个方向，使得选择所有在该方向半平面内（包括边界）的向量能得到最优解。

几何解释：

• 如果向量分散在不同方向，它们会相互抵消
• 集中在某个半平面内能最大化合成向量的模长
• 最优解对应的向量都在某个 $180^\circ$ 的扇形区域内

直观理解：想象把所有向量投影到某个方向上，选择那些投影为正的向量，这样它们的贡献会累加而不是抵消。

算法思路

核心思想

对于任意方向，考虑选择所有与该方向夹角不超过 $90^\circ$ 的向量（即点积非负的向量）。我们需要找到最优的方向。

关键技巧：最优方向一定出现在某个向量的边界方向（即与该向量垂直的方向）。

算法步骤

1. 事件构造：

   • 对于每个非零向量 $p = (x,y)$，计算两个边界方向：
     • 左边界 $L = (-y, x)$：$p$ 逆时针旋转 $90^\circ$
     • 右边界 $R = (y, -x)$：$p$ 顺时针旋转 $90^\circ$
   • 在角度 $L$ 处加入向量 $p$，在角度 $R$ 处移除向量 $p$
   • 处理跨越 $0^\circ$ 的特殊情况

2. 极角排序：将所有事件按极角排序

3. 扫描过程：

   • 初始化当前向量和 $(0,0)$
   • 按顺序处理事件，维护当前向量和
   • 每次更新后计算距离平方并更新答案

为什么这样工作？

当扫描线旋转时，当前集合包含所有与扫描线方向夹角不超过 $90^\circ$ 的向量。由于最优解对应某个半平面，我们一定会在某个事件点遇到最优解对应的集合。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
};

// 向量运算
P operator+(P a, P b) { return {a.x + b.x, a.y + b.y}; }
P operator-(P a) { return {-a.x, -a.y}; }
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }
ll det(P a, P b) { return a.x * b.y - a.y * b.x; }
ll len2(P a) { return a.x * a.x + a.y * a.y; }

// 极角排序：按逆时针方向
bool operator<(P a, P b) {
    int qa = a.y < 0 || (a.y == 0 && a.x < 0);
    int qb = b.y < 0 || (b.y == 0 && b.x < 0);
    if (qa != qb) return qa < qb;
    return det(a, b) > 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<pair<P, P>> events;
    
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        if (x == 0 && y == 0) continue;
        
        P p = {x, y};
        P L = {-y, x};  // 左边界：p逆时针90度
        P R = {y, -x};  // 右边界：p顺时针90度
        
        if (L < R) {
            // 不跨越0度：直接添加区间[L, R]
            events.push_back({L, p});
            events.push_back({R, -p});
        } else {
            // 跨越0度：分成[0,R]和[L,360)两段
            events.push_back({{1, 0}, p});
            events.push_back({R, -p});
            events.push_back({L, p});
        }
    }
    
    if (events.empty()) {
        cout << "0\n";
        return 0;
    }
    
    // 按极角排序事件
    sort(events.begin(), events.end(), [](auto &a, auto &b) {
        return a.first < b.first;
    });
    
    P cur = {0, 0};
    ll ans = 0;
    
    // 扫描事件
    for (auto &[angle, vec] : events) {
        cur = cur + vec;
        ans = max(ans, len2(cur));
    }
    
    cout << ans << "\n";
    return 0;
}

算法正确性证明

关键引理

对于任意向量集合，最大模长的向量和可以通过选择某个方向半平面内的所有向量得到。

证明概要

假设最优解集合为 $S$，和向量为 $v$。

1. 反证法：如果存在 $u \in S$ 与 $v$ 夹角大于 $90^\circ$，则 $u \cdot v < 0$
2. 从 $S$ 中移除 $u$，新和向量 $v' = v - u$ 满足：$$\|v'\|^2 = \|v\|^2 + \|u\|^2 - 2u \cdot v > \|v\|^2 $$
3. 这与 $v$ 是最优解矛盾
4. 因此 $S$ 中所有向量与 $v$ 夹角不超过 $90^\circ$，即都在 $v$ 方向的半平面内

扫描正确性

由于最优解对应某个半平面，而我们的扫描会枚举所有可能的半平面边界（即与某个向量垂直的方向），因此一定会遇到最优解。

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 事件排序：$O(n \log n)$
  • 扫描过程：$O(n)$
• 空间复杂度：$O(n)$

样例解析

样例输入

5
2 -2
-2 -2
0 2
3 1
-3 1

计算过程

最优解之一：选择 $[0,2]$, $[3,1]$, $[2,-2]$

和向量：$(0+3+2, 2+1-2) = (5, 1)$

距离平方：$5^2 + 1^2 = 25 + 1 = 26$

输出：26

边界情况处理

1. 所有向量为零：直接输出 0
2. 向量重复：算法自动处理，每个向量独立考虑
3. 大数值：使用 long long 防止溢出
4. 精度问题：全程使用整数运算，避免浮点误差

总结

本题核心技巧

• 半平面性质：将组合优化转化为几何性质
• 极角扫描：通过扫描边界方向来枚举所有候选解
• 事件驱动：用加入/移除事件维护当前集合