题目理解

我们有一个坐标系，原点(0,0)是飞船位置，有n条线段（线段兽），每条线段有两个端点。我们可以从原点发射最多k条射线（任意角度），每条射线可以击中它穿过的所有线段。目标是最大化被击中的线段数量，且每条线段只能被击中一次。

关键观察：

• 从原点看，每条线段对应一个角度区间
• 如果两条线段的角度区间有重叠，那么可以用同一条射线同时击中它们
• 问题转化为：在圆上选择最多k个点（射线方向），覆盖尽可能多的区间

算法思路

1. 角度表示与离散化

代码中使用了一个巧妙的方法：用叉积来表示角度关系。对于点(x,y)，从原点看的角度可以用向量(x,y)表示。通过叉积 a.x*b.y - a.y*b.x 来判断两个向量的相对方向：

• 如果 a*b < 0，说明a在b的顺时针方向
• 如果 a*b > 0，说明a在b的逆时针方向
• 如果 a*b = 0，说明a和b共线

这样就把角度比较转化为了向量叉积的比较。

2. 区间转换

对于每条线段，计算两个端点对应的角度，形成一个角度区间。由于射线是直线，线段的角度区间应该是"较短"的那一边（不超过180度）。

在代码中，通过排序和离散化，把所有的角度点映射到1..siz的整数坐标上，这样每条线段就变成了一个离散区间 [seg[i].first, seg[i].second]。

3. 预处理

• cnt[i]：有多少条线段覆盖了角度点i
• lft[i]：所有以i为右端点的区间中最小的左端点

4. 动态规划

核心状态转移：

dp[i] = max(dp[i], dp[lft[i]-1] + cnt[i])

这里dp[i]表示考虑前i个角度点时的最大覆盖线段数。转移的含义是：在角度i处放置一条射线，可以覆盖cnt[i]条线段，但是这些线段必须从lft[i]开始才能被完全包含。

由于最多可以发射k次，所以进行k轮DP，每轮都是：

1. 从右往左更新：dp[i] = max(dp[i], dp[lft[i]-1] + cnt[i])
2. 从左往右更新：dp[i] = max(dp[i], dp[i-1])（前缀最大值）

复杂度分析

• 离散化：O(n log n)
• 预处理：O(n)
• DP：O(k × n)

对于n=500000，k=100的情况，总复杂度约为O(kn) = 5e7，可以接受。

代码关键点解释

// 角度比较：通过叉积判断相对方向
friend bool operator < (const Point &a, const Point &b) {
    return a * b < 0;
}

// 离散化：把所有角度点排序去重
sort(arr.begin(), arr.end(), [](const Point & a, const Point & b)->bool{return a * b < 0;});

// 区间处理：确保first <= second
if (seg[i].first > seg[i].second)
    swap(seg[i].first, seg[i].second);

// DP核心
for (int j = 1; j <= K; ++j) {
    for (int i = siz; i >= 1; --i)
        dp[i] = max(dp[i], dp[lft[i] - 1] + cnt[i]);
    for (int i = 1; i <= siz; ++i)
        dp[i] = max(dp[i], dp[i - 1]);
}

总结

这道题的核心在于将几何问题转化为区间覆盖问题，然后通过离散化和动态规划求解。巧妙之处在于用叉积来处理角度关系，避免了复杂的三角函数计算，既高效又精确。

这种"几何问题→区间问题→离散化+DP"的转化思路在很多计算几何题目中都很常见，是一个很重要的解题技巧。