/ 
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 の座標をこの順に空白区切りで出力せよ。
入力例 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
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