#P17833. [Ontak2022]REC
[Ontak2022]REC
题目描述
平面像素网格上最初画有 个轴平行矩形。矩形由左下角像素 和右上角像素 描述,端点像素包含在内。
接下来执行 条移动命令,每条命令把某个原始矩形沿八个方向之一移动整数距离 。移动不是一次完成,而是逐单位移动;每移动一个单位,都会在新位置留下一个永久的矩形图像。原图像也保留。因此一次距离为 的移动产生恰好 个新矩形图像。
后续命令继续移动该原始矩形的当前位置,已经留下的残影不再移动。所有命令执行后,对 个像素位置分别求它被多少个矩形图像覆盖,重合的图像分别计数。
输入格式
第一行三个整数 。
接下来 行,每行四个整数 ,描述一个初始矩形。
接下来 行,每行三个整数 ,表示把编号为 的原始矩形沿方向 移动 。方向编号如下:
| 编号 | 每一步的坐标变化 |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 |
最后 行,每行两个整数,表示一个询问像素。
输出格式
每个询问输出一行覆盖次数。
数据范围
,;矩形满足 、;,,;询问坐标在 内。
保证移动过程中所有矩形始终处于上述坐标范围内。答案需要使用64位整数。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤100,m=0 | 8 |
| 2 | m=0 | |
| 3 | m≤100 | 11 |
| 4 | 所有方向编号为偶数 | 13 |
| 5 | 每个矩形退化为单个像素 | 12 |
| 6 | 无额外限制 | 48 |
样例 1
输入:
1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2
输出:
0
2
1
样例 2
输入:
2 0 3
3 3 7 7
4 4 6 6
5 5
3 7
8 8
输出:
2
1
0