Teleporter Takahashi

题目描述

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)$。Takahashi 从他当前位置关于点 $(x,y)$ 对称地瞬移到该对称点。

判断他是否可以在重复上述操作 0 次到 $10^6$ 次（含）之后到达点 $(t _ x,t _ y)$。 如果可能，构造一列操作使他到达点 $(t _ x,t _ y)$。

输入格式

输入从标准输入给出，格式如下： $s _ x$ $s _ y$ $t _ x$ $t _ y$ $a$ $b$ $c$ $d$

输出格式

第一行若 Takahashi 能在重复操作 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)$ 应包含以空格分隔的点 $(x, y)\in R$ 的坐标，按此顺序，表示在第 $i$ 次操作中选择的点。

1 2
7 8
7 9 0 3

Yes
7 0
9 3
7 1
8 1

Yes
7 3
9 0
7 2
9 1
8 1

0 0
8 4
5 5 0 0

No

1 4
1 4
100 200 300 400

Yes

22 2
16 7
14 30 11 14

No

提示

$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$ 输入中的所有值均为整数。例如，以下选择可以使他从 $(1,2)$ 到达 $(7,8)$。

选择 $(7,0)$。Takahashi 移动到 $(13,-2)$。 选择 $(9,3)$。Takahashi 移动到 $(5,8)$。 选择 $(7,1)$。Takahashi 移动到 $(9,-6)$。 选择 $(8,1)$。Takahashi 移动到 $(7,8)$。

任何满足条件的输出都是被接受的；例如，打印

也是被接受的。
没有操作序列可以使他到达点 $(8,4)$。
Takahashi 可能一开始就已经在目标位置。

标签: AtCoder|abc289F

来源

AtCoder|abc289F