TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

完整題本 PDF:中文英文馬來文

「火花奇遇記:自動化冒險」是一款開放世界工藝生存類型的遊戲。在遊戲中,你可以收集各種資源,發揮創造力設計並建造自動化工坊,享受自動化帶來的樂趣。

小奕在遊玩遊戲時發現,為了讓工坊能達成自動化,他需要某種資源 $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|})\}$ 需滿足:

  • $1 \leq x_i \leq N, 1 \leq y_i \leq M, 1 \leq i \leq |R|$
  • $\forall 1 \leq i, j \leq |R|, i \neq j, (x_i, y_i) \neq (x_j, y_j)$
  • $(x_i, y_i)$ 與 $(x_{i + 1}, y_{i + 1})$ 相鄰,$1 \leq i < |R|$
  • $(x_{|R|}, y_{|R|})$ 與 $(x_1, y_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})\} \subseteq 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})$。保證給定的表格大小及位置必定能找到至少一組滿足要求的環形軌道,如果有多種滿足要求的環狀路線,輸出任意一種即可。

Input Format

輸入第一行包含一行兩個正整數 $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})$。並且,保證這四行代表的座標皆不相同。

  • $2 \leq N, M \leq 5$
  • $1 \leq x_{a_1}, x_{a_2}, x_{b_1}, x_{b_2}\leq N$
  • $1 \leq y_{a_1}, y_{a_2}, y_{b_1}, y_{b_2}\leq M$

Output Format

輸出第一行為一個正整數 $|R|$ 代表環狀軌道 $R$ 的長度。

接下來輸出 $|R|$ 行,第 $i$ 行為兩個正整數 $x_i, y_i$,代表環狀軌道 $R$ 中的 $(x_i, y_i)$。

Sample Input 1

3 3
1 1
1 3
2 3
3 1

Sample Output 1

8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

Sample Input 2

5 5
2 2
4 4
2 4
4 2

Sample Output 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

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 1000 2097152 65536
14 1000 2097152 65536
15 1000 2097152 65536
16 1000 2097152 65536
17 1000 2097152 65536
18 1000 2097152 65536
19 1000 2097152 65536
20 1000 2097152 65536
21 1000 2097152 65536
22 1000 2097152 65536
23 1000 2097152 65536
24 1000 2097152 65536
25 1000 2097152 65536
26 1000 2097152 65536
27 1000 2097152 65536
28 1000 2097152 65536
29 1000 2097152 65536
30 1000 2097152 65536
31 1000 2097152 65536
32 1000 2097152 65536
33 1000 2097152 65536
34 1000 2097152 65536