P16055 [CSPro 31] Coordinate Transformations (Part 2)

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: 。

For a point $(x, y)$ on the Cartesian coordinate plane, Xiao P defines the following two operations: 1. Scale by a factor of $k$: the $x$-coordinate becomes $kx$, and the $y$-coordinate becomes $ky$. 2. Rotate by $\theta$: rotate the point $(x, y)$ **counterclockwise** around the origin $(0, 0)$ by $\theta$ radians ($0 \le \theta < 2\pi$). It is easy to see that after rotation, the new $x$-coordinate is $x \cos \theta - y \sin \theta$, and the new $y$-coordinate is $x \sin \theta + y \cos \theta$. After fixing an operation sequence $(t_1, t_2, \cdots, t_n)$ containing $n$ operations, Xiao P defines the following queries: - `i j x y`: the new coordinates of $(x, y)$ after applying operations $t_i, \cdots, t_j$ ($1 \le i \le j \le n$). Given the operation sequence, compute the results of $m$ queries.

Read input from standard input. The input consists of $n + m + 1$ lines. The first line contains two positive integers $n$ and $m$ separated by spaces, representing the number of operations and the number of queries. The next $n$ lines describe the $n$ operations in order. Each line contains an integer (the operation type) and a real number ($k$ or $\theta$) separated by spaces, in the form `1 k` (scale by a factor of $k$) or `2 θ` (rotate by $\theta$). The next $m$ lines describe the $m$ queries in order. Each line contains four integers $i$, $j$, $x$, and $y$ separated by spaces, with meanings as described above.

Write output to standard output. Output $m$ lines. Each line contains two real numbers separated by spaces, representing the answer to the corresponding query.

### Sample Explanation The 5th query only applies operation 8 to the input coordinates: scale by a factor of $0.716$. $x$-coordinate: $159430 \times 0.716 = 114151.88$. $y$-coordinate: $-511187 \times 0.716 = -366009.892$. Because the exact computation method may differ, the program output may have a small difference from the true value. The sample output keeps only three decimal places. ### Subtasks - $80\%$ of the testdata satisfies: $n, m \le 1000$. - All testdata satisfies: - $n, m \le 10^5$. - All input coordinates are integers with absolute value not exceeding $10^6$. - For each single scaling operation, the factor $k \in [0.5, 2]$. - For any operation interval $t_i, \cdots, t_j$ ($1 \le i \le j \le n$), the product of scaling factors $k$ is within $[0.001, 1000]$. ### Scoring If the absolute error between your floating-point output and the reference answer is at most $0.1$, you get full score for that test point; otherwise you get $0$. ### Notes - C/C++: It is recommended to use `double` to store floating-point numbers, and use `scanf("%lf", &x);` for input and `printf("%f", x);` for output. You may also use `cin` and `cout`. After `#include `, you can use the trig functions `cos()` and `sin()`. - Python: You can directly use `print(x)` to output a floating-point number `x`. After `from math import cos, sin`, you can use the corresponding trig functions. - Java: It is recommended to use `double` to store floating-point numbers. You can use `System.out.print(x);` for output. You can call trig functions with `Math.cos()` and `Math.sin()`. Translated by ChatGPT 5