题目描述

《愤怒的小鸟变形金刚》是一款横向卷轴射击游戏，玩家从左向右移动时可以看到新的物体并尝试摧毁它们。给定所有物体的位置（二维平面上的点），你需要计算玩家在移动过程中最多能同时看到多少个物体。

为简化问题，假设以下条件：

1. 所有物体可视为二维笛卡尔坐标系中的点。
2. 玩家沿 $x$ 轴从左向右移动。
3. 玩家的视野角度为 $90$ 度，且视野关于直线 $x=p_x$ 对称，其中 $p_x$ 为玩家的 $x$ 坐标。

目标：找出玩家在 $x$ 轴上移动时，最多能同时看到的物体数量。如果两个或多个物体与玩家共线，玩家仍能看到所有物体。无需输出玩家位置（可能存在多个位置看到相同最大数量）。

输入：输入包含最多 $100$ 组测试数据。每组数据以一个正整数 $N$ （$N\le 10000$）开始，表示场景中的物体数量。接下来的 $N$ 行，每行包含两个整数 $(x_i,y_i)$ ，表示第 $i$ 个物体的坐标（$0<x_i\le 10000$ ，$0<y_i\le 500$）。输入以一行单独的 $0$ 结束。

输出：对于每组数据，输出一行一个整数，表示玩家能同时看到的最大物体数量。

样例输入：

5
2 3
6 6
9 9
11 6
14 4
0

样例输出：

4

题目分析

关键条件理解

1. 视野范围：玩家的视野是一个 $90$ 度的扇形区域，对称轴是垂直于 $x$ 轴的直线 $x=p_x$ 。这意味着玩家的视野向左和向右各扩展 $45$ 度，总共覆盖 $90$ 度的范围。
2. 可见性判断：对于一个物体 $(x_i,y_i)$ ，当玩家位于位置 $p_x$ 时，该物体可见的条件是：从玩家位置到物体的连线与水平线的夹角不超过 $45$ 度。

数学建模

设玩家位置为 $p_x$ ，物体坐标为 $(x_i,y_i)$ 。

根据几何关系：

• 物体到玩家位置的水平距离为 $|x_i-p_x|$
• 物体的垂直高度为 $y_i$ （题目保证 $y_i>0$ ）

物体可见的条件是：
$$\tan (\theta )=\frac{y_i}{|x_i-p_x|}\le \tan (45^{\circ })=1$$
即：
$$y_i\le |x_i-p_x|$$

这是一个绝对值不等式，需要分两种情况讨论：

1. 当 $x_i\ge p_x$ （物体在玩家右侧或正上方）时：
   $$y_i\le x_i-p_x\Rightarrow p_x\le x_i-y_i$$

2. 当 $x_i\le p_x$ （物体在玩家左侧或正上方）时：
   $$y_i\le p_x-x_i\Rightarrow p_x\ge x_i+y_i$$

综合两种情况，物体 $(x_i,y_i)$ 可见的条件是玩家位置 $p_x$ 满足：
$$x_i-y_i\le p_x\le x_i+y_i$$

也就是说，每个物体对应一个可见区间 $[x_i-y_i,x_i+y_i]$ ，当玩家位于这个区间内的任意位置时，该物体都是可见的。

问题转化

原问题转化为：给定 $N$ 个区间 $[L_i,R_i]$ ，其中 $L_i=x_i-y_i$ ，$R_i=x_i+y_i$ ，求一个实数点最多被多少个区间同时覆盖。

这是一个经典的区间覆盖计数问题，可以通过扫描线算法高效解决。

解题思路

扫描线算法

1. 事件点创建：对于每个物体，创建两个事件点：

   • 进入事件：在位置 $L_i=x_i-y_i$ 处，计数器 $+1$ （物体进入视野）
   • 离开事件：在位置 $R_i=x_i+y_i$ 处，计数器 $-1$ （物体离开视野）

2. 事件点排序：将所有事件点按位置从小到大排序。如果位置相同，则进入事件优先于离开事件，这是因为题目说明当玩家与物体共线时仍然可见（即区间是闭区间）。

3. 扫描计数：从左到右扫描所有事件点，维护当前可见物体数量：

   • 遇到进入事件：当前可见数 $+1$
   • 遇到离开事件：当前可见数 $-1$
   • 记录扫描过程中的最大值

4. 输出结果：最大值即为玩家能同时看到的最大物体数量。

算法复杂度

• 时间复杂度：$O(N\log N)$ ，主要来自排序操作
• 空间复杂度：$O(N)$ ，用于存储事件点

算法正确性证明

1. 覆盖区间正确性：根据几何推导，物体 $(x_i,y_i)$ 在 $p_x\in [x_i-y_i,x_i+y_i]$ 时可见，这准确地转化为区间覆盖问题。
2. 事件处理顺序：当多个事件点在同一位置时，先处理进入事件后处理离开事件，确保在端点处正确计数（闭区间特性）。
3. 最大值记录：扫描过程中记录的最大值对应了某个玩家位置能看到的最多物体数量。

注意事项

1. 坐标范围：$x_i$ 最大为 $10000$ ，$y_i$ 最大为 $500$ ，因此 $L_i$ 最小可能为负数，但这不影响算法。
2. 多组数据：最多 $100$ 组数据，每组最多 $10000$ 个物体，算法效率足够。
3. 边界情况：当玩家与物体共线时，物体仍然可见，这通过将区间视为闭区间并在排序时让进入事件优先来保证。

代码实现

// Angry Birds Transformers
// UVa ID: 13278
// Verdict: Accepted
// Submission Date: 2025-12-26
// UVa Run Time: 0.120s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        vector<pair<int, int>> events; // (位置, 类型: 1起点, -1终点)
        for (int i = 0; i < n; ++i) {
            int xi, yi;
            cin >> xi >> yi;
            events.emplace_back(xi - yi, 1);   // 进入视野
            events.emplace_back(xi + yi, -1);  // 离开视野
        }
        // 排序：位置小的在前，位置相同时起点在前（保证共线时计数正确）
        sort(events.begin(), events.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first != b.first) return a.first < b.first;
            return a.second > b.second; // 起点类型值大，先处理
        });
        int maxVisible = 0;
        int currentVisible = 0;
        for (const auto& e : events) {
            currentVisible += e.second;
            maxVisible = max(maxVisible, currentVisible);
        }
        cout << maxVisible << "\n";
    }
    return 0;
}

代码说明

1. 输入输出优化：使用 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 提高输入输出效率。
2. 事件表示：使用 pair<int, int> 存储事件，第一个元素是位置，第二个元素是类型（$1$ 表示进入，$-1$ 表示离开）。
3. 排序规则：首先按位置升序排序，位置相同时按类型降序排序（$1>-1$，确保进入事件优先）。
4. 扫描过程：遍历排序后的事件列表，更新当前可见物体数并记录最大值。
5. 输出结果：对于每组数据输出最大可见物体数。

样例验证

对于样例输入：

5
2 3
6 6
9 9
11 6
14 4

计算各物体的可见区间：

1. $(2,3)$: $[2-3,2+3]=[-1,5]$
2. $(6,6)$: $[6-6,6+6]=[0,12]$
3. $(9,9)$: $[9-9,9+9]=[0,18]$
4. $(11,6)$: $[11-6,11+6]=[5,17]$
5. $(14,4)$: $[14-4,14+4]=[10,18]$

通过扫描线算法可得最大覆盖数为 $4$ ，与样例输出一致。

总结

本题的关键在于将几何可见性问题转化为区间覆盖问题。通过分析视野的对称性和角度限制，推导出每个物体对应的可见区间，然后使用扫描线算法求解最大区间重叠数。算法时间复杂度为 $O(N\log N)$ ，空间复杂度为 $O(N)$ ，完全满足题目要求。