No.2831 Cos Bomb Crasher
タグ : / 解いたユーザー数 8
作問者 :
twitteryou
/ テスター :
👑 
p-adic
Problem Statement
In a certain town, there is a watermelon field with an area of $2N \times 2N$. The field is square-shaped and positioned so that the segment connecting the coordinates $(-N,-N)$ and $(N,N)$ is its diagonal. At each lattice point inside the field (including the boundary), there is $1$ watermelon.
A star warrior visiting this town loves watermelons. When he tried to inhale and eat the watermelons, he noticed something strange: the watermelon that should have been at coordinates $(0,0)$ was missing, and in its place was a bomb shaped like a watermelon.
He therefore went into the town to look for witnesses to the swapping of the watermelons, and obtained the following testimony:
・The Great King swapped $3$ of the watermelons in the field with bombs. Moreover, only $3$ bombs were swapped in. From here on, the coordinates of the bombs are denoted by $O,A,B$, where $O$ is the coordinates of the bomb at the origin.
・Triangle $OAB$ is a right triangle in which $\angle AOB$ is a right angle.
Also, when he mentioned that he wanted to find the watermelon bombs other than the one at $(0,0)$, he was given a probe during his inquiries. When some coordinates $X$ are specified, this tool works as follows:
・It outputs the sign of $\cos \angle AXB$ and the value of $\cos^2 \angle AXB$.
Being a star warrior, he can use his copy ability. Specifically, he inhales a bomb-shaped monster with a skull pattern, chooses coordinates $(x,y)$ and a radius $r$, and annihilates everything inside the circle (including the boundary) of radius $r$ centered at coordinates $(x,y)$.
He has several requests for removing the bombs:
・Since bombs are dangerous, he wants to annihilate all of the bombs at $O,A,B$.
・His copy ability has limits and can only be used $1$ time, and since he wants to leave as many watermelons as possible, he wants to make $r$ as small as possible.
Using the probe at most $300$ times, find the coordinates and radius that satisfy all of the above requests and tell him. However, output the radius as its value raised to the power of $2$. Under these constraints, there is exactly $1$ pair of coordinates and radius satisfying all of the requests.
Input
$N$
・$3 \leq N \leq 10^8$
・$N$ is an integer
The hidden coordinates $A(x_A,y_A)$ and $B(x_B,y_B)$ satisfy the following:
・$A,B$ are fixed before the interaction between the programs
・$-N \leq x_A,x_B,y_A,y_B \leq N$
・$A,B$ are lattice points
・$O,A,B$ do not lie on a single line
・Triangle $OAB$ is a right triangle with $\angle AOB =\frac{\pi}{2}$
Output
For a query that uses the probe at coordinates $Z(x_Z,y_Z)$, output as follows. If the number of queries exceeds $300$, your answer is judged incorrect.
$1 \ x_Z \ y_Z$Here, the following constraints must be satisfied. If they are not satisfied, the judge's behavior is undefined.
・$-10^9 \leq x_Z,y_Z \leq 10^9$
・Both $x_Z,y_Z$ have at most $9$ digits after the decimal point
The judge then gives the answer to the query as follows:
$P \ u \ v$If $X,A,B$ are all distinct, $P$ is one of
-, +, 0, meaning that the sign of $\cos \angle AXB$ is negative, positive, $0$, respectively. $u,v$ are integers such that $\cos^2 \angle AXB=\frac{u}{v}$. The representation is limited to the irreducible fraction with $v$ positive. Otherwise, $P$ is ? and $u,v=0$.
However, if $v>10^{18}$, the returned $u,v$ are a rational approximation such that $1\leq v \leq 10^{18}$.
To output the coordinates $ANS(x_{ANS},y_{ANS})$ and the radius raised to the power of $2$, $r^2$, that satisfy the conditions, output as follows. After this output, terminate your program.
$2 \ x_{ANS} \ y_{ANS} \ r^2$
Here, the following constraints must be satisfied. If they are not satisfied, the judge's behavior is undefined.
・$-10^9 \leq x_{ANS},y_{ANS} \leq 10^9$
・$0 \leq r^2 \leq 10^{19}$
・$x_{ANS},y_{ANS},r^2$ have at most $9$ digits after the decimal point
Your answer is correct if the inside (including the boundary) of the circle with center $(x_{ANS},y_{ANS})$ and radius $r$ contains the $3$ bombs and $r$ cannot be made any smaller.
Your answer is judged correct if its relative error or absolute error is at most $10^{-5}$ compared with the reference solution, which is prepared so that its error from the true value is at most $10^{-10}$.
Sample
Sample 1
Output
1 0 0 1 5.5 1.5 1 -2 3 1 3 2 2 0 0 13
Judge's Output
3 0 0 1 + 1 1 ? 0 0 ? 0 0
First, $N$ is given. Also, $A(-2,3)$, $B(3,2)$ have been secretly determined.
In the $1$st query, $\angle AOB =\frac{\pi}{2}$, so $\cos \angle AOB=0$.
In the $2$nd query, $\angle AXB = 0$, so $\cos \angle AXB=1$.
In the $3,4$th queries, no angle is formed, so the judge outputs as shown above.
As the answer, center $(0,0)$ and radius $\sqrt{13}$ are output. The inside of the circle contains the $3$ bombs, but the radius can be made smaller while still containing the $3$ bombs, so this is judged incorrect.
Note that outputting a value with leading zeros such as -00.7, or a value that is not a valid decimal such as 18.90.3 or +1c.5, is judged incorrect.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。