TopCoder

Caido
主唱太拼命了

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

16.7% (2/12)

Tags

Description

「你到底有沒有想過你以後要做什麼?你有目標嗎?你有夢想嗎?????????」「趕快醒醒好不好?別把自己的人生玩掉了。手機手機手機,你的人生到底還剩下什麼?」

嘉嘉和阿偉曾經是最好的朋友,他們一起練習程式,一起吃拉麵,一起過著資工的生活。因為一次的爭執,兩人反目成仇,並誓言從此之後走自己的路。為了讓他們找回消失的友誼,小翊決定邀請他們一起玩桌遊—「第三次領地危機」。

遊戲盤由 $N \times M$ 的二維表格組成,每行由上到下以 $1$ 到 $N$ 的正整數編號,每列由左到右以 $1$ 到 $M$ 的正整數編號,第 $x$ 行第 $y$ 列的格子以 $(x, y)$ 表示。在遊戲開始時嘉嘉位於 $(x_A, y_A)$,阿偉位於 $(x_C, y_C)$;而他們的目標為規劃一條路徑到各自的終點,其中嘉嘉的終點為 $(x_B, y_B)$,阿偉的終點為 $(x_D, y_D)$。

設 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$ 為某位玩家規劃的路徑,則其必須符合以下條件:

  • $(x_1, y_1)$ 為該玩家的起始點。
  • $(x_k, y_k)$ 為該玩家的終點。
  • 對於 $1 \le i < k$,$(x_{i+1}, y_{i+1}) \in \{(x_i + 1, y_i), (x_i - 1, y_i), (x_i, y_i + 1), (x_i, y_i - 1)\}$。

為了貫徹當初的誓言,他們打算「走自己的路」,兩人的路徑上不會有任何相同的格子。也就是說,設嘉嘉的路徑為 $P_1, P_2, \ldots$,阿偉的路徑為 $Q_1, Q_2, \ldots$,對於任意 $i, j$ 皆符合 $P_i \ne Q_j$。嘉嘉和阿偉發現,小翊可以指定一些起始點與終點破壞他們的計畫,讓他們沒辦法遵守誓言。聰明的你請寫一支程式,幫嘉嘉和阿偉判斷是否存在路徑使得他們能繼續「走自己的路」。

Input Format

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

每筆測資一行,包含十個正整數 $N$, $M$, $x_A$, $y_A$, $x_B$, $y_B$, $x_C$, $y_C$, $x_D$, $y_D$,分別表示地圖長寬與 $A$, $B$, $C$, $D$ 的位置。

  • $1 \le T \le 10^ 5$
  • $1 \le N, M \le 10^ 5$
  • $1 \le x_A, x_B, x_C, x_D \le N$
  • $1 \le y_A, y_B, y_C, y_D \le M$
  • $(x_A, y_A)$, $(x_B, y_B)$, $(x_C, y_C)$, $(x_D, y_D)$ 皆相異

Output Format

對於每筆測資輸出一行,若嘉嘉和阿偉能「走自己的路」,請輸出 Yes;否則,輸出 No

Sample Input 1

2
5 5 1 4 2 1 3 5 4 2
5 5 1 1 5 5 1 5 5 1

Sample Output 1

Yes
No

Hints

範例測資中,第一筆測資兩人可規劃的其中一種路徑如下圖:

第二筆測資中,兩人無法規劃出沒有相同格子的兩條路徑。

Problem Source

IOICamp 2022 Day5 pN

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~49 無額外限制 100

Testdata and Limits

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