题意分析

题目要求统计所有被其他矩形完全覆盖的矩形的数量。

• 输入：多组测试数据，每组给出若干矩形（数量 ≤ 5000），每个矩形由其最小和最大的 x、y 坐标表示。
• 输出：对于每组数据，输出被完全覆盖的矩形的数量。
• 覆盖条件：矩形 A 被矩形 B 覆盖，当且仅当：
  • A 的 x 范围完全包含在 B 的 x 范围内（即 B.xmin ≤ A.xmin 且 A.xmax ≤ B.xmax）。
  • A 的 y 范围完全包含在 B 的 y 范围内（即 B.ymin ≤ A.ymin 且 A.ymax ≤ B.ymax）。
  • 注意：题目未明确说明是否允许矩形重合（即 A 和 B 完全相同），但样例 2 显示完全相同的矩形也算覆盖。

解题思路

1. 暴力枚举法（适用于数据规模较小的情况，如 n ≤ 5000）：

   • 对于每个矩形 A，检查是否存在另一个矩形 B（B ≠ A），使得 A 被 B 完全覆盖。
   • 时间复杂度：O(n²)，对于 n = 5000，最坏情况下需要约 25,000,000 次比较，在大多数编程竞赛中是可接受的。

2. 优化方法（如果数据规模更大，如 n ≥ 10⁵）：

   • 可以按矩形面积排序，从小到大检查是否被更大的矩形覆盖。
   • 使用空间索引结构（如 R树、KD树）加速查询，但本题不需要。

C++ 实现

以下是该问题的 C++ 解法，采用暴力枚举法，适用于数据规模 n ≤ 5000。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Rectangle {
    int xmin, xmax, ymin, ymax;
};

bool isCovered(const Rectangle& a, const Rectangle& b) {
    return (b.xmin <= a.xmin) && (b.xmax >= a.xmax) &&
           (b.ymin <= a.ymin) && (b.ymax >= a.ymax);
}

int countCoveredRectangles(const vector<Rectangle>& rects) {
    int count = 0;
    for (size_t i = 0; i < rects.size(); ++i) {
        for (size_t j = 0; j < rects.size(); ++j) {
            if (i != j && isCovered(rects[i], rects[j])) {
                ++count;
                break;
            }
        }
    }
    return count;
}

int main() {
    int n;
    while (cin >> n) {
        vector<Rectangle> rects(n);
        for (int i = 0; i < n; ++i) {
            cin >> rects[i].xmin >> rects[i].xmax 
                >> rects[i].ymin >> rects[i].ymax;
        }
        cout << countCoveredRectangles(rects) << endl;
    }
    return 0;
}