信号覆盖(暴力模拟)
❓️
问题描述
小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为
(0, 0)
,
东南角坐标为
(W, 0)
, 西北角坐标为
(0, H)
, 东北角坐标为
(W, H)
。其中
W, H
都是整数。
他在
n
个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为
R
的圆形(包括边缘)。
为了对信号覆盖的情况进行检查,小蓝打算在区域内的所有横纵坐标为整数的点进行测试,检查信号状
态。其中横坐标范围为
0
到
W
,纵坐标范围为
0
到
H
,总共测试
(W+1) * (H+1)
个点。
给定信号塔的位置,请问这
(W+1)*(H+1)
个点中有多少个点被信号覆盖。
输入格式
输入第一行包含四个整数
W, H, n, R
,相邻整数之间使用一个空格分隔。 接下来
n
行,每行包含两个整
数
x, y
,表示一个信号塔的坐标。信号塔可能重合,表示两个信号发射器装在了同一个位置。
输出格式
输出一行包含一个整数,表示答案。
样例输入
10 10 2 5
0 0
7 0
样例输出
57
W,H,n,R = map(int,input().split())
def juli(x1,y1,x2,y2):#计算两点之间距离
return((x1-x2)**2 + (y1-y2)**2)**0.5
vis = [[0]*(H+1) for i in range(W+1)]#记录标记过的点
ans = 0
for k in range(n):
x,y=map(int,input().split())
for i in range(x-R,x+R+1):
for j in range(y-R,y+R+1):
if 0<=i<=W and 0<=j<=H and vis[i][j]==0 and juli(i,j,x,y)<=R:#距离信号塔R以内 且在坐标中 未标记过的点
vis[i][j]=1#标记
ans+=1
print(ans)