中文博客网站模板,网上服务厅,南京知名室内设计公司,新手这样开办公司day9--[AHOI2017]寻找探监点--2.7
习题概述
题目描述
一个nn 的网格图#xff08;标号由 1,1 开始#xff09;上有 m 个探测器#xff0c;每个探测器有个探测半径 r #xff0c;问这 nn 个点中有多少个点能被探测到。
输入格式
第一行 3 个整数 n,m,r。
接下来 m 行标号由 1,1 开始上有 m 个探测器每个探测器有个探测半径 r 问这 n×n 个点中有多少个点能被探测到。
输入格式
第一行 3 个整数 n,m,r。
接下来 m 行每行两个整数x,y表示第 i 个探测器的坐标。
输出格式
能被探测到的点的个数。 代码部分
#includebits/stdc.h
using namespace std;
int x[10001],y[10001];
bool a[10001][10001];
int m,n,r;
int main()
{cinnmr;int ans0;//通过循环读取m组x和y的坐标值for(int i11;i1m;i1){cinx[i1]y[i1];{//嵌套两层循环遍历平面上的所有点计算每个点与给定点之间的距离for(int j1;jn;j){double o1sqrt((x[i1]-i)*(x[i1]-i)(y[i1]-j)*(y[i1]-j)); //两点距离公式//并判断是否小于等于r如果是则将a数组对应位置置为trueif(o1r) a[i][j]true;} }
}
//遍历平面上的所有点统计满足条件的点的数量for(int i1;in;i)for(int j1;jn;j)if(a[i][j]1) ans;coutans;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 o1sqrt( (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最后再次使用嵌套的两层循环遍历整个网格图统计满足被探测到条件的点的数量并输出结果。
