题解：P11254 [GDKOI2023 普及组] Macaron

· · 题解

题意

给你一个长 n 宽 m 的整点坐标系，上面有 k 个关键点。求标记完这些点为圆心的半径为 r 的圆上的整点后有多少个没标记的点。

数据范围

k\le10^6;n,m,r\le10^3,n\times m\le10^9

思路

数据很小，我们可以：

1.预处理出一个点正上方和正下方最近的关键点这可以用在后期处理上，这是十分容易但很有用的。

2.对于每个点，根据刚才的距离可以用一个一个标记周围的点。