All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given n points p1, p2, ..., pn in a plane and n integers a1, a2, ..., an.
For any index i (1 ≤ i ≤ n), it is possible to perform the following operation (let's call it i-rotation) on an arbitrary point P: Rotate P by ai degrees counter-clockwise around the point pi.
Note that ai will always be a multiple of 90. Also note that such an operation changes the point P.
You should process q queries. Each query is of one of the following types:
- 1 x y l r: Initially, you are given P = (x, y). Perform each i-rotation for i = l, l+1, ..., r (in this order) on the point P. Compute the coordinates of P modulo 109 + 7 after performing all i-rotations.
- 2 u x y b: Change the point pu to (x, y) and the angle au to b.
- The first line of the input contains a single integer n.
- Then, n lines follow. The i-th of these lines contains three space-separated integers xi, yi and ai. The i-th point is initially pi = (xi, yi).
- The next line contains a single integer q denoting the number of queries.
- Each of the following q lines contains a query in the format described above.
For each query of type 1, print a single line containing two space-separated integers denoting the coordinates of the point P after performing all rotations, modulo 109 + 7.
- 1 ≤ n ≤ 105
- 0 ≤ xi, yi, x, y ≤ 109
- 0 ≤ ai, b < 360
- 1 ≤ q ≤ 2 · 105
- 1 ≤ l ≤ r ≤ n
- 1 ≤ u ≤ n
Input: 3 0 0 90 1 2 180 3 2 270 3 1 5 5 1 3 2 2 2 2 90 1 5 5 1 3 Output: 0 1000000005 1000000003 6
|Tags||chemthan, chemthan, cook89, likecs, matrix-mul, medium, sqrt-decomp|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.