CF1578I.Interactive Rays

This is an interactive problem.

Your goal is to find a circle on a plane by shooting rays and getting the distance to the circle as a result.

Interactor has three hidden integer parameters that are determined in advance for each test, but which you don't know — $x_c$, $y_c$, and $r_c$. $(x_c, y_c)$ are coordinates of the circle's center and $r_c$ is its radius. The absolute values of $x_c$, $y_c$, and $r_c$ do not exceed $10^5$, and $1 \leq r_c \leq \sqrt{x_c^2 + y_c^2} - 1$.

You can shoot rays that extend from the origin $(0,0)$ and go via a point $(x_q,y_q)$ with the integer coordinates you specify. For each ray, you get a distance from the ray to the circle or $0$ if the ray intersects the circle.

Interaction

The interaction starts with your program printing a query to the standard output and finishes when your program finds and prints the answer to the problem.

Each query has a form of "? $x_q$ $y_q$", where $x_q$ and $y_q$ are integers ($|x_q|, |y_q| \le 10^6$; $x_q \ne 0$ or $y_q \ne 0$).

The interactor outputs a line with a single floating-point number — the distance between a query ray and a circle that is precise to $10^{-10}$ by an absolute value.

Your program can make the next query, read the output, and so on. You are allowed to do at most $60$ queries. At the end of the interaction, print the answer line "! $x_c$ $y_c$ $r_c$", flush the output and exit.

Note, that the output of the interactor is actually rounded to the 10-th digit after a decimal point, so if you are stress-testing your solution locally, make sure that you also perform the corresponding rounding.

这是一个交互式问题。

你的目标是通过发射射线并根据返回的到圆的距离信息，在平面上确定一个圆。

交互器具有三个预先确定但对您隐藏的整数参数：$x_c$、$y_c$ 和 $r_c$。其中 $(x_c, y_c)$ 是该圆的圆心坐标，$r_c$ 是其半径。$x_c$、$y_c$ 和 $r_c$ 的绝对值均不超过 $10^5$，且满足 $1 \leq r_c \leq \sqrt{x_c^2 + y_c^2} - 1$。

您可以从原点 $(0,0)$ 发射一条射线，该射线经过您指定的具有整数坐标的点 $(x_q, y_q)$。对于每条射线，您将获得该射线到圆的距离；若射线与圆相交，则返回 $0$。

交互流程

交互始于您的程序向标准输出打印一条查询，并在您的程序找到答案并输出结果时结束。

每条查询格式为 “? $x_q$ $y_q$”，其中 $x_q$ 和 $y_q$ 为整数，满足 $|x_q|, |y_q| \le 10^6$，且 $x_q \ne 0$ 或 $y_q \ne 0$。

交互器将输出一行，包含一个浮点数——即查询射线与圆之间的距离，该数值的绝对误差不超过 $10^{-10}$。

您的程序可继续发出下一条查询、读取输出，依此类推。您最多允许进行 $60$ 次查询。交互结束时，请输出答案行 “! $x_c$ $y_c$ $r_c$”，刷新输出并退出程序。

注意：交互器实际输出的数值会四舍五入至小数点后第 $10$ 位。因此，若您在本地对解法进行压力测试，请确保也执行相应的四舍五入操作。

Illustration of the queries from the example interaction.

示例交互中各查询的示意图。