TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

71.4% (5/7)

Tags

Description


鹿是草食動物,通常以草和樹葉為食

虎視虎子在社團辦公室種了很多的觀賞用植物,不過從日野動物園逃出來的角田先生經常會偷偷跑來偷吃鹿仙貝順便咬這些植物的葉子。

虎視虎子打算重新安排這些植物的位置,她準備了一片大小為 $N$ 的六邊形田地,並打算將這些花花草草搬過去。六邊形田地以六邊形區域鑲嵌而成,單一一個六邊形區域構成一個大小為 $1$ 的田地,而大小為 $N$ 的田地則由大小為 $N-1$ 的田地在外圍多圍一圈六邊形區域而成。舉例來說,以下由左而右分別是大小為 $2$、$3$ 和 $4$ 的田地。

虎視虎子將每株植物移入如下的 V 字形盆栽中,每個盆栽佔據 $3$ 個六邊形區域:

虎視虎子一共有 $N^ 2-N$ 株植物,她打算將這 $N^ 2-N$ 個盆栽放入田地中,並留下恰好 $1$ 個六邊形區域。她打算利用這個區域作為誘餌,趁角田先生走進這個區域時在周圍擺滿裝水的寶特瓶試圖困住她。盆栽可以被旋轉,不一定要以如上圖的角度擺在田地中,但盆栽之間不能重疊,必須排列整齊,也就是說,每個盆栽必須完整地覆蓋住 $3$ 個六邊形區域。留空的六邊形區域以及田地範圍外皆不能有盆栽。

舉例來說,以下是一個在大小為 $4$ 的田地上擺放 $12$ 個盆栽的方式。白色的格子為留下的空格,而不同的盆栽則以不同顏色作出區隔:

為了方便定位每個區域的位置,虎視虎子使用了以下的座標系統:正中心的區域座標為 $(0,0)$,並以向右的方向為 $x$ 軸,向右上方 $60^ \circ$ 的方向為 $y$ 軸,每個六邊形為 $1$ 單位距離。大小為 $4$ 的田地中,每個區域的座標可以參考下圖:

虎視虎子已經決定好了要留下的空格的位置,她想請你寫一支程式幫她找出一種方式將 $N^ 2-N$ 個盆栽放入田地中。

Input Format

輸入的第一行為一整數 $T$,表示測試資料的數量。

每一筆測試資料僅一行,包含三個整數 $N,X,Y$,表示田地的大小,以及要留空的位置為 $(X,Y)$。

  • $1 \le T \le 50$
  • $2 \le N \le 50$
  • $-N < X, Y < N$
  • $-N < X+Y < N$

Output Format

對於每一筆測試資料,如果不存在擺放的方法,請輸出一行 No;否則,請先輸出一行 Yes,接下來 $N^ 2-N$ 行,每行包含六個整數 $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}, x_{i,3}, y_{i,3}$,表示第 $i$ 個盆栽佔據了 $(x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), (x_{i,3}, y_{i,3})$ 這三個區域。

如果有多種可能的輸出,你可以輸出任意一種。

  • 盆栽必須為 V 字形
  • 每個不是留空的區域必須恰好被一個盆栽佔據

Sample Input 1

3
2 0 -1
3 -1 1
4 2 0

Sample Output 1

Yes
-1 0 0 0 1 -1
-1 1 0 1 1 0
No
Yes
1 2 0 3 -1 3
-3 2 -3 3 -2 3
1 0 1 1 0 2
0 0 0 1 -1 2
-1 0 -1 1 -2 2
-3 0 -3 1 -2 1
3 -1 3 0 2 1
-1 -2 -2 -1 -2 0
3 -3 3 -2 2 -1
2 -3 2 -2 1 -1
1 -3 1 -2 0 -1
0 -3 0 -2 -1 -1

Hints

你可以使用以下的工具幫助解題以及畫出範例測資的擺放方式。我們建議使用電腦瀏覽器開啟以下工具。

Problem Source

改編自 NPSC 2022 國中組決賽 pF - 拼拼圖

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~4 $N \leq 5$ 5
3 5~6 $X = Y = 0$ 5
4 7~8 $X > 0, Y = 0, X = N - 1$ 10
5 9~10 $X > 0, Y = 0, X = N - 2$ 11
6 7~20 $X > 0, Y = 0$ 12
7 7~8, 21~30 $X > 0, Y \geq 0, X + Y = N - 1$ 18
8 9~10, 31~40 $X > 0, Y \geq 0, X + Y = N - 2$ 19
9 0~60 無額外限制 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 9
1 1000 262144 65536 2 9
2 1000 262144 65536 2 9
3 1000 262144 65536 2 9
4 1000 262144 65536 2 9
5 1000 262144 65536 3 9
6 1000 262144 65536 3 9
7 1000 262144 65536 4 6 7 9
8 1000 262144 65536 4 6 7 9
9 1000 262144 65536 5 6 8 9
10 1000 262144 65536 5 6 8 9
11 1000 262144 65536 6 9
12 1000 262144 65536 6 9
13 1000 262144 65536 6 9
14 1000 262144 65536 6 9
15 1000 262144 65536 6 9
16 1000 262144 65536 6 9
17 1000 262144 65536 6 9
18 1000 262144 65536 6 9
19 1000 262144 65536 6 9
20 1000 262144 65536 6 9
21 1000 262144 65536 7 9
22 1000 262144 65536 7 9
23 1000 262144 65536 7 9
24 1000 262144 65536 7 9
25 1000 262144 65536 7 9
26 1000 262144 65536 7 9
27 1000 262144 65536 7 9
28 1000 262144 65536 7 9
29 1000 262144 65536 7 9
30 1000 262144 65536 7 9
31 1000 262144 65536 8 9
32 1000 262144 65536 8 9
33 1000 262144 65536 8 9
34 1000 262144 65536 8 9
35 1000 262144 65536 8 9
36 1000 262144 65536 8 9
37 1000 262144 65536 8 9
38 1000 262144 65536 8 9
39 1000 262144 65536 8 9
40 1000 262144 65536 8 9
41 1000 262144 65536 9
42 1000 262144 65536 9
43 1000 262144 65536 9
44 1000 262144 65536 9
45 1000 262144 65536 9
46 1000 262144 65536 9
47 1000 262144 65536 9
48 1000 262144 65536 9
49 1000 262144 65536 9
50 1000 262144 65536 9
51 1000 262144 65536 9
52 1000 262144 65536 9
53 1000 262144 65536 9
54 1000 262144 65536 9
55 1000 262144 65536 9
56 1000 262144 65536 9
57 1000 262144 65536 9
58 1000 262144 65536 9
59 1000 262144 65536 9
60 1000 262144 65536 9