#P2603. Counting Occurrences of Similar Particle Trajectory Fragments
Counting Occurrences of Similar Particle Trajectory Fragments
Counting Occurrences of Similar Particle Trajectory Fragments
D.博士 has made significant contributions to physics with numerous theorems named after him. Recently, he has become fascinated by the irregularity of particle motion. Despite his deep research, his unwavering belief in the Bible leads him to assert that everything created by God must be orderly and governed by rational laws rather than random or chaotic.
After extensive research, D.博士 identified many trajectory fragments (i.e. contiguous subsequences of particle trajectories) that appear frequently. He stored these fragments in a large database. Your task is to help him by writing a program that, for a given particle trajectory, counts the number of times each trajectory fragment from the database appears in the trajectory.
A particle trajectory is defined as an ordered sequence of points in the two‐dimensional plane: \(P=(P_1, P_2, \dots, P_N)\). A contiguous subtrajectory (i.e. a sub‐sequence) from \(P_i\) to \(P_j\) is denoted by \([i,j]\) and is defined as \((P_i,P_{i+1},\dots,P_j)\). A subtrajectory \([u,v]\) is said to be an occurrence of a trajectory fragment \(Q=(Q_1,Q_2,\dots,Q_{v-u+1})\) if and only if by applying a finite sequence of the following operations on \(Q\), one can obtain a sequence \(Q'\) such that
[ \forall;1\le k\le (v-u+1),\quad Q'k=P{u+k-1}. ]
The four allowed operations are:
| Operation | Description |
|---|---|
| Translation | If the translation vector is \((d_x,d_y)\), a point \((x,y)\) becomes \((x+d_x,y+d_y)\). |
| Rotation | If the rotation angle is \(t\), a point \((x,y)\) becomes \((x\cos t - y\sin t,\; x\sin t + y\cos t)\). |
| Reflection | A point \((x,y)\) is reflected to \((x,-y)\). |
| Scaling | If the scaling factor is \(p\) (with \(p\ne0\)), a point \((x,y)\) becomes \((px,py)\). |
Effectively, these operations form the group of similarity transformations. Two trajectories (or fragments) are considered similar (or to have the same shape) if one can be transformed into the other by a combination of translation, rotation, reflection, and uniform scaling.
Input Format:
- The first line contains an integer \(N\) representing the number of points in the particle trajectory.
- The next \(N\) lines each contain two numbers representing the \(x\) and \(y\) coordinates of the trajectory points.
- The following line contains an integer \(M\) indicating the number of trajectory fragments stored in the database.
- For each of the next \(M\) fragments:
- The first line contains an integer \(L\), the length of the fragment.
- The following \(L\) lines each contain two numbers representing the \(x\) and \(y\) coordinates of the fragment's points.
Output Format:
- Output \(M\) lines. The \(i\)th line should contain a single integer, the count of occurrences of the \(i\)th trajectory fragment in the given particle trajectory. An occurrence is defined as a contiguous subtrajectory of the particle trajectory that is similar to the database fragment.
Note: Two trajectories are similar if their normalized signatures are identical, where the normalization is done as follows for sequences of length at least 2:
[ \text{normalized}(P)=\left(0,;1,;\frac{P_3-P_1}{P_2-P_1},;\dots,;\frac{P_N-P_1}{P_2-P_1}\right). ]
For fragments of length 1, every single point in the particle trajectory is considered a valid occurrence.
inputFormat
The input begins with an integer \(N\) (\(1 \le N \le \text{some limit}\)) representing the number of points in the particle trajectory. The next \(N\) lines each contain two space-separated numbers denoting the coordinates \(x\) and \(y\) of the trajectory.
Following this, an integer \(M\) is given representing the number of trajectory fragments in the database. For each fragment, a line with an integer \(L\) (the fragment's length) is provided, followed by \(L\) lines each containing two space-separated numbers \(x\) and \(y\).
outputFormat
Output exactly \(M\) lines. The \(i\)th line should display an integer indicating the number of times the \(i\)th trajectory fragment appears in the particle trajectory (as a contiguous subtrajectory after similarity transformation).
sample
3
0 0
1 1
2 2
1
2
0 0
1 1
2