4407. 扫雷 - AcWing题库高质量的算法题库
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PLL;
typedef long long ll;
const int N = 1e5 + 4;
map<PLL, int>a;
PLL c[N];
bool within(PLL p, PLL q, int r) {
int x = p.first - q.first;
int y = p.second - q.second;
ll t = x * x + y * y;
return sqrt(t) <= r;
}
int main() {
// freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
int r;
cin >> c[i].first >> c[i].second >> r;
a[c[i]] = max(a[c[i]], r);
}
for (int i = 0; i < m; i++) { // 每个火箭
int x, y, r;
cin >> x >> y >> r;
map<PLL, int>::iterator it, temp;
vector<PLL>node;
vector<int>R;
for (it = a.begin(); it != a.end(); it++) { // 每个雷
if (within(it->first, make_pair(x, y), r)) { // 如果雷在火箭爆炸范围内
node.push_back(it->first);
R.push_back(it->second);
}
}
for (int j = 0; j < node.size(); j++) {
for (it = a.begin(); it != a.end();) { // 去掉node爆炸范围内的雷
if (within(it->first, node[j], R[j])) {
temp = it;
it++;
a.erase(temp);
} else {
it++;
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (a.find(c[i]) == a.end()) {
ans++;
}
}
cout << ans;
return 0;
}
