No.3336 Coincidence
Problem Statement
There is a town on the $xy$-plane.
Currently, there are only $4$ buildings in this town, and their names and coordinates are as follows.
- House $A$ : $(a_x,\ a_y)$
- House $B$ : $(b_x,\ b_y)$
- School $A$ : $(c_x,\ c_y)$
- School $B$ : $(d_x,\ d_y)$
The students Alice and Bob live in this town. Alice lives in House $A$ and attends School $A$. Bob lives in House $B$ and attends School $B$.
At time $0$, Alice and Bob each leave the house they live in and start moving toward the school they attend.
Each time the time advances by $1$, each of them can move exactly distance $1$ in a direction parallel to the $x$-axis or the $y$-axis, but cannot move if the destination point contains a building other than the house they live in or the school they attend.
Both of them also move according to the following rules.
- They move so as to reach their destination at the earliest possible time. If there are multiple routes satisfying this condition, they choose $1$ of them with equal probability.
- If they have already reached their destination, they do not move.
- If there is not even $1$ route to their destination, they stay where they are and do not move.
Now, you are the mayor of this town, and you want Alice and Bob to meet on their way to school no matter what, so you have decided to use your authority as mayor to achieve this goal.
Before the two of them depart, you can choose up to $4000$ lattice points within the region $|x|, |y| \leq 200$ where no building currently stands, and construct buildings there.
Is it possible, by constructing buildings cleverly, to make Alice and Bob always meet at a lattice point at some fixed time on their way to school?
In other words, does there exist a way of constructing buildings such that the following holds?
- There exists a non-negative integer $t$ such that at time $t$, Alice and Bob are at the same lattice point with probability $1$.
Constraints
- All input values are integers
- $1 \leq T \leq 100$
- $-100 \leq a_x, a_y, b_x, b_y, c_x, c_y, d_x, d_y \leq 100$
- $a_x, b_x, c_x, d_x$ are all distinct
- $a_y, b_y, c_y, d_y$ are all distinct
Input
The input is given from standard input in the following format. Here, $case_i$ denotes the $i$-th case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$a_x\ a_y\ b_x\ b_y\ c_x\ c_y\ d_x\ d_y$
Output
For each case, if no placement of buildings satisfying the condition exists, output -1; if one exists, output one example in the following format.
$K$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_K\ y_K$
$K$ is the number of new buildings to construct, and $x_i, y_i$ are the coordinates of the lattice point where the $i$-th building is constructed. $K$ must be a non-negative integer not exceeding $4000$.
Print a newline at the end of the output for each case.
Sample
Sample 1
Input
1 -2 0 0 -2 2 1 1 2
Output
1 1 1
If a new building is constructed at the point $(1,\ 1)$, Alice always moves along the route $(-2,\ 0) \rightarrow (-1,\ 0) \rightarrow (0,\ 0) \rightarrow (1,\ 0) \rightarrow (2,\ 0) \rightarrow (2,\ 1)$, and Bob always moves along the route $(0,\ -2) \rightarrow (0,\ -1) \rightarrow (0,\ 0) \rightarrow (0,\ 1) \rightarrow (0,\ 2) \rightarrow (1,\ 2)$.
Since the two of them always meet at time $2$, this is a correct answer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
cn_449