题目描述

一个n*n的网格图上有m个探测器，每个探测器有个探测半径r，问这n*n个点中有多少个点能被探测到。

输入输出格式

输入格式：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 （1<=r<n<=5000）

（1<=m<=5000）

第一行3个整数n,m,r

接下来m行，每行两个整数x,y表示第i个探测器的坐标

 

输出格式：

 

能被探测到的点的个数

输入输出样例

输入样例#1：  复制 
5 2 1
3 3
4 2
输出样例#1：  复制 
8
  

#include <iostream> #include <cmath> #include <algorithm>
using namespace std; int an[5002][5002]; double longth (int r,int d) { return sqrt(r*r-d*d); } int main () { int n,m,r,x,y,ln,rn,listr,listl; int ans=0; cin>>n>>m>>r; for(int i=0;i<m;i++) { cin>>x>>y; ln=max(x-r,1);//上边界
        rn=min(x+r,n);//下边界
        for(int j=ln;j<=rn;j++)//列数
 { listl=max(1,(int)ceil(y-longth(r,x-j)));//左边界//是将此坐标整体进行向下取整
            listr=min(n,(int)floor(y+longth(r,x-j)));//右边界//同理
            an[j][listl]+=1;//差分标记
            an[j][listr+1]-=1; } } for(int i=1;i<=n;i++)//前缀和后遍历取0(统计零解多次探照问题)//反向计数
        for (int j = 1; j <= n; j++) { an[i][j] += an[i][j - 1]; if (an[i][j]==0) ans++; } cout<<n*n-ans<<endl; return 0; }
  

 

 
 

 


    

        

            

                

                    

                        
                    

                    

                        

                            扫码关注我们
                        

                        

                            微信号：SRE实战
                        

                        

                            拒绝背锅 运筹帷幄