Background

Garuda Team, I've got some good news.

The chemical agent used as a catalyst for their WMD is being transported to our shores from the Estovakian mainland.

This catalyst has already been carried into the outskirts of Gracemeria.

As a measure of caution against any attempts to destroy it, it has been concealed at Fort Norton in Gracemeria's north.

If we start advancing again, the enemy will most likely bring the catalyst into Gracemeria at a faster pace.

If in fact weapons of mass destruction are used on the population of Gracemeria, the resulting devastation can't be expressed in enough words.

It will lead to unspeakable tragedies.

We've used this intelligence to come up with a solid proposal on how to prevent this scorched earth policy from being executed in our capital.

Just a minute ago, we received a letter of approval for our prevention plan from the Joint Chiefs of Staff.

The proposal we put on the table for our scorched earth prevention policy is really quite simple.

While the enemy transport unit is stationed at Fort Norton, we'll ambush them.

We like to call it our tactic for pre-emptive victory.

The enemy has loaded this catalyst into their transport vehicles and is able to send them into Gracemeria at any time.

This plan will be carried out by a handful of our top pilots under absolute secrecy.

Fly through Fort Norton's canyon at an extremely low altitude to avoid radar detection, and take out those transport vehicles.

We've determined that a high-risk mission of this magnitude could not be executed by anyone other than Garuda Team.

We're counting on a flawless execution here.

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 12} \\\Large\text{Weapons of Mass Destruction}\\\tiny -\textit{ Boiling Point }-$$

Problem Description

To destroy the enemy convoy carrying the WMD catalyst, you need to pass through Fort Norton's canyon at extremely low altitude to approach them.

Fort Norton is abstracted as two piecewise linear functions on the plane with respect to $y$ ($y\in[0,10^7]$), $A(y):y\mapsto x$ and $B(y):y\mapsto x$. For any real number $y\in[0,10^7]$, it is guaranteed that $A(y)\le B(y)$.

You and your F-15E are abstracted as a particle. The initial position is $(X_1,0)$, and it is guaranteed that $A(0)\le X_1\le B(0)$. At the same time, you have an initial velocity $(v_0,\theta_0)$, representing the speed magnitude and direction.

To avoid being detected by the enemy, you cannot run the engine at high power. Your thrust is just enough to keep a constant speed while flying level.

Of course, you can turn. Since you are the protagonist of Ace Combat, all your turns are done using PSM. Specifically, your flight path should be a polyline consisting of several line segments. However, you will suffer drag during turns. If the absolute difference between the direction angle after the change and before the change is $\alpha$, then the speed magnitude decreases by $\alpha$. If you do not change direction, then you will keep moving in a uniform straight line.

Since Ghost Eye is in a hurry to finish the mission, your $y$ coordinate must increase over time.

Also, you must ensure that at any time, your position $(x,y)$ satisfies $A(y)\le x\le B(y)$.

The overload of PSM turns is huge, so you must ensure that the number of turns does not exceed $\bf 3\times 10^6$. Otherwise you will g-LOC like Prez and smash your head into the dashboard.

Find any turning plan such that you move to $(X_2,10^7)$ (that is, the speed must not become $\bf 0$ or negative during the motion), and the number of turns does not exceed $3\times 10^6$. Similarly, it is guaranteed that $A(10^7)\le X_2\le B(10^7)$.

Input Format

The first line contains four integers $n,m,X_1,X_2$ and two real numbers $v_0,\theta_0$.

It is guaranteed that the existence of a solution is unchanged within the range $v_0\pm 10^{-6}$.

The next $n$ lines each contain two integers $x,y$. It is guaranteed that $y$ is increasing, the first $y$ is $0$, and the last $y$ is $10^7$. Connecting these points in order with line segments gives the function $A$.

The next $m$ lines each contain two integers $p,q$, describing the function $B$ in the same way as $A$.

Output Format

First output a line containing 1.

Then, since the particle's trajectory must be a polyline, you need to output the number of vertices $K$ on the next line, and then output $K$ lines, each containing two real numbers representing the coordinates of a vertex. Suppose the sequence of points you output is $C:\{(s_1,t_1),(s_2,t_2),\cdots,(s_K,t_K)\}$. Then for all $i\in[1,K)$, connect $C_i$ and $C_{i+1}$ with a line segment; the resulting polyline is the trajectory you provide.

You must ensure:

• $C_1$ coincides with $X_1$, and $C_K$ coincides with $X_2$.
• The $y$ coordinates in $C$ are monotone.
• For any $1\le i<K$, $t_i<t_{i+1}$.
• For any point $(x,y)$ on the polyline, $A(y)-10^{-6}\le x\le B(y)+10^{-6}$.
• The speed is greater than $0$ throughout the motion.
• $K\le 3\times 10^6$.

If you correctly output a plan that satisfies all the requirements above, you will be judged as Accepted; otherwise, Wrong Answer. If there are multiple valid plans, you may output any one of them.

This problem uses a Special Judge.

5 4 4000000 9000000 13 0
3000000 0
1000000 1000000
2000000 4000000
6000000 8000000
7000000 10000000
5000000 0
4000000 2000000
6000000 6000000
10000000 10000000

1
4
4000000.0000000000 0.0000000000
3000000.0000000000 2000000.0000000000
4000000.0000000000 6000000.0000000000
9000000.0000000000 10000000.0000000000

Hint

Sample explanation (scaled down by $10^6$):

Note that the particle may touch the boundary during the motion, and it may also move along the boundary for a while.

---

Constraints:

For $100\%$ of the testdata, it is guaranteed that $2\le n,m\le 10^6$, $0\le x,y,p,q\le 10^7$, $x_1\le X_1\le p_1$, $x_n\le X_2\le p_m$, $0\le \theta_0<\pi$, and $0\le v_0\le 10^9$.

For $100\%$ of the testdata, the real-number precision does not exceed $12$ digits.

For $100\%$ of the testdata, a solution is guaranteed to exist.

• Subtask 1 (3 pts): $n,m\le 6$; $v_0\ge 50$.
• Subtask 2 (8 pts): $n,m\le 6$.
• Subtask 3 (17 pts): $n,m\le 200$.
• Subtask 4 (13 pts): $n,m\le 1500$.
• Subtask 5 (17 pts): $n,m\le 5000$.
• Subtask 6 (19 pts): $n,m\le 10^5$.
• Subtask 7 (23 pts): no additional constraints.

Please pay attention to floating-point output efficiency.

---

idea: Sol1, solution: Sol1 & w33z8kqrqk8zzzx33, code: Sol1, data: w33z8kqrqk8zzzx33

Translated by ChatGPT 5