F - Teleporter Takahashi

Contest Duration: 2023-02-11(Sat) 12:00 - 2023-02-11(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Teleporter Takahashi Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $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)$ に移動することができるような操作の列を $1$ つ構成してください。

制約

$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$

出力

$1$ 行目には、操作を $0$ 回以上 $10^6$ 回以下繰り返して高橋くんが点 $(t _ x,t _ y)$ に到達できるなら Yes 、そうでなければ No と出力せよ。 $1$ 行目で Yes と出力したとき、かつそのときに限り、あなたが構成した操作列の長さを $d$ としてさらに $d$ 行出力せよ（ $d$ は $0\leq d\leq10^6$ を満たさなければならない）。 $1+i$ 行目 $(1\leq i\leq d)$ には、 $i$ 回目の操作で選んだ点 $(x, y)\in R$ の座標をこの順に空白区切りで出力せよ。

入力例 1Copy

Copy

1 2
7 8
7 9 0 3

出力例 1Copy

Copy

例えば、次のようにして $(1,2)$ から $(7,8)$ へ移動することができます。

点 $(7,0)$ を選ぶ。高橋くんは $(13,-2)$ に移動する。
点 $(9,3)$ を選ぶ。高橋くんは $(5,8)$ に移動する。
点 $(7,1)$ を選ぶ。高橋くんは $(9,-6)$ に移動する。
点 $(8,1)$ を選ぶ。高橋くんは $(7,8)$ に移動する。

条件を満たす操作の列であれば何を出力しても正答となるので、例えば

と出力しても正答となります。

入力例 2Copy

Copy

0 0
8 4
5 5 0 0

出力例 2Copy

Copy

No

どのように操作しても点 $(8,4)$ に移動することはできません。

入力例 3Copy

Copy

1 4
1 4
100 200 300 400

出力例 3Copy

Copy

Yes

高橋くんがはじめから目的地にいる場合もあります。

入力例 4Copy

Copy

22 2
16 7
14 30 11 14

出力例 4Copy

Copy

No

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 1Copy

Copy

1 2
7 8
7 9 0 3

Sample Output 1Copy

Copy

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

is also accepted.

Sample Input 2Copy

Copy

0 0
8 4
5 5 0 0

Sample Output 2Copy

Copy

No

No sequence of operations leads him to point $(8,4)$ .

Sample Input 3Copy

Copy

1 4
1 4
100 200 300 400

Sample Output 3Copy

Copy

Yes

Takahashi may already be at the destination in the beginning.

Sample Input 4Copy

Copy

22 2
16 7
14 30 11 14

Sample Output 4Copy

Copy

No