Problem LinkSetter: Trung Nguyen Tester: Hasan Jaddouh Editorialist: Bhuvnesh Jain DifficultyMEDIUM PrerequisitesMatrix Multiplication, Segment Trees, Sqrt Decomposition, Rotation Matrix ProblemThere are $N$ operators in a plane which rotate a given point $P$ around the point $i$ and angle $a_i$. We need to process 2 types of queries.
The final coordinates of the points should be given modulo ${10}^{9}+7$. ExplanationTo rotate a given point about origin by $\theta$, we need the rotation matrix as follows: $\left({\begin{array}{cc} \cos{\theta} & \sin{\theta}\\\sin{\theta} & \cos{\theta} \end{array}}\right)$ * $\left({\begin{array}{c} x\\y \end{array}}\right)$ = $\left({\begin{array}{c} x'\\y' \end{array}}\right)$. To see more details regarding the above matrix, refer to this wikipedia article. Now, to rotate the above matrix about another point, $P$, by same angle $\theta$, we first shift the origin to that point, $P$, and after rotation shift the origin back to the original one. This can be written as equations: $x'$ = $\cos{\theta} * (x  P.x)  \sin{\theta} * (y  P.y) + P.x$ $y'$ = $\sin{\theta} * (x  P.x) + \cos{\theta} * (y  P.y) + P.y$ This can also be written as rotation matrix of size $3 X 3$ as follows: $\left({\begin{array}{ccc} \cos{\theta} & \sin{\theta} & {(1\cos{\theta})*P.x + \sin{\theta}*P.y}\\\sin{\theta} & \cos{\theta} & {(1\cos{\theta})*P.y  \sin{\theta}*P.x}\\0 & 0 & 1 \end{array}}\right)$ * $\left({\begin{array}{c} x\\y\\1 \end{array}}\right)$ = $\left({\begin{array}{c} x'\\y'\\1 \end{array}}\right)$. To apply the operators one after the other, we first apply the first operator, get the new point and then another operator and so on. Thus, it basically means multiplying the corresponding rotation matrices and then applying the operator. Thus, now the problem reduces to the following :
This problem of range query and point update can be easily handled with segment trees keeping a Matrix in each node. For more details on segment trees, one can refer to this. Each update will be handled in ${d}^3 * \log{N}$ and each query will be handled in ${d}^{3} * \log{N}$, where $d = 3$, dimension of rotation matrix. Editorialist ApproachProblems involving range queries and point updates are mostly solved with Segment Trees or Sqrt Decomposition. Sqrt Decomposition is useful when we can precompute some useful information in a block in such a way that the whole block can be queried efficiently. The problem can be viewed as 2 independent coordinates systems undergoing rotation. The first is the rotation of given point by angle $\theta$ about the origin and the other is combined effect of the rotation of "changed" operators around the origin. To understand this, consider the initial point is $(x, y)$ and we apply to operators $(a_1, b_1, 90)$ and $(a_2, b_2, 90)$, in order. Then the resulting point will be $(y + (a_1 + b_1), x + (b_1  a_1))$ and finally $(x  (b_1  a_1) + (a_2 + b_2), y + (a_1 + b_1) + (b_2  a_2))$. This can be seen as:
The modified operators based on the angle are : (This is derived from the above 2 equation written above)
For a given a point, we can easily simulate the above process keeping the rotation effect of given point and of the "changed" operators separately. Thus, block queries, the idea behind splitting the array into blocks can be handled efficiently. Thus, we can simply solve the problem using sqrt decomposition. For details, refer to the editorialist solution below. Basic Tip: Sometimes deciding whether to use segment trees or sqrt decomposition can be difficult. According to me, I like to use Sqrt decomposition mostly when we apply some operation in a range in order as sometimes the order in which segment trees nodes can be combined becomes difficult to handle. Still, the choice depends on the reader and problem. A final note, don't forget to handle all operations in modulo field, i.e. modulo ${10}^{9} + 7$. Time Complexity$O({d}^{3} * N * \log{N})$, per test case, where $d = 3$, dimension of rotation matrix. or $O(N * sqrt(N))$, per test case. Space Complexity$O({d}^{2} * N)$ or $O(N * sqrt(N))$ Solution Links
This question is marked "community wiki".
asked 21 Dec '17, 12:23

"The problem can be viewed as 2 independent coordinates systems undergoing rotation. The first is the rotation of given point by angle θθ about the origin and the other is combined effect of the rotation of "changed" operators around the origin." can you please explain this a little more! I am weak in maths so, didn't able to understand it properly. answered 26 Dec '17, 14:02
