[Solution] Interactive Rays solution codeforces | ICPC WF Moscow Invitational Contest

Interactive Rays solution codeforces

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 — xcxcycyc, and rcrc(xc,yc)(xc,yc) are coordinates of the circle’s center and rcrc is its radius. The absolute values of xcxcycyc, and rcrc do not exceed 105105, and 1rcx2c+y2c−−−−−−√11≤rc≤xc2+yc2−1.

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

Interactive Rays solution codeforces

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 “xqxq yqyq“, where xqxq and yqyq are integers (|xq|,|yq|106|xq|,|yq|≤106xq0xq≠0 or yq0yq≠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 101010−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 6060 queries. At the end of the interaction, print the answer line “xcxc ycyc rcrc“, 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.

Interactive Rays solution codeforces

Example
input

Copy
? 0 -10

? 10 -10

? 10 0

? 10 10

? 10 20

? 10 30

! 20 10 10

Interactive Rays solution codeforces

output

Copy
12.360679775

11.2132034356

0.0

0.0

3.416407865

5.8113883008
Note

Illustration of the queries from the example interaction.

 

Interactive Rays solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment