P3717 [AHOI2017初中组]cover

[AHOI2017初中组]cover

题目背景

以下为不影响题意的简化版题目。

题目描述

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

输入格式

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

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

输出格式

能被探测到的点的个数。

样例 #1

样例输入 #1

5 2 1
3 3
4 2
1
2
3

样例输出 #1

8
1

提示

$1\le n,m\le 100$

解析

纯暴力模拟，注意勾股定理就行了。

#include
using namespace std;
const int N=1002;
bool b[N][N];
int n,m,r,x,y,ans;
int main()
{
	cin>>n>>m>>r;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		for(int j=max(1,y-r);j<=min(n,y+r);j++)
		 for(int k=max(1,x-r);k<=min(n,x+r);k++)
		  if((j-y)*(j-y)+(k-x)*(k-x)<=r*r)
		   b[j][k]=1;
	}
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  if(b[i][j])
	   ans++;
	cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22