AT_abc289_f [ABC289F] Teleporter Takahashi

题目描述

在 $xy$ 平面上有高桥君。一开始，高桥君位于点 $(s_x, s_y)$。高桥君想要移动到点 $(t_x, t_y)$。

在 $xy$ 平面上有一个矩形 $R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,\,c-0.5\leq y\leq d+0.5\rbrace$。请考虑以下操作：

• 选择一个包含在矩形 $R$ 内的格点 $(x, y)$。以点 $(x, y)$ 为中心，高桥君会瞬间移动到关于该点对称的位置。

请判断是否可以通过上述操作 $0$ 次或最多 $10^6$ 次，使高桥君到达点 $(t_x, t_y)$。如果可以，请构造出一种可行的操作序列。

输入格式

输入以如下格式从标准输入读入：

$s_x\ s_y\ t_x\ t_y\ a\ b\ c\ d$

输出格式

第 $1$ 行，如果可以通过 $0$ 次或最多 $10^6$ 次操作使高桥君到达点 $(t_x, t_y)$，输出 Yes，否则输出 No。
如果第 $1$ 行输出了 Yes，则仅在此情况下，接下来输出你构造的操作序列的长度 $d$（满足 $0\leq d\leq 10^6$），并在接下来的 $d$ 行中，第 $1+i$ 行（$1\leq i\leq d$）输出第 $i$ 次操作选择的点 $(x, y)\in R$ 的坐标，坐标之间用空格隔开。

输入输出样例 #1

输入 #1

1 2
7 8
7 9 0 3

输出 #1

Yes
7 0
9 3
7 1
8 1

输入输出样例 #2

输入 #2

0 0
8 4
5 5 0 0

输出 #2

No

输入输出样例 #3

输入 #3

1 4
1 4
100 200 300 400

输出 #3

Yes

输入输出样例 #4

输入 #4

22 2
16 7
14 30 11 14

输出 #4

No

说明/提示

限制条件

• $0\leq s_x, s_y, t_x, t_y\leq 2\times10^5$
• $0\leq a\leq b\leq 2\times10^5$
• $0\leq c\leq d\leq 2\times10^5$
• 输入均为整数

样例解释 1

例如，可以通过如下方式从 $(1,2)$ 移动到 $(7,8)$：

• 选择点 $(7,0)$。高桥君移动到 $(13,-2)$。
• 选择点 $(9,3)$。高桥君移动到 $(5,8)$。
• 选择点 $(7,1)$。高桥君移动到 $(9,-6)$。
• 选择点 $(8,1)$。高桥君移动到 $(7,8)$。

只要满足条件，输出任意一组操作序列均可。例如，输出

Yes
7 3
9 0
7 2
9 1
8 1

也是正确答案。

样例解释 2

无论如何操作，都无法移动到点 $(8,4)$。

样例解释 3

高桥君一开始就已经在目标位置。

由 ChatGPT 4.1 翻译