P5600 [XR-4] Straightedge and Compass Construction

This is an output-only (human intelligence) problem.

You are given several known geometric objects, and you need to construct a required point using straightedge and compass. You must find this point within a limited number of steps. You can perform the following operations: 1. Draw a circle with one known point as the center and another known point as a point on the circle. 2. Connect two known points to form a straight line. You need to output your construction steps.

The first line contains an integer, which is the test point ID. The second line contains an integer $n$, which is the number of known points. The next $n$ lines each contain two real numbers $x_i, y_i$, which are the coordinates of the $i$-th point. Next is an integer $n_1$, which is the number of known line segments. The next $n_1$ lines each contain two integers $u, v$, meaning there is a line segment connecting point $u$ and point $v$. Next is an integer $n_2$, which is the number of known lines. The next $n_2$ lines each contain two integers $u, v$, meaning there is a line passing through point $u$ and point $v$. Next is an integer $n_3$, which is the number of known circles. The next $n_3$ lines each contain two integers $u, v$, meaning there is a circle centered at point $u$, with point $v$ on the circle. Next are two real numbers $x, y$, which are the coordinates of the required point. Next are $10$ integers $a_1$ to $a_{10}$, which are the scoring parameters for this test point. See the statement for details.

The first line contains an integer $m$, which is the number of steps you need. The next $m$ lines describe your construction steps: First an integer $1$ or $2$. $1$ means you draw a circle, and $2$ means you draw a straight line. Then four real numbers $x_1, y_1, x_2, y_2$: If you draw a circle, it means you draw a circle centered at $(x_1, y_1)$ and with $(x_2, y_2)$ as a point on the circle. If you draw a line, it means you connect $(x_1, y_1)$ and $(x_2, y_2)$.

For each test point, if your number of steps is less than or equal to the first $i$ scoring parameters, then you will get $i$ points. Notes: 1. **All $x, y$ must be points you have already obtained.** “Already obtained” means points from the input, or intersection points of known geometric objects. (That is, you cannot choose an arbitrary point to construct with, and you cannot obtain the required point by choosing some suitable point.) More precisely, each time you output a coordinate, the Special Judge will choose, among all points you have currently obtained, the point whose Euclidean distance to your input coordinate is the smallest, as the point you selected this time. If this smallest distance is greater than $10^{-5}$, then this operation will be judged invalid, and for this test point you will get $0$ points. 2. You cannot draw a circle from its center and radius. You can only draw a circle from its center and a point on the circle. 3. **Your constructed answer is considered correct if the absolute error or relative error to the required point is at most $10^{-5}$** (because the author does not know how to write a Special Judge with no error). More precisely, suppose the point you obtained is $(x_1, y_1)$ and the required point is $(x_2, y_2)$. Then your output is considered correct if and only if $\dfrac{|x_1-x_2|}{\max(|x_2|, 1)} \le 10^{-5}$ and $\dfrac{|y_1-y_2|}{\max(|y_2|, 1)} \le 10^{-5}$. 4. The provided files `data1.in` to `data10.in` are the $10$ input datasets. Among them, test points $1, 2, 3, 7, 8$ come with diagrams. 5. The provided checker can compute your score. Usage is as follows (where `data.in` is the input file and `data.out` is your output file.): - Windows-32/64: ``` checker data.in data.out data.out ``` - Linux/MacOS： ``` ./checker data.in data.out data.out ``` 6. The problem setter cannot get $100$ points. update: You can click [here](/paste/capu9k2n) to view the checker source code. If you have ideas for improvements, feel free to suggest them. Translated by ChatGPT 5