Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### grinding_codexp's blog

By grinding_codexp, history, 5 weeks ago,

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!

• +1

 » 5 weeks ago, # |   +9 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.