Problem A
Avoiding the Abyss
Languages
en
is
You are standing on a point with integer coordinates $(x_s, y_s)$. You want to walk to the point with integer coordinates $(x_t, y_t)$. To do this, you can walk along a sequence of line segments. But there is a swimming pool in your way. The swimming pool is an axis aligned rectangle whose lower left corner is on the point $(x_l, y_l)$ and the upper right corner is on the point $(x_r, y_r)$. You cannot ever cross the swimming pool, not even on the border. However, it is dark and you do not know the coordinates $(x_l, y_l)$ and $(x_r, y_r)$. Instead, you threw a rock into the pool which revealed that the point $(x_p, y_p)$ is in the pool (or on the boundary).
Find a way to walk from the start to the end point along a sequence of line segments, so that you never cross the swimming pool.
Input
The first line contains two integers $x_s$ and $y_s$ ($-10^4 \leq x_s, y_s \leq 10^4$).
The second line contains two integers $x_t$ and $y_t$ ($-10^4 \leq x_t, y_t \leq 10^4$).
The third line contains two integers $x_p$ and $y_p$ ($-10^4 \leq x_p, y_p \leq 10^4$).
The problem is not adaptive, i.e. for every test case there exist four integers $x_l, y_l, x_r, y_r$ ($-10^4 \leq x_l < x_r \leq 10^4$, $-10^4 \leq y_l < y_r \leq 10^4$) that constitute a swimming pool. The start and end points are always strictly outside the swimming pool, and the point $(x_p,y_p)$ is inside (or on the border). The start and end points are always distinct. Note that the problem is technically interactive, so the input will not contain an EOF character.
Output
First, print one integer $N$ ($0 \leq N \leq 10$), the number of points in between the start and end point that you want to visit. Then, print $N$ lines, the $i$th containing two integers $x_i, y_i$. These coordinates must satisfy $-10^9 \leq x_i, y_i \leq 10^9$. Note that these are not the same bounds than on the other coordinates.
This means that you will walk along straight line segments between $(x_s, y_s), (x_1, y_1), \dots , (x_N, y_N), (x_t, y_t)$ such that none of the line segments touch the swimming pool. It can be proven that a solution always exists.
Sample Input 1 | Sample Output 1 |
---|---|
0 0 4 4 2 2 |
2 0 3 1 4 |