| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 40 | 3 | 2 | 5.263% |
Since Koreyko having vanished treacherously with the sacred suitcase, Ostap is facing a nearly hopeless problem --- locate Koreyko with at least some approximation.
It is known that the search area is a triangle on a plane with integers coordinates. To find the coordinates of the vertices, Ostap sends a weird telegram ($a$, $b$, $c$) to the Financial Committee and gets a similarly strange reply ($p$, $q$). In reality, the three numbers from Ostap's telegram are coefficients of the line equation $a \cdot x + b \cdot y = c$, and the reply is the proportion of area in which this line cuts the triangle into pieces.
It is known that all vertex coordinates are integers no greater than $1\,000$ in absolute value. Moreover, the triangle is non-degenerate, and all angles are greater than $5$ degrees.
This is an interactive problem, and instead of file input-output you'll have to work with a special program --- the interactor. Interacting with the program is performed via the standard input-output streams.
Your program will be sending queries and the interactor will be replaying to them. For each query that contains coefficients of the line equation you will receive a reply with the proportion in which the given line cuts the triangle.
Once the answer is printed, the participant's solution must terminate.
Find the vertex coordinates in no more than $1\,000$ queries. If you cannot print the coordinates or print them incorrectly, you will receive the \textsf{Wrong Answer} verdict.
Financial Committee answer format: "$p$ $q$", where the real numbers $p$ and $q$ define the proportion in which the given line cuts the triangle ($0 \le p,q \le 1$, $p+q=1$). The number $p$ equals to the part of the triangle area, for which the inequality $a \cdot x + b \cdot y \le c$ holds. The real numbers $p$ and $q$ are printed with $15$ digits after the decimal point.
Ostap's query format: "? $a$ $b$ $c$", where $a$, $b$, $c$ are coefficients of the equation of line. These numbers are real numbers with no more than $15$ digits after the decimal point ($|a|, |b| \le 2 \cdot 10^3$, $|c| \le 4 \cdot 10^6$, $\frac{1}{4 \cdot 10^6} \le a^2 + b^2 \le 4 \cdot 10^6$).
Problem answer format: "! $x_1$ $y_1$ $x_2$ $y_2$ $x_3$ $y_3$", where $x_i$, $y_i$ are integer coordinates of the required triangle vertices. The three triangle vertices can be written in any order.
Make sure that each query ends with a line break and that you flush the output stream buffer (the flush command of the language). Otherwise the solution may get the Deadlock verdict (process execution exceeded the real time limit).
? 0 1 0 ? 0 2 1 ? 0 1 0 ? 1 0 1 ? 0 3 1 ? 2 0 1 ? 2 0 3 ! 0 0 2 0 1 1
0.000000000000000 1.000000000000000 0.750000000000000 0.250000000000000 0.000000000000000 1.000000000000000 0.500000000000000 0.500000000000000 0.555555555555555 0.444444444444445 0.125000000000000 0.875000000000000 0.875000000000000 0.125000000000000