No.471 直列回転機
タグ : / 解いたユーザー数 52
作問者 : koyumeishi / テスター : tubo28
問題文
平面上の点を 点$P(px,py)$ を中心に反時計回りに $R$度 ($R \in \{0,90,180,270\}$) 回転させる機械を回転機と言います。
$N$機の回転機があり、 回転機$i$は平面上の点を 点$Pi({p_i}_x, {p_i}_y)$ を中心に反時計回りに $R_i$度 ($R_i \in \{0,90,180,270\}$) 回転させます。
$M$個の点の座標が与えられるので、回転機$1$から回転機$N$まで番号順に続けて使用した後の点の座標を出力してください。
(点を回転機$1$で回転 -> 更に回転機$2$で回転 -> $\dots$ -> 更に回転機$N$で回転)
というのはよくある問題なので、一捻りします。
回答者に回転機の情報は与えられません。
その代わり$10$回まで 点$(x,y)$ ( $x$,$y$ は整数 かつ $|x|,|y|\leq10^4$ ) に$N$機の回転機を使用した後の座標 $(x^\prime, y^\prime)$ を返す質問クエリを実行することができます。
入出力
この問題はリアクティブ問題です。 出力の flush を忘れないでください。
標準入力に$M$個の点が与えられるので、まずはこれを受け取ってください。 入力は全て整数で与えられます。
$M$ $x_1$ $y_1$ $\vdots$ $x_M$ $y_M$
$1 \leq M \leq 5 \times 10^4$
$|x_i|, |y_i| \leq 10^4$
入力を受け取ったら、質問クエリ、解答クエリを実行してください。
質問クエリは、次のフォーマットで標準出力へ出力してください。 末尾に改行が必要です。
? $x$ $y$
質問クエリは10回まで実行できます。 10回を超えると不正解となります。
$x,y$ は整数 かつ $|x|, |y| \leq 10^4$ である必要があります。
(制約を満たさない場合、ジャッジプログラムが正常に動作しない場合があります)
質問クエリに対する応答は、次のフォーマットで標準入力へ返されます。
$x^\prime$ $y^\prime$
質問クエリで与えられた 点$(x,y)$ を $N$ 機の回転機で回転した後の座標 $(x^\prime, y^\prime)$ が返されます。 $x^\prime, y^\prime$ は整数ですが、入力次第では $10^4$ を超える場合があります。
質問クエリを行った後、解答クエリを次のフォーマットで出力してください。
! $x^\prime_1$ $y^\prime_1$ $\vdots$ $x^\prime_M$ $y^\prime_M$
1行目には "!", 2行目以降には最初に与えられた$M$個の点を回転させた後の点を一行ずつ順に出力してください。
全ての点に関して正しいと判定されると正解となります。 後ろに余計な出力はしないでください。
また回答者には開示されませんが、 $N$機の回転機は以下の形式でジャッジに与えられています。
$N$ ${p_1}_x$ ${p_1}_y$ $R_1$ $\vdots$ ${p_N}_x$ ${p_N}_y$ $R_N$
$1 \leq N \leq 5 \times 10^4$
$|{p_i}_x|, |{p_i}_y| \leq 10^4$
$R_i \in \{0,90,180,270\}$
サンプル
サンプル1
回転機が次のような場合です。
2 0 0 90 1 1 90
平面上の点は (0,0) を中心に 90度回転させられた後、 (1,1) を中心に 90度回転させられます。
例) (1,1) -> (-1,1) -> (1,-1)
入力
初めに M 個の点についての情報を受け取ってください。
3 0 0 1 0 1 1
質問クエリを10回まで行うことが出来ます。 以下はその一例です。
質問
? 0 0
応答
2 0
質問
? 1 0
応答
1 0
質問
? 1 1
応答
1 -1
解答クエリ
! 2 0 1 0 1 -1
$M > 10$ のケースに対してこの手法は使えないので、工夫したり超能力を使ったりして解いてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。