问题描述
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下, 在一个二维平面上放置着 n 个炸雷, 第 ii 个炸雷 (xi,yi,ri) 表示在坐标 (xi,yi) 处 存在一个炸雷, 它的爆炸范围是以半径为 ri 的一个圆。
为了顺利通过这片土地, 需要玩家进行排雷。玩家可以发射 m 个排雷火 箭, 小明已经规划好了每个排雷火箭的发射方向, 第 j 个排雷火箭 (xj,yj,rj)表 示这个排雷火箭将会在 (xj,yj)处爆炸, 它的爆炸范围是以半径为 rj 的一个圆, 在其爆炸范围内的炸雷会被引爆。同时, 当炸雷被引爆时, 在其爆炸范围内的 炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个 炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n、m
接下来的 n 行, 每行三个整数 xi,yi,ri 表示一个炸雷的信息。
再接下来的 m 行, 每行三个整数 xj,yj,rj 表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
样例输入
2 1
2 2 4
4 4 2
0 0 5
样例输出
2
样例说明
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。
评测用例规模与约定
对于 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.
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
AC代码展示（附带解题思路）
首先此题存在三种方法 思路略有不同 下文将一一详述
注意：三种方法在蓝桥杯官网数据下均能AC 但AcWing平台为hack另外两种做法 单独加了一组数据 所以AcWing平台只有第三种方法能AC
（1）DFS+二分
看到题目 很容易想到直接DFS 枚举每一颗火箭 并且递归模拟每一颗爆炸的地雷
但因为N*M达到1e10 所以直接 每次双层循环 检查每一颗地雷是否爆炸 会超时
而要缩小搜索范围 自然很容易想到二分
于是每次搜索前 先两次二分 找到在横坐标上距离火箭弹中心不超过r的地雷的编号的左右界 直接循环遍历 每次check出是否爆炸即可 若爆炸 则作为一次DFS递归搜索一次
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
const int N=1e5+5; struct s{LL x;LL y;LL r;
};
struct s a[N],b[N];
int n,m;
bool st[N];
LL res;bool cmp(struct s a,struct s b){return a.x<b.x;
}
double check(LL x1,LL x2,LL y1,LL y2){return sqrt( (x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2));
}
void dfs(LL x,LL y,LL rr){LL leftt,rightt;LL l=0,r=n-1;while(l<r){int mid=l+r>>1;if(a[mid].x>=x-rr) r=mid;else l=mid+1;}leftt=l;l=0,r=n-1;while(l<r){int mid=l+r+1>>1;if(a[mid].x<=x+rr) l=mid;else r=mid-1;}rightt=l;for(LL i=leftt;i<=rightt;i++){if(!st[i]&&check(a[i].x,x,a[i].y,y)<=rr){res++;st[i]=true;dfs(a[i].x,a[i].y,a[i].r);}}
}int main(){IOS;cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y>>a[i].r;for(int i=0;i<m;i++) cin>>b[i].x>>b[i].y>>b[i].r;sort(a,a+n,cmp);for(int i=0;i<m;i++) dfs(b[i].x,b[i].y,b[i].r);cout<<res<<endl;return 0;
}（2）哈希表+优化
但其实看代码会有一个疑问 对地雷排序只按照x排序 找左右界时 也是按照[x-r,x+r]内的地雷来找的 但是存不存在一些数据在x上很近 y上却很远 这样的话 二分依旧不能达到很好的效果 代码真的正确吗
正解是 蓝桥杯的数据比较弱 上面的代码就能AC
但正确稳妥的做法应该是哈希 但这里本该因数据量较大 必须手写哈希表 而不能用unordered_map (两者速度相差大约一个数量级 即10倍左右 但经测试发现只要开启O(2)以上的优化或下文代码中的关闭输入输出流即可在unordered_map下顺利AC）
此代码具体思路可移步第三种方法
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
const int N=1e9+1;
int n,m;
unordered_map<LL,int> hash1; //存储key点地雷数量
unordered_map<LL,int> hash2; //存储key点的地雷中 最大半径
unordered_map<LL,bool> st;
LL res;LL Getkey(int x,int y){return (LL)x*1000000001+y;
}
bool check(int x1,int x2,int y1,int y2,int r){int ans=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);return ans<=r*r; //利用r的平方 巧妙化解平方根的精度损失
}void dfs(int x,int y,int r){for(int i=-r;i<=r;i++){for(int j=-r;j<=r;j++){int xx=x+i,yy=y+j;LL key=Getkey(xx,yy);if(!st[key]&&hash1.count(key)&&check(xx,x,yy,y,r)){res+=hash1[key];st[key]=true;dfs(xx,yy,hash2[key]);} }}
}int main(){IOS;cin>>n>>m; int x,y,r;for(int i=0;i<n;i++){cin>>x>>y>>r;LL key=Getkey(x,y);hash1[key]++;hash2[key]=max(hash2[key],r);}for(int i=0;i<m;i++){cin>>x>>y>>r;dfs(x,y,r);}cout<<res<<endl;return 0;
}PS:这里的Base不能在Getkey中直接写成1e9+1 因为1e9+1是个浮点数 在自动隐式转换时 会出现精度错误 可以在定义的时候 int Base 或者写成1000000001也可以（别问我怎么知道！！！！！）
（3）手写哈希
最正确的思路：由于二维不好书写哈希 所以利用n进制累加方法 降维 得到key值 之后手写哈希表hash1 及find函数 之后得到的映射值为int类型 即可适用于 int类型的hash2和hash3的表中
（上文第二种做法 由于未手写find函数 所以直接以LL类型为索引 除速度外 无任何差异）
最后枚举搜索 范围内还没爆炸的点 使其爆炸 更新答案变量 并递归搜索连锁引爆
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
const int M=999997,Base=1e9+1;
int n,m;
LL hash1[M]; //开放寻址法 将降维得到大数key映射下来 维护find函数
int hash2[M],hash3[M];
bool st[M];
//存储key点地雷数量
//存储key点的地雷中 最大半径 int res;LL Getkey(int x,int y){ //降维 放大 return (LL)x*Base+y;
}//开放寻址法 将降维后的数 映射在int范围内
int find(LL x){ int t=(x %M+M)%M;while(hash1[t]!=-1&&hash1[t]!=x){t++;if(t==M) t=0;}return t;
}bool check(int x1,int x2,int y1,int y2,int r){int ans=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);return ans<=r*r; //利用r的平方 巧妙化解平方根的精度损失
}void dfs(int x,int y,int r){for(int i=-r;i<=r;i++){for(int j=-r;j<=r;j++){int xx=x+i,yy=y+j;LL key=Getkey(xx,yy);if(hash2[find(key)]&&check(xx,x,yy,y,r)&&!st[find(key)]){res+=hash2[find(key)];st[find(key)]=true;dfs(xx,yy,hash3[find(key)]);} }}return ;
}int main(){IOS;cin>>n>>m; memset(hash1,-1,sizeof hash1);int x,y,r;for(int i=0;i<n;i++){cin>>x>>y>>r;LL key=Getkey(x,y);hash1[find(key)]=key;hash2[find(key)]++;hash3[find(key)]=max(hash3[find(key)],r);}for(int i=0;i<m;i++){cin>>x>>y>>r;dfs(x,y,r);}cout<<res<<endl;return 0;
}如果觉得有用 就点赞＋收藏 关注一下吧！！！！