2 条题解
-
1
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; typedef long long ll; map<PII, int> coordinate, cnt; /* coordinate存坐标(x, y)和半径r的映射关系 cnt存坐标(x, y)和该坐标上炸雷总数的映射关系 */ int n, m, res; ll distance(int x1, int y1, int x2, int y2) { return (ll)pow(x1 - x2, 2) + pow(y1 - y2, 2); } void bfs() { queue<pair<PII, int>> q; for(int i = 0; i < m; i ++ ) { int x, y, r; cin>>x>>y>>r; q.push({{x, y}, r}); } while(q.size()) { auto u = q.front(); q.pop(); int x = u.first.first, y = u.first.second, r = u.second; //搜索的时候用r搜 因为r很小很小 for(int i = x - r; i <= x + r; i ++ ) for(int j = y - r; j <= y + r; j ++ ) { //如果不在覆盖范围内 continue if(distance(x, y, i, j) > r*r)continue; auto t = make_pair(i, j); //如果这个点上有雷 if(coordinate.count(t)) { res += cnt[t]; q.push({t, coordinate[t]}); coordinate.erase(t); } } } cout<<res<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; for(int i = 1; i <= n; i ++ ) { int x, y, r; cin>>x>>y>>r; coordinate[{x, y}] = max(coordinate[{x, y}], r); //显然如果一个点上 有两个雷 那么有效的是半径大的 cnt[{x, y}] ++; } bfs(); return 0; }
信息
- ID
- 973
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 48
- 已通过
- 7
- 上传者