Fort Norton Canyon Infiltration

You are tasked with infiltrating Fort Norton to destroy an enemy convoy loaded with WMD catalysts. Fort Norton is abstracted as two piecewise linear functions on the plane:

\(A(y): y \mapsto x\) and \(B(y): y \mapsto x\) defined for all \(y \in [0,10^7]\) and satisfying \(A(y) \le B(y)\). At time \(t=0\) you start at \((X_1,0)\) with an initial speed of \(v_0\) and direction \(\theta_0\) (in radians). You must always remain within the corridor defined by \[ A(y) \le x \le B(y) \quad \text{for all } y \in [0,10^7]. \]

Your flight path is a polyline consisting of a sequence of straight segments. When you change direction, if the absolute difference between the new angle and the old angle is \(\alpha\), your speed decreases by \(\alpha\) (i.e. the new speed is the old speed minus \(\alpha\)). You may fly in a straight line (keeping constant speed) if you do not change direction. Additionally, your \(y\) coordinate must increase strictly over time, and your speed must always remain positive (i.e. it can never drop to 0 or below).

Your goal is to design a turning scheme with at most \(3 \times 10^6\) turns so that you end exactly at \((X_2,10^7)\) – note that \(A(10^7) \le X_2 \le B(10^7)\). You may output any valid turning scheme that meets these requirements. In the output, the flight path is defined by the starting point \((X_1,0)\), followed by the list of turning points (in the order they occur), and ending at \((X_2,10^7)\).

inputFormat

The input is given as follows:

1. A line with two floating-point numbers: v0 and theta0 (in radians), representing the initial speed and the initial direction, respectively.
2. A line with two floating-point numbers: X1 and X2, where \(X1\) is the initial \(x\)-coordinate (at \(y=0\)) and \(X2\) is the \(x\)-coordinate of the destination (at \(y=10^7\)). It is guaranteed that \(A(0) \le X1 \le B(0)\) and \(A(10^7) \le X2 \le B(10^7)\).
3. A line with two integers: m_A and m_B, the number of vertices describing the functions \(A(y)\) and \(B(y)\), respectively. (Each function is defined by a sequence of vertices and is linear between consecutive vertices.)
4. The next m_A lines each contain two numbers: y A(y), representing a vertex of \(A(y)\). The first vertex will have \(y=0\) and the last vertex will have \(y=10^7\).
5. The next m_B lines each contain two numbers: y B(y), representing a vertex of \(B(y)\). The first vertex will have \(y=0\) and the last vertex will have \(y=10^7\).

You may assume that the functions are valid (i.e. for every \(y \in [0,10^7]\), \(A(y) \le B(y)\)).

outputFormat

Output your turning scheme as follows:

1. First, output an integer \(k\) indicating the number of turns (\(0 \le k \le 3 \times 10^6\)).
2. If \(k > 0\), then output \(k\) lines. Each line should contain two floating-point numbers representing the coordinates \(x\) and \(y\) of the turning point (in the order they occur).

The complete flight path is then constructed as follows: the starting point \((X1,0)\), followed by the \(k\) turning points, and finally the destination \((X2,10^7)\).

sample

10 0
5000000 5000000
2 2
0 0
10000000 0
0 10000000
10000000 10000000

1
5000000 0