Please read the new rule regarding the restriction on the use of AI tools. ×

A geometry problem

Revision en1, by grinding_codexp, 2024-08-11 12:28:36

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!

Tags geometry, computational geometry, rotation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English grinding_codexp 2024-08-11 12:28:36 779 Initial revision (published)