扫雷

小明最近迷上了一款名为《扫雷》的游戏。

其中有一个关卡的任务如下：

在一个二维平面上放置着 n个炸雷，第 i个炸雷 (xi,yi,ri)表示在坐标 (xi,yi)处存在一个炸雷，它的爆炸范围是以半径为 ri的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。

玩家可以发射 m个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j个排雷火箭 (xj,yj,rj)表示这个排雷火箭将会在 (xj,yj)处爆炸，它的爆炸范围是以半径为 rj的一个圆，在其爆炸范围内的炸雷会被引爆。

同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。

现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。

一个点处可以存在多个炸雷和排雷火箭。

当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式
输入的第一行包含两个整数 n、m。

接下来的 n行，每行三个整数 xi,yi,ri，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 xj,yj,rj，表示一个排雷火箭的信息。

输出格式
输出一个整数表示答案。

数据范围
对于 40%的评测用例：0≤x,y≤109,0≤n,m≤103,1≤r≤10，
对于 100%的评测用例：0≤x,y≤109,0≤n,m≤5×104,1≤r≤10。

输入样例：
2 1
2 2 4
4 4 2
0 0 5

输出样例：
2

样例解释
示例图如下，排雷火箭 1覆盖了炸雷 1，所以炸雷 1被排除；炸雷 1又覆盖了炸雷 2，所以炸雷 2也被排除。

手写哈希+bfs

一些哈希表的知识点：
手写哈希比直接用map和unordered_map速度快很多，这一题数据很大，所以必须手写哈希。

得到哈希值为return (ll)x * X + y;的解释：
本题m和n范围都是到1e9，故用1e9+1进制的数来表示，如二进制只可能出现0和1，(xy)看成一个1e9+1进制的数，则这个数为 x*（1e9+1）+ y，假设这个值是h，令t = 1e9+1，那么x = h / t，y = h % t，每一对x，y一定是唯一确定的。

得到哈希数组的下标int key = (hs % M + M) % M;的解释：
hs%m保证了这个数为0到m-1,再加m则这个数为m到2*m-1,再对m取余则这个数为1到m-1

本题思路：用bfs，但是如果遍历每个导弹反而更多，再看到题目半径r最大为10，故遍历范围内的每个点判断更快。

#include 
#include 
#include 
using namespace std;const int N = 5e4 + 10, M = 1e6 + 7, X = 1e9 + 1;
int n, m;
struct node {int x, y, r;
}b[N];
typedef long long ll;
ll h[M]; // 哈希数组
bool st[N]; // 判断是否访问过
int id[M], res; // id数组为哈希数组中key对应的地雷下标ll get_hs(int x, int y) { // 得到每个坐标的哈希值return (ll)x * X + y;
}int find(int x, int y) { // 找到该坐标被哈希数组存储的下标keyll hs = get_hs(x, y);int key = (hs % M + M) % M; // 映射到哈希数组内部// 如果该位置已经被占用并且不等于我们要求的哈希值，要在之后找到相应位置while(h[key] != -1 && h[key] != hs) { key++;if(key == M) key = 0; // 哈希表走到末尾，又从0开始}return key;
}// 判断x1，y1为圆心，半径为r的圆是否包含x，y
bool check(int x1, int y1, int r, int x, int y) { int d = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);return d <= r * r;
}void bfs(int pos) {queue q;q.push(pos);st[pos] = 1;while(q.size()) {int t = q.front();q.pop();int x = b[t].x, y = b[t].y, r = b[t].r;for(int xx = x - r; xx <= x + r; xx++) { // 从(x-r, y-r)枚举到(x+r, y+r)for(int yy = y - r; yy <= y + r; yy++) {int key = find(xx, yy); // 找到该坐标点对应的哈希下标// 该点是不是地雷，有没有被访问过，能不能炸到 if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) { int pos = id[key]; // 获得对应地雷编号st[pos] = 1;q.push(pos);}}}}
}int main() {cin >> n >> m;memset(h, -1, sizeof(h));int x, y, r;for(int i = 1; i <= n; i++) { // 读入地雷，存入哈希表cin >> x >> y >> r;b[i] = {x, y, r};int key = find(x, y);// 找到该坐标点对应的哈希下标if(h[key] == -1) h[key] = get_hs(x, y); // 如果哈希对应位置为空，则插入// id数组没有被标记或者找到了同一个坐标点更大半径的地雷if(!id[key] || b[id[key]].r < r) { id[key] = i;}}for(int i = 1; i <= m; i++) { // 枚举导弹cin >> x >> y >> r;for(int xx = x - r; xx <= x + r; xx++) {for(int yy = y - r; yy <= y + r; yy++) {int key = find(xx, yy);// 如果该点有地雷，没有被访问过，能被炸到if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) bfs(id[key]);}}}// 遍历每个地雷，看是否被标记for(int i = 1; i <= n; i++) {int key = find(b[i].x, b[i].y); // 获得坐标点对应哈希下标int pos = id[key]; // 哈希下标对应的地雷编号if(pos && st[pos]) res++; // 如果有地雷并且被访问过}cout << res;return 0;
}