問題一覧 > 通常問題

No.3336 Coincidence

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 3
作問者 : 👑 kencho / テスター : cn_449 👑 みうね
お気に入りにしたユーザー ProblemId : 12739 / 自分の提出
問題文最終更新日: 2025-11-08 01:59:23
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 487 (順位表) の他の問題:

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)$
Here, $a_x, b_x, c_x, d_x$ are all distinct, and $a_y, b_y, c_y, d_y$ are also all distinct.

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$.
If it exists, find one example; if it does not exist, report so.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。