A6695. 「ZJOI2008」无序运动
编程题
省选/NOI-
知识点
题目描述
D 博士对物理有着深入的研究，经典物理、天体物理、量子物理都有着以他的名字命名的定理。最近 D 博士着迷于研究粒子运动的无规则性。对圣经深信不疑的他相信，上帝创造的任何事物必然是有序的、有理可循的，而不是无规则的、混沌的。
经过长时间的研究，D 博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断储存在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。
为清楚起见，我们定义一个粒子的轨迹为二维平面上的一个点列（$p_1, p_2, \dots, p_n$）。点列 $p$ 的一个子列 $[i, j]$ 定义为 $p$ 中一段连续的子序列（$p_i, p_{i + 1}, \dots, p_j$）。点列 P 的一个子列 $[u, v]$ 被称为点列 $q = q_1, q_2, \dots, q_{v - u + 1}$）在 $p$ 中的一次出现，当且仅当 $q$ 经过有限次的平移、旋转、翻转、放缩之后得到 $q^{\prime}$ 满足 $q^{\prime}_k = p_{u + k - 1}$（$k = 1, \dots, u–v+1$）。
经过长时间的研究，D 博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断储存在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。
为清楚起见，我们定义一个粒子的轨迹为二维平面上的一个点列（$p_1, p_2, \dots, p_n$）。点列 $p$ 的一个子列 $[i, j]$ 定义为 $p$ 中一段连续的子序列（$p_i, p_{i + 1}, \dots, p_j$）。点列 P 的一个子列 $[u, v]$ 被称为点列 $q = q_1, q_2, \dots, q_{v - u + 1}$）在 $p$ 中的一次出现，当且仅当 $q$ 经过有限次的平移、旋转、翻转、放缩之后得到 $q^{\prime}$ 满足 $q^{\prime}_k = p_{u + k - 1}$（$k = 1, \dots, u–v+1$）。
输入格式
输入第一行两个整数 $n, m$，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。
接下来 $m$ 行依次给出每个轨迹片断。每行先是一个正整数 $k$，表示该轨迹片断点列的长度。然后 $2k$ 个整数，依次描述点列中的 $k$ 个点的横坐标与纵坐标。
接下来一行 $2n$ 个整数，依次描述待处理的粒子运动轨迹的点列中 $n$ 个点的横坐标与纵坐标。
注：输入中的每条轨迹中任意相邻两点不会相同。
接下来 $m$ 行依次给出每个轨迹片断。每行先是一个正整数 $k$，表示该轨迹片断点列的长度。然后 $2k$ 个整数，依次描述点列中的 $k$ 个点的横坐标与纵坐标。
接下来一行 $2n$ 个整数，依次描述待处理的粒子运动轨迹的点列中 $n$ 个点的横坐标与纵坐标。
注：输入中的每条轨迹中任意相邻两点不会相同。
输出格式
输出应包含 $m$ 行，依次给出每个片段在待处理运动轨迹中的出现次数。
输入输出样例
输入 #1
3 2 2 17 0 10 1 3 0 0 1 0 1 -1 0 0 1 0 1 1
输出 #1
2 1
说明/提示
- 对于 $30\%$ 的数据，$1\le n, m, k\le100$，片段总长度 $\le 500$。
- 对于 $50\%$ 的数据，$1\le n,m,k\le10^3$，片段总长度 $\le5\times 10^3$。
- 对于 $100\%$ 的数据，满足 $1 \le n, k \le 2 \times 10^5$，片段总长度 $\le 2 \times 10^4$，所有点坐标绝对值均不大于 $10^4$。
| 对平面 $X-Y$ 进行四种操作的解释 | 对平面 $X-Y$ 进行四种操作的解释 |
| - | - |
| 平移 | 设平移向量为 $(d_x, d_y)，则任意点 $(x, y)$ 平移后的结果为 $(x + d_x, y + d_y)$ |
| 旋转 | 设旋转角为 $t$，则任意点 $(x, y)$ 旋转后的结果为 $(x \cos t - y \sin t, x \sin t + y \cos t)$ |
| 翻转 | 任意点 $(x, y)$ 翻转后的结果为 $(x, -y)$ |
| 放缩 | 设放缩比例为 $p$（$p \ne 0$），则任意点 $(x, y)$ 放缩后的结果为 $(px, py)$ |
- 对于 $50\%$ 的数据，$1\le n,m,k\le10^3$，片段总长度 $\le5\times 10^3$。
- 对于 $100\%$ 的数据，满足 $1 \le n, k \le 2 \times 10^5$，片段总长度 $\le 2 \times 10^4$，所有点坐标绝对值均不大于 $10^4$。
| 对平面 $X-Y$ 进行四种操作的解释 | 对平面 $X-Y$ 进行四种操作的解释 |
| - | - |
| 平移 | 设平移向量为 $(d_x, d_y)，则任意点 $(x, y)$ 平移后的结果为 $(x + d_x, y + d_y)$ |
| 旋转 | 设旋转角为 $t$，则任意点 $(x, y)$ 旋转后的结果为 $(x \cos t - y \sin t, x \sin t + y \cos t)$ |
| 翻转 | 任意点 $(x, y)$ 翻转后的结果为 $(x, -y)$ |
| 放缩 | 设放缩比例为 $p$（$p \ne 0$），则任意点 $(x, y)$ 放缩后的结果为 $(px, py)$ |