如何高效求解给定向量集可实现的最大欧氏距离平方

题目描述 #

这是波兰信息学奥林匹克（PIO）中的一道名为Pionek的题目。给定一组可重复的向量，每个向量仅能使用一次，求从原点(0,0)出发移动后能达到的最大欧氏距离的平方。

约束条件 #

• 每个向量[x, y]满足 (10^{-4} \leq x,y \leq 10^4)
• 向量数量 (n \leq 200000)
• 内存限制为128MB

示例输入 #

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

选择向量[0,2]、[3,1]、[2,-2]可得到最优结果，最终点为(5,1)，欧氏距离平方为26。

暴力解法（超时） #

#include <iostream>
#include <vector>

using namespace std;

long long solve(const vector<pair<int, int>>& points, int i, int x, int y) {
    if (i == points.size())
        return 1LL * x * x + 1LL * y * y;

    long long ans = 0;
    ans = max(solve(points, i + 1, x, y), solve(points, i + 1, x + points[i].first, y + points[i].second));
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> points(n);
    for (int i = 0; i < n; ++i)
        cin >> points[i].first >> points[i].second;

    cout << solve(points, 0, 0, 0);
}

该解法时间复杂度为 (O(2^n))，对于 (n=2e5) 完全无法通过，记忆化又会超出内存限制。

高效解法思路（O(nlogn)） #

这个问题的核心是转化为向量子集和的最大模长平方，可通过以下步骤解决：

1. 问题本质 #

欧氏距离平方即最终点 ((X,Y)) 的 (X^2 + Y^2)，我们需要选择部分向量，使得这个值最大。

2. 核心策略：随机方向采样+贪心选择 #

最优子集的和向量 (S) 的方向是关键——若我们采样到与 (S) 接近的方向，那么所有属于最优子集的向量在该方向上的投影必为正（否则加入投影为正的向量会让模长更大），不在最优子集的向量投影为负。基于此，我们可以：

• 随机采样方向：生成多个随机单位向量（比如100个），覆盖可能的最优方向；
• 按投影筛选向量：对每个采样方向，计算所有向量在该方向上的投影，选择投影为正的向量累加；
• 计算模长平方：对每个筛选后的子集，计算其和向量的模长平方，记录最大值。

3. 为什么有效？ #

由于向量模长平方是凸函数，最大值必然出现在某个特定方向上。通过随机采样足够多的方向，能以极高概率覆盖接近最优方向的情况，从而得到正确结果。额外加入所有向量自身的方向作为采样点，可进一步确保不遗漏最优解。

4. 实现细节 #

• 随机生成单位向量：通过随机角度计算 (\cos\theta) 和 (\sin\theta)，或生成随机点后归一化；
• 投影计算：无需精确单位向量，仅需方向一致即可，避免浮点误差；
• 时间控制：每次采样遍历所有向量的复杂度为 (O(n))，100次采样总操作量为 (2e7)，完全符合时间要求。

5. 代码示例 #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));

    int n;
    cin >> n;
    vector<pii> vecs(n);
    for (int i = 0; i < n; ++i) {
        cin >> vecs[i].first >> vecs[i].second;
    }

    ll max_dist_sq = 0;

    // 随机采样100个方向
    for (int iter = 0; iter < 100; ++iter) {
        double a = (double)rand() / RAND_MAX * 2 - 1;
        double b = (double)rand() / RAND_MAX * 2 - 1;
        double len = sqrt(a*a + b*b);
        if (len < 1e-9) continue;
        a /= len;
        b /= len;

        ll sum_x = 0, sum_y = 0;
        for (auto& p : vecs) {
            double proj = a * p.first + b * p.second;
            if (proj > 0) {
                sum_x += p.first;
                sum_y += p.second;
            }
        }
        ll dist_sq = sum_x * sum_x + sum_y * sum_y;
        max_dist_sq = max(max_dist_sq, dist_sq);
    }

    // 采样所有向量自身的方向，确保覆盖最优情况
    for (auto& p : vecs) {
        double a = p.first;
        double b = p.second;
        double len = sqrt(a*a + b*b);
        if (len < 1e-9) continue;
        a /= len;
        b /= len;

        ll sum_x = 0, sum_y = 0;
        for (auto& q : vecs) {
            double proj = a * q.first + b * q.second;
            if (proj > 0) {
                sum_x += q.first;
                sum_y += q.second;
            }
        }
        ll dist_sq = sum_x * sum_x + sum_y * sum_y;
        max_dist_sq = max(max_dist_sq, dist_sq);
    }

    cout << max_dist_sq << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者Szyszka947