E - Range Rotate Query
問題文
二次元平面上に $N$ 個の点があり、 $i$ 番目の点 $(1 \leq i \leq N)$ は始め座標 $(X_i, Y_i)$ にあります。
$Q$ 個のクエリが与えられるので、それぞれについて答えてください。
与えられるクエリは以下の $2$ 種類です。
1 l r θ: 原点からのユークリッド距離が $\sqrt{l}$ 以上 $\sqrt{r}$ 以下の全ての点を、原点中心に反時計回りに $\theta$ 度だけ回転移動させる。2 a b c: $a$ 番目の点と $b$ 番目の点と $c$ 番目の点を頂点とする、三角形の面積を出力する。
ここで、原点からのユークリッド距離は、原点 $(0, 0)$ と点 $(x, y)$ に対し、この $2$ 点間の距離が $\sqrt{x^2 + y^2}$ であるものとして定められています。
ただし、三角形が退化している ($3$ つの頂点が同一直線上にある) 場合、その面積は $0$ であるとします。
制約
- $3 \leq N \leq 10^5$
- $-10^5 \leq X_i, Y_i \leq 10^5$
- $i \ne j \Longrightarrow (X_i, Y_i) \ne (X_j, Y_j) \enspace (1 \leq i, j \leq N)$
- $1 \leq Q \leq 50000$
- $0 \leq l \leq r \leq 2 \times 10^{10}$
- $0 \leq \theta \lt 360$
- $1 \leq a < b < c \leq N$
- 入力は全て整数
部分点
以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。
- (20点) $N \leq 100, ~~ Q \leq 1000, ~~$
2 a b cのクエリのみ与えられる - (20点) $N \leq 100, ~~ Q \leq 1000$
- (60点) 追加の制約なし
入力
入力は以下の形式で標準入力から与えられる。ここで、 $\mathrm{query}_k$ は $k$ 番目のクエリである。
$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$
$Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$
各クエリは以下の形式で与えられる。
$1$ $l$ $r$ $\theta$
$2$ $a$ $b$ $c$
出力
問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。
ただし、ジャッジの出力との相対誤差または絶対誤差が $10^{-6}$ 以下だった場合、正解と判定される。
5
0 0
3 1
-5 3
10 -6
-14142 -1356
4
2 1 2 3
2 1 3 4
2 2 3 4
2 3 4 5
7.0
0.0
21.0
73809.0
例えば、 $1$ 番目のクエリについて、
- $1$ 番目の点の座標は $(0, 0)$ です。
- $2$ 番目の点の座標は $(3, 1)$ です。
- $3$ 番目の点の座標は $(-5, 3)$ です。
これら $3$ つの頂点からなる三角形の面積は $7$ です。
6
0 0
2 2
0 3
4 -5
31415 92653
-9982 -44353
8
2 1 2 3
1 0 8 45
2 1 2 3
2 2 3 4
1 9 41 165
2 2 3 4
1 1234 3141592653 270
2 4 5 6
3.0
0.0
0.3431457505076194
8.535898384862243
2211183117.39239
例えば、$2$ 番目のクエリについて、
- 原点からのユークリッド距離が $\sqrt{0} ~ (= 0)$ 以上 $\sqrt{8} ~ (= 2\sqrt{2})$ 以下の全ての点を反時計回りに $45$ 度回転移動させます。
$1$ 番目の点 と $2$ 番目の点が該当し、それぞれ $(0, 0) \to (0, 0)$、 $(2, 2) \to (0, 2\sqrt{2})$ と移動します。
また、 $3$ 番目のクエリについて、
- $1$ 番目の点の座標は $(0, 0)$ です。
- $2$ 番目の点の座標は $(0, 2\sqrt{2})$ です。
- $3$ 番目の点の座標は $(0, 3)$ です。
これら $3$ つの頂点からなる三角形の面積は $0$ です。（退化している三角形の面積が $0$ であることに注意してください。）