```cpp #include <bits/stdc++.h> using namespace std; #define int long long map<pair<int, int>, int> boom; set<pair<int, int>> res; bool judge(int x1, int y1, int x2, int y2, int r) { int a = abs(x1 - x2), b = abs(y1 - y2); if (a > r || b > r)//防止爆longlong return false; return a * a + b * b <= r * r; } void dfs(int x, int y, int r) { for (int j = -r; j <= r; ++j) for (int k = -r; k <= r; ++k) { int dx = x + j, dy = y + k; if (judge(x, y, dx, dy, r)) { if (boom.count({dx, dy}) && !res.count({dx, dy})) { res.insert({dx, dy}); dfs(dx, dy, boom[{dx, dy}]); } } } return; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { int x, y, r; cin >> x >> y >> r; boom[{x, y}] = r; } for (int i = 0; i < m; ++i) { int x, y, r; cin >> x >> y >> r; for (int j = -r; j <= r; ++j) for (int k = -r; k <= r; ++k) { int dx = x + j, dy = y + k; if (judge(x, y, dx, dy, r)) { if (boom.count({dx, dy}) && !res.count({dx, dy})) { res.insert({dx, dy}); dfs(dx, dy, boom[{dx, dy}]); } } } } cout << res.size() << endl; return 0; } ```

暴力模拟: 模拟爆炸的过程, 因为不知道怎么寻找就近的点, 所以全部遍历一次, 如果可以被波及, 则删除它, 并且入队, 继续模拟本次爆炸 - 使用list可以实现一个 $O(1)$ 的删除 - 使用 $(x_1-x_2)^2+(y_1-y_2)^2\le r^2$ 判断是否在爆炸范围, (而不是使用根号再判断,) 更快 时间复杂度 $O(n^2)$ ```cpp #include <cstdio> #include <iostream> #include <algorithm> #include <utility> #include <queue> #include <map> #include <set> #include <vector> #include <tuple> #include <functional> #include <unordered_set> #include <unordered_map> #include <list> #include <cmath> using namespace std; using ll = long long; using boom = tuple<int, int, int>; // x, y, r int main() { int n, m; scanf("%d %d", &n, &m); list<boom> zadan; for (int i = 0; i < n; ++i) { int x, y, r; scanf("%d %d %d", &x, &y, &r); zadan.push_back(make_tuple(x, y, r)); } queue<boom> pq; int res = 0; for (int i = 0; i < m; ++i) { int px, py, pr; scanf("%d %d %d", &px, &py, &pr); pq.push(make_tuple(px, py, pr)); while (pq.size()) { int x, y, r; tie(x, y, r) = pq.front(); pq.pop(); for (auto it = zadan.begin(); it != zadan.end(); ++it) { int kx, ky, kr; tie(kx, ky, kr) = *it; kx -= x; ky -= y; if (kx * kx + ky * ky <= r * r) { pq.push(make_tuple(kx + x, ky + y, kr)); auto tmp = it; ++it; zadan.erase(tmp); ++res; } } } } printf("%d\n", res); return 0; } ```