問題一覧 > 通常問題

No.471 Serial Rotators

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 3.141秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 53
作問者 : koyumeishi / テスター : tubo28
お気に入りにしたユーザー ProblemId : 709 / 自分の提出
問題文最終更新日: 2026-06-25 10:09:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

Problem Statement

A machine that rotates points on the plane counterclockwise by $R$ degrees ($R \in \{0,90,180,270\}$) around the point $P(px,py)$ is called a rotator.
There are $N$ rotators, and rotator $i$ rotates points on the plane counterclockwise by $R_i$ degrees ($R_i \in \{0,90,180,270\}$) around the point $Pi({p_i}_x, {p_i}_y)$.

Given the coordinates of $M$ points, output the coordinates of each point after using rotators $1$ through $N$ successively in order of their numbers.
(Rotate the point with rotator $1$ -> then rotate it with rotator $2$ -> $\dots$ -> then rotate it with rotator $N$)

That would be a common problem, so here is a twist.
The solver is not given the information about the rotators. Instead, up to $10$ times, you may execute a question query that returns the coordinates $(x^\prime, y^\prime)$ obtained after applying the $N$ rotators to a point $(x,y)$ ( $x$,$y$ are integers and $|x|,|y|\leq10^4$ ).

Input and Output

This is a reactive problem. Do not forget to flush the output.

$M$ points are given on standard input, so first read them. All input is given as integers.

$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$

After reading the input, execute question queries and the answer query.

Output each question query to standard output in the following format. A trailing newline is required.

? $x$ $y$

You can execute up to 10 question queries. Exceeding 10 results in a wrong answer.
$x,y$ must be integers with $|x|, |y| \leq 10^4$. (If these constraints are not satisfied, the judge program may not work correctly.)

The response to a question query is returned on standard input in the following format.

$x^\prime$ $y^\prime$

The coordinates $(x^\prime, y^\prime)$ obtained by rotating the point $(x,y)$ given in the question query with the $N$ rotators are returned. $x^\prime, y^\prime$ are integers, but depending on the input they may exceed $10^4$.

After making your question queries, output the answer query in the following format.

!
$x^\prime_1$ $y^\prime_1$
$\vdots$
$x^\prime_M$ $y^\prime_M$

On the first line output "!", and on the second and subsequent lines output, one per line and in order, the points obtained by rotating the $M$ points given at the beginning.
Your answer is accepted if it is judged correct for all the points. Do not output anything extra afterward.

Although it is not disclosed to the solver, the $N$ rotators are given to the judge in the following format.

$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\}$

Sample

Sample 1

This is the case where the rotators are as follows.

2
0 0 90
1 1 90

Points on the plane are rotated by 90 degrees around (0,0), and then rotated by 90 degrees around (1,1).
Example) (1,1) -> (-1,1) -> (1,-1)

Input

First, read the information about the M points.

3
0 0
1 0
1 1

You can make up to 10 question queries. The following is one example.

Query

? 0 0

Response

2 0

Query

? 1 0

Response

1 0

Query

? 1 1

Response

1 -1

Answer query

!
2 0
1 0
1 -1

This approach does not work for cases with $M > 10$, so solve the problem by devising something clever or by using your psychic powers.

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