凉山西昌网站建设深圳网络推广培训中心

day9--[AHOI2017]寻找探监点--2.7

习题概述

题目描述

一个n×n 的网格图（标号由 1,1 开始）上有 m 个探测器，每个探测器有个探测半径 r ，问这 n×n 个点中有多少个点能被探测到。

输入格式

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

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

输出格式

能被探测到的点的个数。

 代码部分

#include<bits/stdc++.h>
using namespace std;
int x[10001],y[10001];
bool a[10001][10001];
int m,n,r;
int main()
{cin>>n>>m>>r;int ans=0;//通过循环读取m组x和y的坐标值for(int i1=1;i1<=m;i1++){cin>>x[i1]>>y[i1];{//嵌套两层循环遍历平面上的所有点，计算每个点与给定点之间的距离for(int j=1;j<=n;j++){double o1=sqrt((x[i1]-i)*(x[i1]-i)+(y[i1]-j)*(y[i1]-j)); //两点距离公式//并判断是否小于等于r，如果是则将a数组对应位置置为trueif(o1<=r) a[i][j]=true;} }
}
//遍历平面上的所有点，统计满足条件的点的数量for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]==1) ans++;cout<<ans;return 0;
}

心得体会

1.很简单的一道题，对于r最初的理解错了， r 指的是一个大范围 ！！！

2. 代码中的两点距离公式用于计算平面上两个点之间的距离，通过欧几里得距离公式来实现的。在代码中，两点的坐标分别为 (x[i1], y[i1]) 和 (i, j)。

根据欧几里得距离公式，两点之间的距离可以计算为：

d = sqrt(   (x[ i1] - i)^2 + (y[ i1] - j)^2  )

其中，^2 表示对其前面的数进行平方运算，sqrt() 函数表示求平方根。

double o1=sqrt( (x[ i1] - i )*(x[ i1] - i )+(y[ i1] - j )*(y[ i1] - j ) ) ;

3.代码总结：

（1）代码首先通过标准输入读取了三个整数n、m和r，分别表示网格图的大小、探测器的数量以及探测半径。

（2）然后通过循环逐个读取m个探测器的坐标位置(x, y)，接着使用嵌套的两层循环遍历整个n×n的网格图上的所有点，计算每个点到探测器的距离，如果小于等于探测半径r，则将对应的a数组位置置为true，表示该点能被探测到。

（3）最后再次使用嵌套的两层循环遍历整个网格图，统计满足被探测到条件的点的数量，并输出结果。