Hello codeforces!
I would like to search for help about a problem:
Given $$$n$$$ points $$$x_i, y_i(|x_i|,|y_i|<=10^4)$$$ and $$$q$$$ queries. The $$$j^th$$$ query consists of 3 integers $$$C_j x, C_j y, z_i$$$ $$$(|C_j x|, |C_j y|<=100,1<=z_i<=180)$$$: taking the center as $$$(C_jx, C_jy)$$$, rotate all n given points $$$z_i^o$$$ counterclockwise. Print the position of n points after q queries. Constraints: $$$1<=n,q<=10^5$$$
(This is not my problem, and i just want to ask for idea because there is no online judge for this)
Sample test:
Input:
3 1
1 1 90
2 1 180
1 2 90
3 3
Output:
4.0000000000 6.0000000000
I want to ask for ideas that works with large $$$n,q$$$(Up to $$$10^5$$$) because for $$$O(nq)$$$ just brute-force for all points.
Thanks!
I didn't work out the details but here is my idea: You can see the query as applying an affine transformation to $$$n$$$ points. For a given point $$$p$$$, the query transform it into $$$A(p - C)+C$$$ with $$$A$$$ being the $$$2\times2$$$ rotation matrix and $$$C$$$ being the center of rotation. For each point, just unroll the recursive transformation at that point to get the answer.