[蓝桥杯 2022 省 B] 扫雷

题目描述

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第 2023-05-31i 个炸雷 (,,)(xi​,yi​,ri​) 表示在坐标 (,)(xi​,yi​) 处存在一个炸雷，它的爆炸范围是以半径为 ri​ 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (,,)(xj​,yj​,rj​) 表示这个排雷火箭将会在 (,)(xj​,yj​) 处爆炸，它的爆炸范围是以半径为 rj​ 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?

你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式

输入的第一行包含两个整数 n、m。

接下来的 n 行, 每行三个整数 ,,xi​,yi​,ri​, 表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 ,,xj​,yj​,rj​, 表示一个排雷火箭的信息。

输出格式

输出一个整数表示答案。

输入输出样例

2 1
2 2 4
4 4 2
0 0 5

2

说明/提示

【样例说明】

示例图如下, 排雷火箭 1 覆盖了炸雷 1 , 所以炸雷 1 被排除; 炸雷 1 又覆 盖了炸雷 2 , 所以炸雷 2 也被排除。

【评测用例规模与约定】

对于 40%40% 的评测用例: 0≤,≤109,0≤,≤103,1≤≤100≤x,y≤109,0≤n,m≤103,1≤r≤10.

对于 100%100% 的评测用例: 0≤,≤109,0≤,≤5×104,1≤≤100≤x,y≤109,0≤n,m≤5×104,1≤r≤10.

蓝桥杯 2022 省赛 B 组 H 题。

直接dfs的话,由于数据较弱,可以得60分,想要优化就加一个二分,因为不二分得话,每次dfs都要遍历所有n,我们可以找出这次dfs炸得左端点和右端点,这样就可以大大减少dfs范围

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1010;
struct node
{
    long long x,y,p;
    long long r;
    bool operator<(const node&w)const
    {
        return x<w.x;
    }
}boom[N];
struct node1
{
    long long x,y,r;
}fire[N];
long long n,m,res,x;
//int vis[M][M][11];
void dfs(long long x,long long y,int r)
{
    // long long Lmid,Rmid,L=0,R=n-1;
    // while(L<=R){
    //     Lmid=(L+R)/2;
    //     if(boom[Lmid].x<x-r)L=Lmid+1;
    //     else R=Lmid-1;
    // }
    // Lmid=L;
    // L=1,R=n;
    // while(L<=R){
    //     Rmid=(L+R)/2;
    //     if(boom[Rmid].x<=x+r)L=Rmid+1;
    //     else R=Rmid-1;
    // }
    //if(vis[x][y][r]==1) return;
    long long st,ed,l1=0,r1=n-1;
    while(l1<=r1)
    {
        st=(l1+r1)/2;
        if(boom[st].x<x-r) l1=st+1;
        else r=st-1;
    }
    st=l1,l1=0,r1=n-1;
    while(l1<=r1)
    {
        ed=(l1+r1)/2;
        if(boom[ed].x<=x+r) l1=ed-1;
        else r1=ed+1; 
    }
    ed=r1;
    for(int i=st;i<=ed;i++) if((x-boom[i].x)*(x-boom[i].x)+(y-boom[i].y)*(y-boom[i].y)<=r*r&&boom[i].p==1)
    {
        res++;
        boom[i].p=0;
        dfs(boom[i].x,boom[i].y,boom[i].r);
        //vis[boom[i].x][boom[i].y][boom[i].r]=1;
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>boom[i].x>>boom[i].y>>boom[i].r,boom[i].p=1;
    for(int i=0;i<m;i++) cin>>fire[i].x>>fire[i].y>>fire[i].r;
    sort(boom,boom+n);
    for(int i=0;i<m;i++) dfs(fire[i].x,fire[i].y,fire[i].r);
    cout<<res;
    return 0;
}