题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 50010, M = 999997;
typedef long long ll;
int n, m;
struct Circle
{
    int x, y, r;
}cir[N];
ll h[M];
int id[M];
bool st[M];
ll get(int x, int y)
{
    return x * 1000000001ll + y;
}
int find(int x, int y)//开放寻址法
{
    ll key = get(x, y);
    int t = (key % M + M) % M;//如果是负数就这样写
    while (h[t] != -1 && h[t] != key)
        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)] = true;

    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] && !st[t])//如果对应坑位有地雷且没有引爆
                    dfs(i, j, cir[id[t]].r);
            }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y,r;
        cin>>x>>y>>r;
        cir[i]={x,y,r};//cir数组存所有的地雷;
        int t=find(x,y);//计算点在哈希表中的坑位;
        if(h[t]==-1)h[t]=get(x,y);//如果对应坑位没有地雷,就放进去;
        if(!id[t]||cir[id[t]].r<r)//如果这个坑位没有地雷，
        id[t]=i;                  //或者坑位上的地雷半径比当前这个小，
    }                             //就更新这个坑位放的第几个地雷;
    while(m--)
    {
        int x,y,r;
        cin>>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]&&!st[t])//如果对应坑位有地雷且没有引爆
                    dfs(i,j,cir[id[t]].r); //就以其为中心遍历
                }
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)//遍历所有地雷,看哪些地雷被引爆了;
    if(st[find(cir[i].x,cir[i].y)])
    res++;
    cout<<res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla