P2603 [ZJOI2008] Unordered Motion

Dr. D has conducted in-depth research in physics, with theorems in classical physics, astrophysics, and quantum physics named after him. Recently, he has been fascinated by the irregularity of particle motion. Firmly believing in the Bible, he is convinced that anything created by God must be orderly and rational, rather than random and chaotic. After long study, Dr. D found many trajectory fragments that appear quite frequently and stored them in a large database. He needs you to write a program that, for a given particle trajectory, counts the number of occurrences of each trajectory fragment from the database. For clarity, we define a particle’s trajectory as a sequence of points on a 2D plane, $(P_1, P_2, \dots, P_N)$. A subarray $[i, j]$ of the point sequence $P$ is defined as a contiguous subsequence in $P$, $(P_i, P_{i + 1}, \dots, P_j)$. A subarray $[u, v]$ of the point sequence $P$ is called an occurrence of the point sequence $Q = (Q_1, Q_2, \dots, Q_{v - u + 1})$ in $P$ if and only if, after a finite number of translations, rotations, reflections, and scalings, we obtain $Q'$ such that $\forall 1 \le k \le v - u + 1$, $Q'_k = P_{u + k - 1}$. Explanations for the four operations on point sequences: |Operation|Explanation| |:-:|:-:| |Translation|Let the translation vector be $(d_x, d_y)$. Then any point $(x, y)$ is mapped to $(x + d_x, y + d_y)$.| |Rotation|Let the rotation angle be $t$. Then any point $(x, y)$ is mapped to $(x \cos t - y \sin t, x \sin t + y \cos t)$.| |Reflection|Any point $(x, y)$ is mapped to $(x, -y)$.| |Scaling|Let the scaling factor be $p (p \ne 0)$. Then any point $(x, y)$ is mapped to $(px, py)$.|

The first line contains two integers $N, M$, representing the size of the point sequence of the trajectory to be processed and the number of trajectory fragments in the database, respectively. The next $M$ lines describe each trajectory fragment in order. Each line starts with a positive integer $K$, the length of the point sequence of that fragment. Then $2K$ integers follow, describing the $K$ points’ $x$- and $y$-coordinates in order. The next line contains $2N$ integers, describing the $x$- and $y$-coordinates of the $N$ points in the point sequence of the trajectory to be processed, in order. Note: In every trajectory in the input, any two adjacent points are different.

Output $M$ lines. For each fragment, output the number of its occurrences in the trajectory to be processed, in order.

Let the total length of all fragments be $L$. Constraints: - For $30\%$ of the testdata, $N, M, K \le 100$, $L \le 500$. - For $50\%$ of the testdata, $N, M, K \le 1000$, $L \le 5000$. - For $100\%$ of the testdata, $N, K \le 2 \times 10 ^ 5$, $L \le 2 \times 10 ^ 6$, and it is guaranteed that the absolute value of every given point coordinate in the input does not exceed $10 ^ 4$. Translated by ChatGPT 5