E. Range Rotate Query - 水以下コンテスト

E - Range Rotate Query

Ceylon

1024

100

点

二次元平面上に $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$
入力は全て整数

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

入力は以下の形式で標準入力から与えられる。ここで、 $\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}$ 以下だった場合、正解と判定される。

入力例 1

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

出力例 1

例えば、 $1$ 番目のクエリについて、

これら $3$ つの頂点からなる三角形の面積は $7$ です。

入力例 2

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

出力例 2

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$ 番目のクエリについて、

これら $3$ つの頂点からなる三角形の面積は $0$ です。（退化している三角形の面積が $0$ であることに注意してください。）