回收站选址

题目描述

给定平面上N个垃圾投放点位置，回收站可以建在某个垃圾点$(x,y)$的上下左右四个相邻位置。如果一个选址位置的四方向都有垃圾点，且四个对角方向各有至少一个垃圾点，则该选址为有效。

统计所有有效选址的数量。

算法思路

枚举所有可能的回收站选址：

1. 先将所有垃圾点存入哈希集合（便于O(1)查找）
2. 遍历所有垃圾点作为参考位置
3. 对每个垃圾点的四个方向邻居位置作为候选选址
4. 检查每个候选选址是否满足条件：
   • 四正方向都有垃圾点
   • 四对角方向至少有一个垃圾点
5. 计数满足条件的选址数

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int,int>> pts(n);
    unordered_set<long long> S;
    for(int i = 0; i < n; i++){
        cin >> pts[i].first >> pts[i].second;
        long long key = ((long long)pts[i].first << 32) + pts[i].second;
        S.insert(key);
    }
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int cx[4] = {1, 1, -1, -1};
    int cy[4] = {1, -1, 1, -1};
    
    int ans = 0;
    for(int i = 0; i < n; i++){
        int x = pts[i].first, y = pts[i].second;
        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            long long key = ((long long)nx << 32) + ny;
            
            // 检查四正方向是否有垃圾点
            bool fourDir = true;
            for(int d = 0; d < 4; d++){
                int tx = nx + dx[d];
                int ty = ny + dy[d];
                long long tkey = ((long long)tx << 32) + ty;
                if(S.find(tkey) == S.end()){
                    fourDir = false;
                    break;
                }
            }
            if(!fourDir) continue;
            
            // 检查四对角方向至少有一个
            bool diagonal = false;
            for(int d = 0; d < 4; d++){
                int tx = nx + cx[d];
                int ty = ny + cy[d];
                long long tkey = ((long long)tx << 32) + ty;
                if(S.find(tkey) != S.end()){
                    diagonal = true;
                    break;
                }
            }
            if(diagonal) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

关键点

• 使用哈希集合存储垃圾点坐标，支持O(1)查找
• 枚举每个垃圾点的四方向邻居作为候选选址
• 对角方向只需至少一个满足即可
• 注意坐标范围，使用合适的数据结构

参考

• CCF-CSP认证