青岛模板建站代理,游戏app开发,苏州网络科技公司有哪些,广东中山今天最新通知题目描述
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下#xff0c; 在一个二维平面上放置着 n 个炸雷#xff0c;第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处存在一个炸雷#xff0c;它的爆炸范围是以半径为 ri 的一个圆。
为了顺利通过这片土…题目描述
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下 在一个二维平面上放置着 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表示一个排雷火箭的信息。
输出一个整数表示答案。
样例输入 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.
第一种图的深度优先遍历邻接表实现 由于点数有1e5,那么遍历所有图上的点是否联通需要O(n^2)也就是需要2.5e9 明显会超时。(WA)
#includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
#define int long long
using namespace std;
const int N5e310;
bool st[N];
int n,m;
//存炸弹
struct node
{int x,y,r;
}stu[N];
vectorintv[N];
//判断是否在这颗雷是否在这个圆
bool sqr(int x,int y,int xx,int yy,int r)
{if((xx-x)*(xx-x)(yy-y)*(yy-y)r*r) return true;return false;
}
//连成一个连通图 雷在这个雷的范围内的就扩展
void add(int idx)
{int xstu[idx].x,ystu[idx].y,rstu[idx].r;for(int i1;in;i){if(i!idx){if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}}
}
//看有多少颗符合要求的炸弹
int dfs(int idx)
{int sum1;st[idx]1;for(int i0;iv[idx].size();i){int jv[idx][i];if(!st[j]){st[j]1;sumdfs(j);}}return sum;
}
//计算这颗排雷火箭能炸多少地雷
int dfs_Trave(int x,int y,int r)
{int sum0;for(int i1;in;i){if(sqr(stu[i].x,stu[i].y,x,y,r)){if(!st[i])sumdfs(i);}}return sum;
}
signed main()
{cinnm;for(int i1;in;i){int x,y,r;cinxyr;stu[i]{x,y,r};}for(int i1;in;i){add(i);}int sum0;for(int i1;im;i){int x,y,r;cinxyr;sumdfs_Trave(x,y,r);}coutsumendl;return 0;
}AC版
#includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
#includemap
#includeset
#define int long long
using namespace std;
typedef pairint,intPII;
const int N5e410;
bool st[N];
mapPII,intmp;
int n,m,n10;
//存炸弹
struct node
{int x,y,r,cnt;bool operator (node const a) const{if(x!a.x)return xa.x;return ya.y;}
}stu[N];
/*
bool cmp(node xx,node yy)
{if(xx.xyy.x) return xx.yyy.y;return xx.xyy.x;
}*/
vectorintv[N];
//判断是否在这颗雷是否在这个圆
bool sqr(int x,int y,int xx,int yy,int r)
{if((xx-x)*(xx-x)(yy-y)*(yy-y)r*r) return true;return false;
}
//连成一个连通图 雷在这个雷的范围内的就扩展
void add(int idx)
{int xstu[idx].x,ystu[idx].y,rstu[idx].r;for(int iidx-1;i0;i--){if(r(x-stu[i].x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}for(int iidx1;in1;i){if(r(stu[i].x-x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}
}
//看有多少颗符合要求的炸弹
int dfs(int idx)
{int sumstu[idx].cnt;st[idx]1;for(int i0;iv[idx].size();i){int jv[idx][i];if(!st[j]){st[j]1;sumdfs(j);}}return sum;
}
//计算这颗排雷火箭能炸多少地雷
int dfs_Trave(int x,int y,int r)
{node e1{x-r,y,r,1},e2{xr,y,r,1};int l1lower_bound(stu1,stu1n1,e1)-stu;int r1upper_bound(stu1,stu1n1,e2)-stu;int sum0;for(int il1;ir1;i){if(sqr(stu[i].x,stu[i].y,x,y,r)){if(!st[i])sumdfs(i);}}return sum;
}
signed main()
{cinnm;for(int i1;in;i){int x,y,r;cinxyr;int idmp[{x,y}];if(id!0){stu[id].rmax(stu[id].r,r);stu[id].cnt;}else{int xx1;n1;stu[n1].xx;stu[n1].yy;stu[n1].rr;stu[n1].cnt1;mp[{x,y}]n1;}}sort(stu1,stu1n1);for(int i1;in1;i){add(i);}int sum0;for(int i1;im;i){int x,y,r;cinxyr;sumdfs_Trave(x,y,r);}coutsumendl;return 0;
}
