102895: [Atcoder]ABC289 F - Teleporter Takahashi
Description
Score : $500$ points
Problem Statement
Takahashi is on an $xy$-plane. Initially, he is at point $(s _ x,s _ y)$, and he wants to reach point $(t _ x,t _ y)$.
On the $xy$-plane is a rectangle $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$. Consider the following operation:
- Choose a lattice point $(x,y)$ contained in the rectangle $R$. Takahashi teleports to the point symmetric to his current position with respect to point $(x,y)$.
Determine if he can reach point $(t _ x,t _ y)$ after repeating the operation above between $0$ and $10^6$ times, inclusive. If it is possible, construct a sequence of operations that leads him to point $(t _ x,t _ y)$.
Constraints
- $0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5$
- $0\leq a\leq b\leq2\times10^5$
- $0\leq c\leq d\leq2\times10^5$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$s _ x$ $s _ y$ $t _ x$ $t _ y$ $a$ $b$ $c$ $d$
Output
In the first line, print Yes if Takahashi can reach point $(t _ x,t _ y)$ after repeating the operation between $0$ and $10^6$ times, inclusive, and No otherwise.
If and only if you print Yes in the first line, print $d$ more lines, where $d$ is the length of the sequence of operations you have constructed ($d$ must satisfy $0\leq d\leq10^6$).
The $(1+i)$-th line $(1\leq i\leq d)$ should contain the space-separated coordinates of the point $(x, y)\in R$, in this order, that is chosen in the $i$-th operation.
Sample Input 1
1 2 7 8 7 9 0 3
Sample Output 1
Yes 7 0 9 3 7 1 8 1
For example, the following choices lead him from $(1,2)$ to $(7,8)$.
- Choose $(7,0)$. Takahashi moves to $(13,-2)$.
- Choose $(9,3)$. Takahashi moves to $(5,8)$.
- Choose $(7,1)$. Takahashi moves to $(9,-6)$.
- Choose $(8,1)$. Takahashi moves to $(7,8)$.
Any output that satisfies the conditions is accepted; for example, printing
Yes 7 3 9 0 7 2 9 1 8 1
is also accepted.
Sample Input 2
0 0 8 4 5 5 0 0
Sample Output 2
No
No sequence of operations leads him to point $(8,4)$.
Sample Input 3
1 4 1 4 100 200 300 400
Sample Output 3
Yes
Takahashi may already be at the destination in the beginning.
Sample Input 4
22 2 16 7 14 30 11 14
Sample Output 4
No
Input
题意翻译
在坐标系中有一个起始点 $(s_x,s_y)$ 和一个矩形 $\{(x,y)|a-0.5\le x\le b+0.5,c-0.5\le x\le d+0.5\}$，每次操作可以选中一个矩形内的整点并把当前点移到与该点对称的位置，问能否在 $10^6$ 次操作以内到达目标点 $(t_x,t_y)$ 如能请输出`Yes`并给出任意一个方案，如不能输出`No` 给出的所有横纵坐标都是 $\le 2\times10^5$ 的非负整数Output
得分：500分
问题描述
高桥在$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)$。如果可能，构造一个能将他带到点$(t _ x,t _ y)$的操作序列。
限制条件
- $0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5$
- $0\leq a\leq b\leq2\times10^5$
- $0\leq c\leq d\leq2\times10^5$
- 输入中的所有值都是整数。
输入
输入将从标准输入中按照以下格式给出：
$s _ x$ $s _ y$ $t _ x$ $t _ y$ $a$ $b$ $c$ $d$
输出
在第一行，如果高桥能在重复操作$0$到$10^6$次（含）后到达点$(t _ x,t _ y)$，则打印Yes，否则打印No。
只有当你在第一行打印了Yes，才打印$d$多行，其中$d$是你构造的操作序列的长度（$d$必须满足$0\leq d\leq10^6$）。
第$(1+i)$行（$1\leq i\leq d$）应该按照顺序包含在$R$内的点$(x, y)$的空格分隔的坐标。
样例输入1
1 2 7 8 7 9 0 3
样例输出1
Yes 7 0 9 3 7 1 8 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
0 0 8 4 5 5 0 0
样例输出2
No
没有任何操作序列能将他带到点$(8,4)$。
样例输入3
1 4 1 4 100 200 300 400
样例输出3
Yes
高桥可能一开始就位于目的地。
样例输入4
22 2 16 7 14 30 11 14
样例输出4
No