「火花奇遇記:自動化冒險」是一款開放世界工藝生存類型的遊戲。在遊戲中,你可以收集各種資源,發揮創造力設計並建造自動化工坊,享受自動化帶來的樂趣。
小奕在遊玩遊戲時發現,為了讓工坊能達成自動化,他需要某種資源 $A$ 源源不絕的出現在位置 $Y$,然而,資源 $A$ 只會在非常遙遠的位置 $X$ 無限產生。為了解決這個問題,小奕決定鋪設環形鐵路,來讓火車可以將資源 $A$ 從位置 $X$ 運輸至位置 $Y$,再返回到位置 $X$ 重複運輸。
不過,新的問題隨之出現了,小奕很快發現到,除了資源 $A$ 以外,他還需要一種只會在位置 $X'$ 無限產生的資源 $B$,源源不絕的出現在位置 $Y'$。由於物資有限,小奕只足夠設置一台火車和一組環形軌道,火車一次只能夠裝載一種資源,請問你可以幫忙設計環形軌道來讓兩種資源都能夠被完成運輸嗎?
正式地說,在一個 $N \times M$ 的表格上,資源 $A$ 要從 $(x_{a_1}, y_{a_1})$ 運輸到 $(x_{a_2}, y_{a_2})$,資源 $B$ 要從 $(x_{b_1}, y_{b_1})$ 運輸到 $(x_{b_2}, y_{b_2})$,一組滿足要求的環形軌道 $R = \{(x_1, y_1), (x_2, y_2), ..., (x_{|R|}, y_{|R|})\}$ 需滿足:
注意到,這裡的相鄰指的是四方位相鄰,及 $(x_i, y_i)$ 和 $(x_j, y_j)$ 相鄰若且唯若 $|x_i - x_j| + |y_i - y_j| = 1$。
並且若是從 $(x_{a_1}, y_{a_1})$ 開始沿著環形軌道行進,必定接著依序經過 $(x_{a_2}, y_{a_2}), (x_{b_1}, y_{b_1}), (x_{b_2}, y_{b_2})$。保證給定的表格大小及位置必定能找到至少一組滿足要求的環形軌道,如果有多種滿足要求的環狀路線,輸出任意一種即可。
輸入第一行包含一行兩個正整數 $N$ 和 $M$ 代表表格的大小。
接下來有四行輸入,每一行有兩個正整數,分別代表 $(x_{a_1}, y_{a_1}), (x_{a_2}, y_{a_2}), (x_{b_1}, y_{b_1}), (x_{b_2}, y_{b_2})$。並且,保證這四行代表的座標皆不相同。
輸出第一行為一個正整數 $|R|$ 代表環狀軌道 $R$ 的長度。
接下來輸出 $|R|$ 行,第 $i$ 行為兩個正整數 $x_i, y_i$,代表環狀軌道 $R$ 中的 $(x_i, y_i)$。
3 3 1 1 1 3 2 3 3 1
8 1 1 1 2 1 3 2 3 3 3 3 2 3 1 2 1
5 5 2 2 4 4 2 4 4 2
20 2 2 1 2 1 1 2 1 3 1 4 1 5 1 5 2 5 3 5 4 4 4 3 4 2 4 1 4 1 3 2 3 3 3 4 3 4 2 3 2
| No. | Testdata Range | Score |
|---|