問題一覧 > 通常問題

No.1226 I hate Robot Arms

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 66
作問者 : tyawanmusityawanmusi / テスター : tko919tko919
6 ProblemId : 5075 / 出題時の順位表
問題文最終更新日: 2020-09-12 14:48:54

お知らせ

テストケースに誤差がありましたので、腕の長さの最大値を $10^9$ から $10$ に変更しました。

テストケース変更に伴いリジャッジをかけたところ、何名かの提出結果がWAからACになりました。申し訳ございません。

元ネタ

Robot Arms
面白い問題です。

問題文

すぬけ君の工場には、次の特徴を持つ ロボットアームEX があります。

  • ロボットアームEXは、$N$ 個の と $N+1$ 個の 関節 からなる。腕には $1,2,\dots,N$ で、関節には $0,1,\dots,N$ で番号が付けられている。腕 $i$ は関節 $i-1$ と関節 $i$ をつなぐ。
  • 各腕には、それぞれ独立に 角度長さ を指定することができる。
  • 工場を座標平面とみなすと、関節 $i$ の座標 $(x_i,y_i)$ は次のように定まる。
    • $(x_0,y_0) = (0,0)$
    • 腕 $i$ の長さを $d_i$ 、腕 $i$ の角度を $\theta_{i}$ とする。
    • $\phi_{i} = \theta_{1} + \theta_{2} + \dots + \theta_{i}$ として、$(x_{i},y_{i})=(x_{i-1}+d_i\cos \phi_{i},y_{i-1}+d_i\sin \phi_{i})$
  • 各腕の角度と長さを次のように変更できる。
    • 腕 $i$ の角度を $X$ 度に変更する。
    • 腕 $i$ の長さを $X$ に変更する。

あなたはすぬけ君の工場のエンジニアです。$Q$ 回、次のような入力形式でクエリが与えられるので処理してください。

  • クエリ $0$ :0 i x:腕 $i$ の角度を $x$ 度に変更する。
  • クエリ $1$ :1 i x:腕 $i$ の長さを $x$ に変更する。
  • クエリ $2$ :2 i :関節 $i$ の $x$ 座標、$y$ 座標を空白区切りで $1$ 行に出力する。

また、最初は全ての腕の角度が $0$ 度、長さが $1$ で初期化されています。

PyPyでのACは確認しておりますが、PythonでのACは確認しておりません。

制約

  • 入力はすべて整数
  • $1 \le N \le 10^5$
  • $1 \le Q \le 10^5$
  • クエリ $0,1,2$ について、$1 \le i \le N$
  • クエリ $0$ について、$0 \le x < 360$
  • クエリ $1$ について、$1 \le x \le 10$
  • 少なくとも $1$ 回以上クエリ $2$ が与えられる。

入力

$N\ Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

$1$ 行目には $N,Q$ が空白区切りで与えられます。
$1 + i$ 行目には $i$ 番目のクエリが空白区切りで与えられます。詳しくは問題文を参照してください。

出力

クエリ $2$ の数を $q$ として、$q$ 行出力してください。
$i$ 行目には $i$ 番目のクエリ $2$ の結果を出力してください。
最後に改行してください。

想定解答との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解として扱われます。

サンプル

サンプル1
入力
3 8
0 1 90
0 2 270
0 3 315
1 2 2
1 3 2
2 1
2 2
2 3
出力
0.000000 1.000000
2.000000 1.000000
3.414213 -0.414213

$5$ つのクエリにより、ロボットアームEXは次のような形になります。

関節 $1,2,3$ の座標はそれぞれ $(0,1),(2,1),(2+\sqrt 2,1-\sqrt 2)$ となります。

サンプル2
入力
1024 6
0 537 53
2 538
0 435 88
1 684 9
0 623 221
2 705
出力
537.203630046 1.597271020
461.669761237 159.235272186

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