题目描述
小明最近迷上了一款名为《扫雷》的游戏。
其中有一个关卡的任务如下：
在一个二维平面上放置着?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≤10^9,0≤n,m≤10^3,1≤r≤10，
对于?100%?的评测用例：0≤x,y≤10^9,0≤n,m≤5×10^4,1≤r≤10。
输入样例：
2 1
2 2 4
4 4 2
0 0 5
输出样例：
2
样例解释
示例图如下，排雷火箭?1?覆盖了炸雷?1，所以炸雷?1?被排除；炸雷?1?又覆盖了炸雷?2，所以炸雷?2?也被排除。
题意：?有n颗地雷以及m个排雷火箭，分别给出这n+m个点的坐标以及其爆炸半径，处于爆炸半径内的地雷都会被引爆，这个反应可以连锁传递下去，开始时依次引爆所有排雷火箭，问最终能引爆多少颗地雷。
分析：?这道题目有个很关键的信息，所有点爆炸半径都不超过10，而且每个点坐标都是整数，那么对于一个点其半径内的点完全可以枚举出来，这样最多也才枚举不到400个点而已。于是可以以点坐标为索引，存储该点的最大半径以及该点雷数，一开始我用的是map，但是一直T，后来听y总说这题必须手写hash，于是换上手写hash，将点的坐标映射到一个小于1e6的整数上，然后存储点信息的数组都可以以该整数为索引了。手写hash的过程就和数据结构书上写的一样，首先先将点坐标看作一个1e9+1进制的数字，然后将该数字映射到哈希数组上，哈希函数构造方法为除留余数法，冲突处理方法为线性探测再散列。
得到某点的最大半径以及雷数就可以bfs或dfs了，后面的步骤就比较常规了，这道题目主要是手写hash比较难想，根本想不到会卡常数。
具体代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define int long long
#define pii pair<int, int>
using namespace std;
const int mod = 1000003;//哈希表表长
int n, m;
int x[100005], y[100005], r[100005];
int h[1000005];
bool vis[1000005];
pii mp[1000005];//记录该点处最大半径及雷数
int get_key(int xx, int yy){//转化为一个1e9+1进制的数
return xx*1000000001+yy;
}
int find(int xx, int yy){//将一个二维坐标映射到小于mod的数字
int key = get_key(xx, yy);
int temp = key;
temp = (temp%mod+mod)%mod;
while(!(h[temp] == -1 || h[temp] == key))
temp = (temp+1)%mod;
return temp;
}
signed main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++){
scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);
h[find(x[i], y[i])] = get_key(x[i], y[i]);
int id = find(x[i], y[i]);
mp[id].second++;
mp[id].first = max(mp[id].first, r[i]);
}
for(int i = n+1; i <= n+m; i++){
scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);
h[find(x[i], y[i])] = get_key(x[i], y[i]);
int id = find(x[i], y[i]);
mp[id].first = max(mp[id].first, r[i]);
}
queue<pii> q;
for(int i = n+1; i <= n+m; i++){
int id = find(x[i], y[i]);
if(!vis[id]){
vis[id] = true;
q.push(make_pair(x[i], y[i]));
}
}
int res = 0;
while(q.size()){
pii now = q.front();
q.pop();
int nowx = now.first, nowy = now.second;
int id = find(nowx, nowy);
int rmax = mp[id].first, num = mp[id].second;
res += num;
for(int xx = nowx-rmax; xx <= nowx+rmax; xx++)
for(int yy = nowy-rmax; yy <= nowy+rmax; yy++)
if(rmax*rmax >= (xx-nowx)*(xx-nowx)+(yy-nowy)*(yy-nowy)){
int id = find(xx, yy);
if(!vis[id] && mp[id].second){//如果该处有雷且未被访问过
vis[id] = true;
q.push(make_pair(xx, yy));
}
}
}
cout << res;
return 0;
}
