#212062. [KTSC 2021] 卡顿 / lag

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 1차 선발고사 #3 렉。

请注意，你不需要也不应该实现 main 函数。具体实现方式见【实现细节】部分。

警告：滥用本题评测一次即可封号。

在一台老旧计算机上使用画图程序。画图程序的屏幕是由称为像素的格子组成的网格。

最左下角的像素坐标为 ，向右第 个、向上第 个像素的坐标为 。初始屏幕上画有 个具有垂直和水平边的矩形。矩形由该区域内包含的像素表示。

将对 个矩形执行 个移动命令。矩形的移动方向包括东、西、南、北四个方向，以及东北、西北、东南、西南（与水平轴成 度角）四个方向。此外，移动距离 也会给定。换句话说，移动命令由方向和距离组成。具体来说，如果矩形的最左下角像素坐标为 ，那么向东、北、西、南方向移动距离 后，其左下角坐标将分别变为 。而向东北、西北、西南、东南方向移动距离 后，其左下角坐标将分别变为 （见图 1）。

屏幕上矩形 的移动距离 是通过依次在每移动距离 时快速显示 的位置来实现的。但由于计算机过于老旧， 移动时会出现严重的卡顿。因此， 移动过程中绘制的所有样子都会保留在屏幕上。也就是说， 移动距离 后，屏幕上会新增 个矩形。例如，在图 2 中，矩形向东北方向移动距离 后，会新增 个矩形，最终屏幕上共有 个矩形。移动结束后， 将位于东北方向的终点。

执行完 个移动命令后，将给出 个查询。每个查询给出平面上的一个像素 。对于每个查询，需要输出包含像素 的矩形数量。

实现细节

你需要实现以下函数：

vector<long long int> count_enclosing_rectangle(vector< pair<int, int> > R1, vector< pair<int, int> > R2, vector<int> V, vector<int> I, vector<int> D, vector< pair<int, int> > P )

• 该函数仅被调用一次。
• 参数数组 R1 和 R2 的大小为 。数组的每个元素表示初始给定的 个矩形中的一个，R1[i] 和 R2[i] 分别表示矩形 的最左下角和最右上角像素的坐标。坐标以 的形式给出，表示位置为 。矩形编号为 到 的整数。
• 参数数组 V、I、D 的大小为 。数组的每个元素表示 个矩形移动中的一个，表示矩形 I[i] 向方向 V[i] 移动距离 D[i]。
• 参数数组 P 的大小为 。数组 P 的每个元素表示查询对应的平面上的像素 的坐标，以 的形式给出。
• 该函数需要计算每个查询像素 被多少个矩形包含，并将结果存储在长度为 的数组中返回。第 个值应为第 个查询的结果（）。

提交的源代码中不得调用任何输入输出函数。

示例评测程序按以下格式接收输入：

• 第 行：
• 第 行（）：
• 第 行（）：
• 第 行（）：

示例评测程序输出以下内容：

• 第 行（）：函数 count_enclosing_rectangle 返回数组的第 个元素。

请注意，示例评测程序与实际评测程序可能不同。

样例输入 1

3 3 4
1 1 2 2
3 3 4 4
4 1 6 2
1 1 2
6 2 2
2 3 3
3 3
4 3
3 2
5 3

样例输出 1

4
5
3
2

约束条件

• 屏幕上的坐标值在 到 之间。任何矩形包含的所有像素的坐标值始终在此范围内，移动后也满足此条件。查询的像素也满足此条件。
• 矩形移动方向 V[i] 的值为：（东）、（东北）、（北）、（西北）、（西）、（西南）、（南）、（东南）。

子任务

1. （ 分）
   • ，
2. （ 分）
3. （ 分）
4. （ 分）
   • （），即矩形仅沿水平或垂直方向移动。
5. （ 分）
   • （）
6. （ 分）
   • 无额外约束条件。

评分标准

只有当 count_enclosing_rectangle 函数返回的数组长度为 ，并且与正确答案数组的所有元素完全一致时，才判定为该测试用例正确。

示例

• ，，，R1 = [(1, 1), (3, 3), (4, 1)]，R2 = [(2, 2), (4, 4), (6, 2)]，V = [1, 6, 2]，I = [1, 2, 3]，D = [2, 2, 3]，P = [(3, 3), (4, 3), (3, 2), (5, 3)]时，考虑以下情况。

  评测程序将调用以下函数：

  count_enclosing_rectangle(R1, R2, V, I, D, P)
  

  在此示例中， 个矩形的 次移动共生成 个新矩形，因此最终屏幕上有 个矩形。像素 被矩形 生成的 个矩形和矩形 生成的 个矩形包含，因此共被 个矩形包含。注意，矩形 的第三次移动生成的矩形与矩形 的矩形虽然区域相同，但被视为不同的矩形。

  

  函数 count_enclosing_rectangle 应返回数组 [4, 5, 3, 2]。