Блог пользователя grinding_codexp

Автор grinding_codexp, история, 4 месяца назад, По-английски

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
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится +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.