問題一覧 > 通常問題

No.1932 動く点 P / Moving Point P

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 33
作問者 : 👑 nullnull / テスター : RhoRho
0 ProblemId : 3994 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-06 23:04:05

問題文

座標平面上の $(x_j, y_j)$ に点 ${\rm P}_j$ があります。($1 \le j \le Q$)
null くんは $i(1 \le i \le N)$ 番目の操作では、点を $(p_i, q_i)$ を中心に $r_i^\circ$ 反時計回りに回転させます。(角度は度数法で与えられることに注意してください。)
この操作を $s_j$ 番目の操作から $t_j$ 番目の操作まで のみ 順番に 点 ${\rm P}_j$ に行ったときの最終的な ${\rm P}_j$ の座標を各 $j$ について求めてください。

制約

  • $1 \le N, Q \le 10^5$
  • $-1000 \le p_i, q_i, x_j, y_j \le 1000$
  • $-360 \le r_i \le 360$
  • $1 \le s_j \le t_j \le N$ (22:07 修正)
  • $N, Q, s_j, t_j$ は整数である。
  • $p_i, q_i, r_i, x_j, y_j$ は小数点以下 $6$ 桁まで与えられる。

入力

$N$
$p_1\ q_1\ r_1$
$p_2\ q_2\ r_2$
$\dots$
$p_N\ q_N\ r_N$
$Q$
$s_1\ t_1\ x_1\ y_1$
$s_2\ t_2\ x_2\ y_2$
$\dots$
$s_Q\ t_Q\ x_Q\ y_Q$

出力

$j$ 行目に $s_j$ 番目の操作から $t_j$ 番目の操作まで のみ 順番に 点 ${\rm P}_j$ に行ったときの最終的な ${\rm P}_j$ の座標を空白区切りに一行に出力してください。

想定解との絶対誤差または相対誤差の小さい方が $10^{-3}$ であるとき、正答となります。(23:04 修正)

サンプル

サンプル1
入力
5
0.000000 0.000000 90.000000
1.000000 1.000000 180.000000
133.000000 333.000000 0.000000
367.092893 80.084048 -75.124327
842.043304 429.624441 0.066603
5
1 1 0.000000 0.000000
2 2 0.000000 0.000000
1 2 0.000000 0.000000
1 4 123.000000 456.900000
2 4 0.127890 0.123490
出力
0.000000 0.000000
2.000000 2.000000
2.000000 2.000000
196.317090 -60.268951
197.746090 412.986886

$1$ 番目の出力について、$(0,0)$ を $(0,0)$ を中心に $90^\circ$ 回した座標は $(0,0)$ です。
$2$ 番目の出力について、$(0,0)$ を $(1,1)$ を中心に $180^\circ$ 回した座標は $(2,2)$ です。
$3$ 番目の出力について、上記二つの操作を順番に行った座標は $(2,2)$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。