题目分析

题意简述

本题存在多组测试用例，每组测试用例包含点的数量 $n$ 和一个半径 $r$，以及 $n$ 个点的坐标 $(x, y)$。需要找出在一个边长为 $r$ 的正方形区域内能够包含的最多点数，最终输出这个最大点数。

输入

• 第一行输入测试用例的组数 $t$。
• 对于每组测试用例，第一行输入点的数量 $n$ 和半径 $r$。
• 接下来的 $n$ 行，每行输入一个点的 $x$ 坐标和 $y$ 坐标。

输出

对于每组测试用例，输出一个整数，表示在边长为 $r$ 的正方形区域内能够包含的最多点数。

解题思路

点的排序与分组

1. 结构体定义：定义结构体 pt 来存储点的坐标 $(x, y)$。
2. 点的排序：读入所有点的坐标后，按照 $x$ 坐标从小到大排序，如果 $x$ 坐标相同，则按照 $y$ 坐标从小到大排序。
3. 按 $x$ 坐标分组：遍历排序后的点，将 $x$ 坐标相同的点归为一组，记录每组的 $x$ 坐标（ptHeng 数组）和该组内点的 $y$ 坐标（ptList 数组）以及该组的点数（ptNum 数组）。

枚举起始列并收集点

对于每一列，将其作为起始列，收集所有 $x$ 坐标在 $[x_{start}, x_{start} + r]$ 范围内的点的 $y$ 坐标到 collect 数组中。

滑动窗口计算最大点数

1. 排序：对收集到的 $y$ 坐标数组 collect 进行排序。
2. 滑动窗口：使用双端队列 fangye 来维护一个滑动窗口，窗口的长度不能超过 $r$。遍历排序后的 collect 数组，将元素加入队列，同时检查队列头部元素与当前元素的差值是否超过 $r$，如果超过则移除队列头部元素。在这个过程中，记录窗口内元素的最大数量 mxGs。

更新最大点数

比较所有起始列对应的最大点数 mxGs，更新全局最大点数 ans。

代码实现

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  // 替换nullptr为0

    int t;
    cin >> t;
    while (t--) {
        int n, r;
        cin >> n >> r;
        vector<pair<int, int> > trees(n);  // 注意空格在> >
        vector<int> x_coords, y_coords;
        
        for (int i = 0; i < n; ++i) {
            cin >> trees[i].first >> trees[i].second;
            x_coords.push_back(trees[i].first);
            y_coords.push_back(trees[i].second);
        }
        
        // 离散化处理
        sort(x_coords.begin(), x_coords.end());
        sort(y_coords.begin(), y_coords.end());
        x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
        y_coords.erase(unique(y_coords.begin(), y_coords.end()), y_coords.end());
        
        int x_size = x_coords.size();
        int y_size = y_coords.size();
        
        // 创建离散化后的网格
        vector<vector<int> > grid(x_size + 1, vector<int>(y_size + 1, 0));  // 注意空格在> >
        
        // 替换auto和范围for循环
        for (vector<pair<int, int> >::const_iterator it = trees.begin(); it != trees.end(); ++it) {
            int x = lower_bound(x_coords.begin(), x_coords.end(), it->first) - x_coords.begin() + 1;
            int y = lower_bound(y_coords.begin(), y_coords.end(), it->second) - y_coords.begin() + 1;
            grid[x][y]++;
        }
        
        // 构建前缀和数组
        vector<vector<int> > prefix(x_size + 1, vector<int>(y_size + 1, 0));  // 注意空格在> >
        for (int i = 1; i <= x_size; ++i) {
            for (int j = 1; j <= y_size; ++j) {
                prefix[i][j] = grid[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
        
        int max_trees = 0;
        
        // 检查所有可能的正方形
        for (int i = 0; i < x_size; ++i) {
            int x_start = x_coords[i];
            int x_end = x_start + r;
            int x_upper = upper_bound(x_coords.begin(), x_coords.end(), x_end) - x_coords.begin();
            
            for (int j = 0; j < y_size; ++j) {
                int y_start = y_coords[j];
                int y_end = y_start + r;
                int y_upper = upper_bound(y_coords.begin(), y_coords.end(), y_end) - y_coords.begin();
                
                int count = prefix[x_upper][y_upper] - prefix[i][y_upper] - prefix[x_upper][j] + prefix[i][j];
                if (count > max_trees) {
                    max_trees = count;
                }
            }
        }
        
        cout << max_trees << '\n';
    }
    
    return 0;
}

代码说明

1. 结构体和数组定义：

   • pt 结构体用于存储点的坐标。
   • points 数组存储所有点的坐标。
   • ptNum 数组记录每组 $x$ 坐标相同的点的数量。
   • ptHeng 数组记录每组点的 $x$ 坐标。
   • ptList 数组记录每组点的 $y$ 坐标。

2. 排序函数 compare：用于对 points 数组进行排序，先按 $x$ 坐标排序，再按 $y$ 坐标排序。

3. 主函数 main：

   • 读取测试用例的组数 $t$。
   • 对于每组测试用例，读取点的数量 $n$ 和半径 $r$，以及每个点的坐标。
   • 对 points 数组进行排序。
   • 按 $x$ 坐标对点数进行分组。
   • 枚举起始列，收集满足条件的点的 $y$ 坐标。
   • 对收集到的 $y$ 坐标进行排序，使用滑动窗口计算最大点数。
   • 更新全局最大点数 ans 并输出。