P4713 投沙包（入门）

解题思路

选手向一片区域投了 n 个矩形沙包，沙包落地后是平行于坐标轴的。只要沙包盖住了目标点就算投中（目标点在边上或四个顶点上也算）。题目要求统计一共有多少个沙包投中了目标点；如果一个都没投中，就输出 -1。

这道题和"铺地毯"很相似，但有一个重要区别：输入给的是沙包左上角的坐标 (x1,y1)，以及长 l、宽 w。沙包是平行于坐标轴的矩形，所以它覆盖的范围是：

• x 方向从 x1 到 x1+l；
• y 方向从 y1-w 到 y1（因为左上角的 y 坐标最大，矩形向下延伸 w 个单位）。

于是判断目标点 (x,y) 是否在某个沙包内，只需要同时满足：

• x1 ≤ x ≤ x1+l
• y1-w ≤ y ≤ y1

和铺地毯一样，边界和顶点都算被覆盖，所以用 ≤ 而不是 <。

另一个要注意的地方是输入顺序：所有沙包的信息先给出，目标点 (x,y) 在最后一行才给。所以我们要先把 n 个沙包分别存进数组，等读入目标点之后，再逐个沙包去判断。每判断成功一个，计数器就加一。

最后看计数结果：如果计数值为 0，说明一个沙包都没投中，输出 -1；否则输出计数值。

验证一下样例：三个沙包中，前两个都盖住了点 (2,2)，第三个沙包的 x 范围是 4 到 7，不包含 2，所以答案就是 2。

参考代码

// 投沙包：统计有多少个矩形沙包覆盖目标点
#include <iostream>
using namespace std;
int xa[100005], ya[100005], la[100005], wa[100005];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> xa[i] >> ya[i] >> la[i] >> wa[i];
    int x, y;
    cin >> x >> y;
    int cnt = 0;
    // 沙包左上角(x1,y1)，长l宽w：x范围[x1,x1+l]，y范围[y1-w,y1]
    for (int i = 0; i < n; i++) {
        int x1 = xa[i], y1 = ya[i], l = la[i], w = wa[i];
        if (x >= x1 && x <= x1 + l && y >= y1 - w && y <= y1) cnt++;
    }
    if (cnt == 0) cout << -1 << endl;
    else cout << cnt << endl;
    return 0;
}

复杂度分析

程序先读入 n 个沙包存进数组，需要 O(n) 时间；再对每个沙包做一次常数时间的判断，也是 O(n)。所以总时间复杂度是 O(n)，对于 n 很大的数据也能轻松通过。

空间方面，用四个长度 100005 的数组分别存沙包的左上角 x、y 和长、宽，空间复杂度 O(n)，足够大不会越界。