No.471 直列回転機

レベル : / 実行時間制限 : 1ケース 3.141秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 36
作問者 : koyumeishikoyumeishi / テスター : tubo28tubo28

1 ProblemId : 709 / 出題時の順位表

問題文

平面上の点を 点$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$ のケースに対してこの手法は使えないので、工夫したり超能力を使ったりして解いてください。

提出ページヘ