63 lines
1.9 KiB
C++
63 lines
1.9 KiB
C++
// lanqiao 2110 (扫雷)
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
typedef pair<int, int> pii;
|
||
struct circle{ int x, y, r; };
|
||
// 解法: 图的搜索处理图的连通性
|
||
// 检查圆c是否覆盖点p
|
||
bool check(circle c, pii p){
|
||
int t1 = (c.x - p.first)*(c.x - p.first);
|
||
int t2 = (c.y - p.second)*(c.y - p.second);
|
||
return c.r >= sqrt(t1 + t2);
|
||
}
|
||
int main(){
|
||
int n, m;
|
||
cin >> n >> m;
|
||
// key: 代表坐标 x, y value: 代表最大半径和对应数量
|
||
map<pii, pii> mp;
|
||
// 处理炸弹
|
||
for(int i = 1; i <= n; i++){
|
||
int x, y, r; cin >> x >> y >> r;
|
||
// 优化
|
||
pii p = {x, y};
|
||
mp[p].second++; // 统计同一个x, y点炸弹的数量
|
||
mp[p].first = max(mp[p].first, r); // 统计同一个x, y点炸弹的最大半径
|
||
}
|
||
// 处理火箭弹
|
||
queue<circle> q;
|
||
for(int i = 1; i <= m; i++){
|
||
int x, y, r; cin >> x >> y >> r;
|
||
q.push({x, y, r});
|
||
}
|
||
// 记录爆炸坐标
|
||
set<pii> s;
|
||
// 记录答案，即爆炸数量
|
||
int ans = 0;
|
||
while(!q.empty()){
|
||
circle cur = q.front(); q.pop();
|
||
int x = cur.x, y = cur.y, r = cur.r;
|
||
// 以i,j为中心，长度均为2r的正方形范围，这里为了方便直接枚举正方形，后续通过判定排除无效点
|
||
for(int i = x - r; i <= x + r; i++){
|
||
for(int j = y - r; j <= y + r; j++){
|
||
pii p = {i, j};
|
||
// 已爆炸，不做处理
|
||
if(s.count(p)) continue;
|
||
// 该坐标无雷，不处理
|
||
if(!mp.count(p)) continue;
|
||
// 不在范围
|
||
if(!check(cur, p)) continue;
|
||
s.insert(p);
|
||
ans += mp[p].second;
|
||
q.push({i, j, mp[p].first});
|
||
}
|
||
}
|
||
}
|
||
cout << ans << endl;
|
||
return 0;
|
||
}
|
||
/* test samples -> 2
|
||
2 1
|
||
2 2 4
|
||
4 4 2
|
||
0 0 5
|
||
*/ |