题目分析

根据题意，是一道图论的题目，将炸雷看作是图中的各个结点，一个炸雷与其爆炸范围内的炸雷用单向边相连，每一个排雷火箭相当于是图中的各个起点。如果依照该思路直接建图遍历的话，由于图中一共有1e5个点，最多会有1e5 ^ 2条边，因此在建图时最多耗时10 ^ 10，一定是会TLE的。

因此我们可以换一种思路，不去建图，不去建图的话我们怎么去求解点与点之间的连通性呢？（即判断一个点可以引爆哪些点），我们发现一个炸雷（或排雷火箭）的爆炸半径最大为10，因此一个炸雷（或排雷火箭）最多会引爆300多个炸雷，已知一共有1e5个点，我们可以通过枚举的方法判断每一个点的爆炸范围内“有哪些坐标存在可以引爆的点”，这样最多使用3e7的时间就能得出各个点与哪些点具有连通性（即将整张图遍历下来）。

下面一个问题就是如何判断某一个坐标上是否存在可以引爆的点？针对这一问题，我们可以使用哈希表，求解每一个坐标对应的哈希值，但有可能某一坐标上存在多个炸雷，对于这种情况，我们只需要保留爆炸范围最大的那一个炸雷，因此我们需要开一个数组id[N]专门用来存储某一个哈希值对应的是哪一个炸雷（即炸雷编号）

//建图 + 暴力搜图（4/11）
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 5e4 + 10;
struct Mine
{
    int x, y, r;
}a[N], b[N];
int n, m;
int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int ans;
bool st[N];
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            int s = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
            double dis = sqrt(s);
            if(dis <= (double)a[i].r) add(i, j);
        }

    for(int i = 1; i <= m; i ++)
    {
        scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].r);
        for(int j = 1; j <= n; j ++)
        {
            if(st[j] == 0)
            {
                int s = (b[i].x - a[j].x) * (b[i].x - a[j].x) + (b[i].y - a[j].y) * (b[i].y - a[j].y);
                double dis = sqrt(s);
                if(dis <= (double)b[i].r)
                {
                    int cnt = 0;
                    for(int k = h[j]; k != -1; k = ne[k])
                    {
                        int t = e[k];
                        if(st[t] == 0)
                        {
                            st[t] = 1;
                            cnt ++;
                        }
                    }
                    ans += cnt;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
//哈希表 + DFS（11/11）
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, M = 1e6 - 3;
typedef long long LL;
LL h[M];
bool st[M];
int id[M];
struct Circle
{
    int x, y, r;
}cir[N];
int n, m;
LL get(int x, int y)
{
    return x * 1000000003ll + y;
}
int find(int x, int y)
{
    LL k = get(x, y);
    int t = (k % M + M) % M;
    while(h[t] != -1 && h[t] != k)
    {
        t ++;
        if(t == M) t = 0;
    }
    return t;
}
int sqr(int x)
{
    return x * x;
}
void dfs(int x, int y, int r)
{
    st[find(x, y)] = 1;
    for(int i = x - r; i <= x + r; i ++)
        for(int j = y - r; j <= y + r; j ++)
            if(sqr(i - x) + sqr(j - y) <= sqr(r))
            {
                int t = find(i, j);
                if(id[t] != 0 && st[t] == 0) dfs(i, j, cir[id[t]].r);
            }    
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int x, y, r;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d%d%d", &x, &y, &r);
        cir[i] = {x, y, r};
        int t = find(x, y);//找到(x, y)对应的哈希值
        if(h[t] == -1) h[t] = get(x, y);
        //若某一坐标上有多个炸雷，只需保留爆炸范围最大的那一个：
        if(id[t] == 0 || cir[id[t]].r < cir[i].r) id[t] = i;
    }
    while(m --)
    {
        scanf("%d%d%d", &x, &y, &r);
        //枚举某一个点的爆炸范围内哪些坐标存在炸雷
        for(int i = x - r; i <= x + r; i ++)
            for(int j = y - r; j <= y + r; j ++)
                if(sqr(i - x) + sqr(j - y) <= sqr(r))
                {
                    int t = find(i, j);
                    if(id[t] != 0 && st[t] == 0) dfs(i, j, cir[id[t]].r);
                }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(st[find(cir[i].x, cir[i].y)] == 1) ans ++;
    }
    cout << ans << endl;
    return 0;
}