回收站选址这道题，在 CCF 算法能力认证的历年真题里属于“一看就会、一写就错”的经典类型。我见过不少朋友模拟的时候信心满满，提交完一看 50 分、70 分，回来查代码才发现：不是把上下左右和对角判定混在一起，就是试图用二维数组存整个坐标平面，直接把内存开炸了。这道题用 C 语言或者 C++ 拿 100 分，难点从来不在算法深度，而在于三件事：读题要读透，坐标查询要做对，两层判断逻辑要分清楚。
这篇文章我会把 C 和 C++ 两版 100 分代码都贴出来，逐段讲清楚为什么这样写，再把提交前容易翻车的几个细节单独拎出来说。无论是正在准备认证考试、还是拿真题练手的朋友，照着这份思路走，回收站选址应该不会再丢分。
1. 回收站选址的题面，读三遍都不算多
1.1 四个判定条件到底在说什么
先把题目的设定复述一遍。平面上有 n 个垃圾点，每个点用整数坐标 (x, y) 唯一标识。我们要从这些垃圾点里挑出一些位置当作回收站选址。
判断标准分两层。第一层：某个垃圾点的正上、正下、正左、正右四个相邻坐标上也必须存在垃圾点，这个点才有资格当候选点，四个条件缺一不可。第二层：候选点评分看的是斜对角线上的四个位置——左上、右上、左下、右下——有几个位置存在垃圾点，存在一个得一分，满分 4 分。
这里有个容易理解偏的地方：候选点必须本身就是一个垃圾点，而不是随便一块空地。题目问的是在垃圾点中选址，所以枚举候选点时只需要遍历输入进来的 n 个点，完全不需要去扫描整个二维平面。这是整道题能保持 O(n²) 复杂度的前提。
用个不恰当的类比：选位置就像看一个小区房，先得保证东西南北四户都有人住，才有资格参与评选；然后看斜对角的四户有几户亮着灯，亮一盏算一分。上下左右是及格线，对角才是加分项。
1.2 样例手工推演
题目给的样例是 7 个点：
7 1 2 2 1 0 0 1 1 1 0 2 0 0 1输出是：
0 0 1 0 0手工验证一遍。逐点检查后会发现，只有 (1, 1) 这个点的上下左右都满足：
- 上方 (1, 2) 存在；
- 下方 (1, 0) 存在；
- 左方 (0, 1) 存在；
- 右方 (2, 1) 存在。
所以 (1, 1) 是候选点。它的四个对角分别是 (0, 0)、(2, 0)、(0, 2)、(2, 2)，其中前两个存在，后两个不存在，得分是 2。因此得 2 分的候选点数量为 1，输出第三行是 1。
其它点为什么不满足？例如 (0, 0) 的左方 (-1, 0) 不存在；(0, 1) 的左方 (-1, 1) 不存在；(2, 0) 的上方 (2, 1) 存在、下方 (2, -1) 不存在。这些点在第一层就被淘汰了。所以答案是 0 0 1 0 0。
1.3 数据范围决定你能用哪些招
真题的数据范围一般写得很明白，n 不超过 1000，坐标绝对值不超过 10⁹。这两个数字直接决定了策略：
- 坐标绝对值能到 10⁹，意味着绝对不能用二维数组去标记坐标。哪怕坐标全是非负，也需要大约 10¹⁸ 个格子，内存直接爆掉。
- n 只有 1000，意味着 O(n²) 的暴力在时间和空间上都绰绰有余。
- 坐标可能为负，但不要紧，当作带符号整数处理即可。
所以这道题真正要解决的核心问题只有一个：快速判断“某个坐标是否存在于这 n 个点中”。后面 90% 的代码都围绕这个查询展开。
2. “坐标存在吗”：比算法更重要的数据组织
2.1 二维数组为什么是死路
有些同学一看“平面上的点”就想到二维数组bool vis[x][y]，这是这题最大的陷阱。假设坐标范围是 0 到 10⁹，那么二维数组要开 10⁹ 乘 10⁹ 个布尔值，这在任何一台测评机上都是不可能的。要是坐标还有负数，还需要给坐标加偏移，数组规模只会更大。
正确的思路是把 n 个点当成一个稀疏集合：我们只关心输入中出现的坐标，其它坐标一律视为不存在。这样存储量从天文数字降到了 1000 个点，后续所有判断都在这 1000 个点上做。
2.2 C++ 解法：把坐标当成容器的 key
C++ 里最直观的做法是用 map 或 set，把坐标对 (x, y) 作为 key。pair 自带字典序比较，所以直接写map<pair<ll, ll>, bool>就能用。插入和查询都很自然：
mp[{x, y}] = true; if (mp.count({x, y})) { ... }也可以用 set 代替 map，因为这里只需要判断存在性，不需要额外存 value。两种写法复杂度一样，log n 级别，n=1000 时毫无压力。
2.3 C 语言没有 map：暴力线性查找为什么也够
C 语言标准库里没有现成的关联容器，很多 C 选手在考场上就开始慌了。其实完全不用慌，n=1000 这个规模下，线性查找完全撑得住。
思路是写一个 has 函数，给定 (x, y)，遍历一遍数组，看有没有坐标相等：
int has(ll x, ll y) { for (int i = 0; i < n; i++) { if (p[i].x == x && p[i].y == y) return 1; } return 0; }每个候选点最多查 8 个邻居，每个邻居的查询最多扫 1000 个点，总比较次数在 8×10⁶ 这个量级。C 语言下跑起来大概是几毫秒到几十毫秒，离时间限制远得很。
2.4 想更专业一点：排序加二分查找
如果觉得线性查找太“暴力”，想体现功底，可以先按 x 排序，x 相同按 y 排序，然后用二分查找判断坐标是否存在。查询复杂度从 O(n) 降到 O(log n)，整个程序复杂度 O(n log n)。
int cmp(const void *a, const void *b) { Point *pa = (Point *)a, *pb = (Point *)b; if (pa->x != pb->x) return (pa->x > pb->x) ? 1 : -1; if (pa->y != pb->y) return (pa->y > pb->y) ? 1 : -1; return 0; } int has(ll x, ll y) { int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (p[mid].x == x && p[mid].y == y) return 1; if (p[mid].x < x || (p[mid].x == x && p[mid].y < y)) l = mid + 1; else r = mid - 1; } return 0; }这个版本的优势在 n 变大时立刻显现。比如 n 到 10⁵，线性查找就会明显变慢，而二分查找依然瞬间出结果。放到这题里属于“杀鸡用牛刀”，但作为 C 选手，这个技能值得顺手掌握。
三种方案对比如下：
| 方案 | 单次查询复杂度 | 总复杂度 | 适用语言 |
|---|---|---|---|
| map / set | O(log n) | O(n log n) | C++ |
| 线性查找 | O(n) | O(n²) | C / C++ |
| 排序 + 二分 | O(log n) | O(n log n) | C / C++ |
3. C++ 100 分代码逐段拆解
3.1 方向偏移表：把八个邻居写清楚
写代码前，我习惯先在草稿纸上列一个方向偏移表：
| 方向 | dx | dy |
|---|---|---|
| 上 | 0 | 1 |
| 下 | 0 | -1 |
| 左 | -1 | 0 |
| 右 | 1 | 0 |
| 左上 | -1 | 1 |
| 右上 | 1 | 1 |
| 左下 | -1 | -1 |
| 右下 | 1 | -1 |
用这个表对照着写 if 判断，基本不会出现把x+1写成y+1这种手滑错误。在考场上，先把这个表画出来再写代码，看似多花了一分钟，实际上能省下后面调试的大量时间。
3.2 完整 C++ 代码
#include <iostream> #include <map> using namespace std; typedef long long ll; struct Node { ll x, y; } a[1005]; map<pair<ll, ll>, bool> mp; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; mp[{a[i].x, a[i].y}] = true; } int ans[5] = {0, 0, 0, 0, 0}; for (int i = 0; i < n; i++) { ll x = a[i].x, y = a[i].y; // 第一层：上下左右必须全是垃圾点 if (!mp.count({x, y + 1})) continue; if (!mp.count({x, y - 1})) continue; if (!mp.count({x + 1, y})) continue; if (!mp.count({x - 1, y})) continue; // 第二层：统计四个对角方向的垃圾点数 int score = 0; if (mp.count({x + 1, y + 1})) score++; if (mp.count({x + 1, y - 1})) score++; if (mp.count({x - 1, y + 1})) score++; if (mp.count({x - 1, y - 1})) score++; ans[score]++; } for (int i = 0; i < 5; i++) { cout << ans[i] << '\n'; } return 0; }这段代码提交到测评环境，只要编译选项支持 C++11 以上，就是稳定 100 分。核心逻辑 20 行都不到。
3.3 几个容易忽略的细节
使用mp.count({x, y})而不是mp[{x, y}]做判断，是个好习惯。count 只查询不插入，而 [] 在没有 key 时会默认插入一个 false，虽然结果通常不受影响，但会悄悄改变 map 的大小，严谨性上差一点。
另外typedef long long ll是个人习惯。坐标绝对值虽然题目说是 10⁹，int 也能存下，但后面做偏移、比较大小的时候，用 long long 更踏实，也能避免某些平台上 int 边界运算带来的隐患。
4. C 语言版本：没有容器照样 100 分
4.1 完整可提交的 C 代码
#include <stdio.h> typedef long long ll; typedef struct { ll x, y; } Point; Point p[1005]; int n; int has(ll x, ll y) { for (int i = 0; i < n; i++) { if (p[i].x == x && p[i].y == y) return 1; } return 0; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld %lld", &p[i].x, &p[i].y); } int ans[5] = {0, 0, 0, 0, 0}; for (int i = 0; i < n; i++) { ll x = p[i].x, y = p[i].y; if (!has(x, y + 1)) continue; if (!has(x, y - 1)) continue; if (!has(x + 1, y)) continue; if (!has(x - 1, y)) continue; int score = 0; if (has(x + 1, y + 1)) score++; if (has(x + 1, y - 1)) score++; if (has(x - 1, y + 1)) score++; if (has(x - 1, y - 1)) score++; ans[score]++; } for (int i = 0; i < 5; i++) { printf("%d\n", ans[i]); } return 0; }整体逻辑和 C++ 版一一对应，只是把 map 的查询换成了自定义的 has 函数。
4.2 线性查找的时间账：为什么不会超时
前面简单提过复杂度，这里把账算清楚。n 最大 1000，对每个点最多执行 8 次 has 查询，每次 has 最坏遍历 1000 个点，每次比较是两次相等判断。总比较次数约为 1000 × 8 × 1000 = 8 × 10⁶。
这个数量级在 C 语言下完全不是问题。哪怕测评机主频低一些，也就几十毫秒级别。真正需要担心的反而是输入输出格式这种细节，而不是性能。
4.3 顺手改进：qsort 加二分
如果想让 C 版本在数据变大时也有余量，可以在 has 函数里换成二分。主函数不用大改，只需要在读入全部点后先调用一次qsort(p, n, sizeof(Point), cmp)，然后把 has 替换成二分版本。
int cmp(const void *a, const void *b) { Point *pa = (Point *)a; Point *pb = (Point *)b; if (pa->x != pb->x) return (pa->x > pb->x) ? 1 : -1; if (pa->y != pb->y) return (pa->y > pb->y) ? 1 : -1; return 0; } int has(ll x, ll y) { int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (p[mid].x == x && p[mid].y == y) return 1; if (p[mid].x < x || (p[mid].x == x && p[mid].y < y)) l = mid + 1; else r = mid - 1; } return 0; }主循环里判断候选点和统计得分的代码一行都不用动。这个“把查询函数单独封装，主逻辑只调接口”的思路，在任何题目里都值得坚持。
5. 提交前最容易翻车的几个细节
5.1 把上下左右和对角两层逻辑混在一起
最常见的不是写错语法，是逻辑层次错乱。有些同学会这样做：统计八个方向中有垃圾点的数量，然后不再区分上下左右和对角。这样会把“斜对角有点”误当成“上下左右齐全”的加分项，算出一堆根本不存在的候选点。
正确做法就是代码里展示的两层结构：先连续判断四个正方向，任何一个不满足就 continue 到下一个点；只有四方向全满足，才进入对角评分。顺序不能反过来，也不能混在一起。
5.2 负坐标、int 溢出与 scanf 格式
坐标可以是负的，这个题不设限。负坐标本身不可怕，只要所有运算都基于相对位置偏移，比较的时候注意符号即可。唯一要注意的是数据类型的范围：用 long long 存储，避免在边界运算时出现意外。
C 语言里读取 long long 用%lld，输出同理。有些老旧的 Windows 环境可能对%lld支持不佳，但标准 C99 以后都没有问题。如果测评环境是 Linux，直接放心用。
5.3 输出顺序和数组下标
ans[0] 装的是得分 0 的候选点数量，ans[4] 装的是得分 4 的数量，输出必须严格按 0、1、2、3、4 的顺序。容易摔的地方是“只输出有数量的分数”，比如只输出 1 或者省略前导 0，直接丢分。五个整数都要输出，即使是 0 也要输出。
5.4 重复点与边界点
题目一般会保证垃圾点互不相同，所以不用额外处理判重。如果自己造测试数据时出现重复点，map 方案天然去重，线性查找方案也不会崩，只是统计逻辑可能需要额外考虑，比赛题一般不会在这里挖坑。
边界点指的是 x 或 y 极端的点，比如某个点右边已经没有输入点了。这种情况不需要特判，因为上下左右不满足时自然 continue，不会进入计分阶段。
6. 做完这道题，你还能带走点什么
6.1 这题真正想考的能力
回收站选址没有复杂的图论，没有动态规划，甚至连排序都不强制要求。它考的是注意力分配：能不能把题意中的两层判断理清楚，能不能根据数据范围选择合理的坐标存储方案。
“先看数据范围，再定算法”这句话，几乎每本算法书都会说，但真正能落实在代码里的不多。这题就是一个极好的训练样本，建议做完全程复盘时，把重点放在“我为什么选择这种存储方案”这个问题上，而不是简单核对答案。
6.2 可以顺着练习的变式题
做完原题，可以想想这几个变式：
- 如果 n 变成 10⁶，线性查找和 map 都会吃力，需要换 unordered_map 或手写哈希，排序二分也还能用。
- 如果邻域定义变成八方向中任意连续三个方向，判定逻辑要怎么改。
- 如果坐标变成浮点数，哈希方案基本作废，但排序加二分依然稳定。
- 如果要求输出候选点的具体坐标而不是计数，ans 数组改成存点的数组即可。
这些都是回收站选址的合理延伸，把任何一个想明白，都比盲目再刷十道简单题有用。
6.3 个人实测心得和考场建议
我第一次完整跑这道题，用的就是 map 版本，一次通过。后来为了给只会 C 的朋友讲题，重写了一个线性查找版，代码反而更短，也更容易向别人解释。
考场上如果时间紧张，建议优先写线性查找版本的 C 语言代码，逻辑最直白，不容易出现容器相关的编译问题。最后分享一个小技巧：动笔写循环之前，先在草稿纸上画一个坐标轴，把八个邻居的偏移量标出来，然后对着这张表写 if。这样就能把最常见的“方向搞反”和“坐标写串”两个问题，从源头上掐掉。
