Competitive Skating

By 3025, the Midnight Code Cup has been running for a millennium, and problem-setters are slowly running out of ideas for crazy challenges. So now you are about to race on an actual two-dimensional ice field!

The task is straightforward enough: you need to skate through $N$ gates placed on a field in a fixed order. The faster, the better.

Your ice skating skills are a bit rusty, so you can only skate in straight lines and circles. Changing direction is also a struggle, with the ice being so slippery. Fortunately, your problem solving skills are sharp as ever, allowing you to effortlessly formalize the challenge before you.

Here's what you got:

• Each gate is represented as a segment.

• Your trajectory starts at the point $(0, 0)$.

• It should be a union of at most $M$ parts. Each part can be of two types: a segment of a line or an arc of a circle.

• The start point of each new trajectory part is the end point of the previous one, or $(0, 0)$ if it is the first part.

• If a part is a segment, it can be represented by the coordinates of its end point. The coordinates should not exceed $10^4$ by an absolute value.

• If a part is an arc of a circle, it can be represented by the coordinates of its end point $e$, the coordinates of a circle center $c$, and the direction. The coordinates of the end point should not exceed $10^4$ by absolute value. The radius should not be smaller than $10^{-2}$ and should not exceed $10^4$ by absolute value. The direction is specified by $0$ or $1$, where $1$ means clockwise and $0$ means counter-clockwise.

• Each part of the trajectory should be provided with the desired speed at the end. Due to the physics of the ice field, the speed has to satisfy certain limitations:

  • The initial speed is $0$.

  • The speed at the start of a part is equal to the speed at the end of the previous part.

  • The acceleration on a part should be constant and should not exceed $\mathtt{max\_acc}$ by absolute value. In other words, if $v_s$ and $v_e$ are the speed at the start and the end of a part, and $l$ is its length, then $\left|\dfrac{v_e^2 - v_s^2}{2 \cdot l} \right| \le \mathtt{max\_acc}$.

  • Also, your speed cannot be too large on an arc with a small radius. Suppose that a trajectory part is an arc with radius $r$, start speed $v_s$, and end speed $v_e$. Then, $\max(v_s, v_e)$ should not exceed $\sqrt{r \cdot \mathtt{friction}}$ where $\mathtt{friction}$ is a global parameter of the ice field.

  • And average speed cannot be too small as well, i.e. $\dfrac{v_s + v_e}{2}$ should be more than $10^{-6}$ for each trajectory part.

  • Finally, if the tangents of two consecutive trajectory parts at the joint point do not match, the end speed on the eariler part should be $0$.

Now that everything is clear: ready, set, skate!

Input Data

You are given a zip-archive with $10$ tests: 01, 02, $\ldots$, 10.

Download inputs (problem-с-inputs.zip)

The first line of each test contains:

• $N$, the number of gates;

• $M$, the maximum number of trajectory parts;

• $\mathtt{friction}$, the friction;

• $\mathtt{max\_acc}$, the maximal acceleration.

Each of the next $n$ lines contains the description of a corresponding gate represented as a segment: the coordinates of the first end and the coordinates of the second end.

The gates should be passed in the order of appearance in the input.

Here is a short description of these tests:

Output Data

You should submit files 01.out, 02.out, $\ldots$, 10.out with answers to corresponding inputs. Some of the files may be missing.

Each of these files should have the following format:

• The first line should contain $m$: the number of trajectory parts.

• Each of the next $m$ lines should describe the corresponding part.

• If the part is a segment, the line should start with $0$ followed by the end speed and the coordinates of the end point: 0 speed x y.

• If the part is an arc, the line should start with $1$ followed by coordinates of the end point, coordinates of the center, and whether an arc is clockwise ($1$) or counter-clockwise ($0$): 1 speed xe ye xc yc is_clockwise.

All the real values should be provided with maximal precision possible. The checker uses 64-bit floating point types.

Instead of explaining how the validation checks are performed we provide the code of the checker. The main file is check.py.

Checker should be run as

python3 check.py test_file solution_file solution_file

Scoring

The total number of points for each test is calculated as the sum of time spent on each trajectory part. The time to pass a trajectory part of length $l$ with start speed $v_s$ and end speed $v_e$ is calculated as $\dfrac{2 \cdot l}{v_s + v_e}$, that is, the length divided by the average speed. It is also worth to mention, that each test can be easily passed within time $10^9$, so your total skating time will be calculated as $\min\left(\sum{\dfrac{2 \cdot l}{v_s + v_e}}, 10^9\right)$.

Your final score for each test is calculated as follows:

• If the output is incorrect (see the provided checker for details), the score is $0$.
• Otherwise, the score will be proportional to the square of the lowest amount of points among all participants for this test divided by the number of points for your output: $360 \cdot \left(\frac{\texttt{best\_points}}{\texttt{your\_points}}\right)^{1.5}$.

Note that the scoreboard will show your best score for each test among all your submissions.