// 请把代码粘贴在这里

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

// 自定义哈希函数,用于 unordered_map 支持 pair<int, int>
struct HashPair {
size_t operator()(const pii& p) const {
return (size_t)p.first 1000000007 + p.second;
}
};

// 存储:坐标 -> {最大半径, 数量}
unordered_map<pii, pair<int, int>, HashPair> mp;
// 记录已引爆的坐标
unordered_set<pii, HashPair> visited;

int n, m;
int ans = 0;

// 深度优先搜索
void dfs(int x, int y, int r) {
// 扫描正方形范围:[x-r, x+r]
[y-r, y+r]
// 题目保证 r <= 10,所以这个循环最多执行 2121 = 441 次
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
pii p = {i, j};

// 剪枝1:如果这个坐标已经炸过了,跳过
if (visited.count(p)) continue;

// 剪枝2:如果这个坐标根本没有,跳过
if (!mp.count(p)) continue;

// 剪枝3:精确判断是否在圆内 (使用平方避免 sqrt)
long long dx = x - i;
long long dy = y - j;
// 注意:题目逻辑通常是圆心到点的距离 <= 半径
if (dx
dx + dy dy > (long long)r r) continue;

// --- 命中 ---
visited.insert(p); // 标记爆炸
ans += mp[p].second; // 累加该坐标的数量

// 递归:用这个新炸的最大半径继续引爆
dfs(i, j, mp[p].first);
}
}
}

int main() {
// 优化 IO
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m;

// 1. 读入
for (int i = 0; i < n; i++) {
int x, y, r;
cin >> x >> y >> r;
pii p = {x, y};
// 如果同一点有多个,保留数量,半径取最大值
if (mp.count(p)) {
mp[p].second++;
mp[p].first = max(mp[p].first, r);
} else {
mp[p] = {r, 1};
}
}

// 2. 读入火箭并触发 DFS
for (int i = 0; i < m; i++) {
int x, y, r;
cin >> x >> y >> r;
// 火箭也是引爆源,直接开始 DFS
dfs(x, y, r);
}

cout << ans << endl;

return 0;
}
0 回复 0 转发 0 喜欢 4 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!