Atena

Plato and Aristotle, good friends, had gotten lost in Athens. One could say they have a platonic friendship. However, they had moved so far apart that they could not hear each other directly even when shouting. Thus, they needed an intermediary: Pythagoras. When the two friends stand still, Pythagoras can calculate using his knowledge the area of the zone where he must be located to hear them both and transmits the information to them via Morse code in IEEE 754 format. Plato, being old, could not move as quickly as his disciple Aristotle, so he chose to remain stationary.

In this problem you are in Aristotle's situation. The committee has a hidden circle $\mathscr{C}_1$ with center $(X, Y)$ (representing Plato's position) and radius $R$ (at which the philosopher's voice can be heard). The contestant must find the numbers $(X, Y, R)$ using as few questions as possible of the type: Let $\mathscr{C}_2$ be a circle with center $(x', y')$ and radius $r'$ (representing Aristotle's position and his lung capacity). What is the area of intersection of circles $\mathscr{C}_1$ and $\mathscr{C}_2$?

We consider that $x', y', r'$ are all three numbers chosen by the contestant with the following constraints:

• $-10^7 \leq x' \leq 10^7$
• $-10^7 \leq y' \leq 10^7$
• $0 < r' \leq 10^7$

By the area of intersection of two circles we mean the area of the common portion of the disks determined by these circles.

Task

Write a program that guesses using as few questions as possible and as accurately as possible the coordinates of the circle. The score will be awarded based on the number of questions and the precision with which the answer is given.

$\textbf{Note: Contestants will be provided with several helper geometric functions to simplify the implementation.}$

Interaction Protocol

The contestant must implement exclusively the function

std::vector<double> solve();

The function will return a vector $v = (v_1, v_2, v_3)$ of $3$ elements with the property that $X = v_1, Y = v_2, R = v_3$. The contestant does not need to implement the main function.

To ask questions, the contestant can call the function:

double query(double x, double y, double r);

The function will return the area of intersection between the circle with center $(x, y)$ and radius $r$ and the hidden circle $\mathscr{C}_1$ from the committee.

Attached Files

Participants have access to the following files:

• atena.h -- the header that defines the interaction functions (solve and query) necessary for implementation.
• atena.cpp -- a simple implementation example that executes one query and answers with the circle $(1, 2, 3)$ each time.
• lgrader.cpp -- a testing grader for participants that can help them verify their code. A different grader will be used for scoring submissions.
• geometry.h -- a file with multiple geometry functions to ease contestants' implementation.

Using lgrader in Code::Blocks

To use lgrader.cpp in Code::Blocks:

• Create a new project.
• Add a file named solutie.cpp (select File > New > Empty File), where you will write the solution code.
• Add an empty file named atena.h and copy the contents from the attached atena.h file
• Copy the contents from lgrader.cpp into main.cpp to simulate running the solution.

After this setup, write in solutie.cpp the implementation of the solve function. To test the configuration, you can initially copy the code from atena.cpp into solutie.cpp. Then, press F9 or select Build and Run to compile and run the program. When running, the program will read the values $X$, $Y$ and $R$, and will simulate the interaction between lgrader and the contestant's solution, displaying the answers to queries made through query and validating the final answer provided through solve.

Constraints

• Let $\mathscr{C}_1$ be the hidden circle from the committee with center $(X, Y)$ and radius $R$.
• $-10^6 \leq X \leq 10^6$
• $-10^6 \leq Y \leq 10^6$

Scoring

Let $D = (x - X)^2 + (y - Y)^2 + (r - R)^2$ be the error margin of the answer and $Q$ the number of questions asked by the contestant.

Let $C_D$ and $C_Q$ be two scoring coefficients defined as follows:

Then your score for a test will be $100 \cdot C_D \cdot C_Q \%$ of the maximum for the test.

It is guaranteed that for tests worth $20$ points the center of the hidden circle is on the \texttt{Ox} axis.

Example Interaction

The hidden circle is $\mathscr{C}_1(X=17.00000, Y=2.62331, R=6.7890)$. This case cannot be manifested in the test data as $R$ does not meet the lower bound of $10^4$.

An example interaction is as follows:

query(1, 1.5, 2.5)

The area of intersection between the hidden circle $\mathscr{C}_1$ and the circle $(1, 1.5, 2.5)$ is $0$.

query(15, 14, 7)

The area of intersection between circle $\mathscr{C}_1$ and circle $(15, 14, 7)$ is $11.429000978$.

return {17.000001, 2.62331, 6.7891};

It is observed that, although the returned values do not exactly match the real ones, the solution is considered correct because the error margin is less than $10^{-5}$.