题目分析

题意简述

在Kamran前往El Dorado的奇妙旅程中，国王赐予他皇家花园中指定面积的矩形区域。花园中树木分布无规律，Kamran要在满足园丁要求（子花园边界与主花园边界平行、顶点坐标为整数、面积大于零）的前提下，根据给定的树木位置和允许的最大面积，找到一个矩形子花园，使得其中包含的树木数量最多（边界上的树木也算在内）。

输入

• 第一行包含整数 $T$，表示测试用例数量。
• 每个测试用例中：
  • 第一行有两个整数 $F$（树木数量，$0 \leq F \leq 1000$）和 $A$（允许的最大面积） 。
  • 接下来 $F$ 行，每行两个整数 $x$ 和 $y$（$1 \leq x,y \leq 1000$ ），表示一棵树的位置，且所有树位置唯一。

输出

对于每个测试用例，输出一个整数，即Kamran能获得的最大树木数量。

解题思路

枚举矩形范围

通过四层循环枚举所有可能的矩形。其中两层循环枚举矩形在 $x$ 轴方向上的边界（由两棵树的 $x$ 坐标确定），另外两层循环枚举矩形在 $y$ 轴方向上的边界（由两棵树的 $y$ 坐标确定）。这样可以遍历到所有可能包含树木的矩形区域。

计算矩形相关属性

1. 对于每一个枚举出来的矩形，通过 $area$ 函数计算其面积。$area$ 函数根据矩形对角顶点坐标（$x_1$, $y_1$ 和 $x_2$, $y_2$ ），利用公式 $(x_2 - x_1 + 1) * (y_2 - y_1 + 1)$ 计算面积。
2. 使用 $countTrees$ 函数统计该矩形内包含的树木数量。$countTrees$ 函数遍历所有树木，判断每棵树的坐标是否在矩形范围内（$x$ 坐标满足 $x \geq x_1$ 且 $x \leq x_2$，$y$ 坐标满足 $y \geq y_1$ 且 $y \leq y_2$ ），如果在范围内则计数加一。

筛选符合条件的矩形

判断计算出的矩形面积是否满足不超过允许的最大面积 $A$ 且大于零的条件。若满足条件，则更新当前找到的包含树木最多的数量 $maxTrees$ 。

代码实现

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

using namespace std;

// 计算矩形面积
int area(int x1, int y1, int x2, int y2) {
    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

// 检查矩形内包含的树木数量
int countTrees(const vector<pair<int, int> >& trees, int x1, int y1, int x2, int y2) {
    int count = 0;
    // 使用传统for循环替代范围for循环
    for (size_t i = 0; i < trees.size(); ++i) { 
        const pair<int, int>& tree = trees[i];
        int x = tree.first;
        int y = tree.second;
        if (x >= x1 && x <= x2 && y >= y1 && y <= y2) {
            count++;
        }
    }
    return count;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int F, A;
        cin >> F >> A;

        vector<pair<int, int> > trees;
        for (int i = 0; i < F; ++i) {
            int x, y;
            cin >> x >> y;
            trees.push_back(make_pair(x, y));
        }

        int maxTrees = 0;
        // 枚举所有可能的矩形
        for (int i = 0; i < F; ++i) {
            for (int j = i; j < F; ++j) {
                for (int k = 0; k < F; ++k) {
                    for (int l = k; l < F; ++l) {
                        int x1 = min(trees[i].first, trees[j].first);
                        int x2 = max(trees[i].first, trees[j].first);
                        int y1 = min(trees[k].second, trees[l].second);
                        int y2 = max(trees[k].second, trees[l].second);
                        int rectArea = area(x1, y1, x2, y2);
                        if (rectArea <= A && rectArea > 0) {
                            int numTrees = countTrees(trees, x1, y1, x2, y2);
                            maxTrees = max(maxTrees, numTrees);
                        }
                    }
                }
            }
        }

        cout << maxTrees << endl;
    }

    return 0;
}

代码说明

1. 输入处理：
   • 首先读取测试用例数量 $T$ ，然后进入循环处理每个测试用例。
   • 在每个测试用例中，读取树木数量 $F$ 和允许的最大面积 $A$ ，接着依次读取每棵树的坐标 $(x, y)$ ，并存储到 $trees$ 向量中。
2. 枚举矩形并计算：
   • 通过四层嵌套循环枚举所有可能的矩形。确定矩形在 $x$ 轴和 $y$ 轴方向上的边界点坐标 $x_1$、$x_2$、$y_1$、$y_2$ 。
   • 计算矩形面积 $rectArea$ ，判断其是否满足面积条件（不超过 $A$ 且大于 $0$ ）。若满足条件，计算该矩形内树木数量 $numTrees$ ，并更新最大树木数量 $maxTrees$ 。
3. 输出结果：
   • 每个测试用例处理完毕后，输出当前测试用例中能获得的最大树木数量 $maxTrees$ 。