atcoder#ABC289F. [ABC289F] Teleporter Takahashi

[ABC289F] Teleporter Takahashi

题目描述

xy xy 平面上に高橋くんがいます。 はじめ、高橋くんは点 (s  x,s  y) (s\ _\ x,s\ _\ y) にいます。 高橋くんは、点 (t  x,t  y) (t\ _\ x,t\ _\ y) に移動したいです。

xy 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 R に含まれる格子点 (x,y) (x,y) をひとつ選ぶ。 点 (x,y) (x,y) を中心に高橋くんはいまいる位置と対称な位置に瞬間移動する。

上の操作を 0 0 回以上 106 10^6 回以下繰り返して、高橋くんが点 (t  x,t  y) (t\ _\ x,t\ _\ y) にいるようにできるか判定してください。 できる場合、高橋くんが点 (t  x,t  y) (t\ _\ x,t\ _\ y) に移動することができるような操作の列を 1 1 つ構成してください。

输入格式

入力は以下の形式で標準入力から与えられる。

s  x s\ _\ x s  y s\ _\ y t  x t\ _\ x t  y t\ _\ y a a b b c c d d

输出格式

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

题目大意

在坐标系中有一个起始点 (sx,sy)(s_x,s_y) 和一个矩形 {(x,y)a0.5xb+0.5,c0.5xd+0.5}\{(x,y)|a-0.5\le x\le b+0.5,c-0.5\le x\le d+0.5\},每次操作可以选中一个矩形内的整点并把当前点移到与该点对称的位置,问能否在 10610^6 次操作以内到达目标点 (tx,ty)(t_x,t_y)
如能请输出Yes并给出任意一个方案,如不能输出No
给出的所有横纵坐标都是 2×105\le 2\times10^5 的非负整数

1 2
7 8
7 9 0 3
Yes
7 0
9 3
7 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 a b2×105 0\leq\ a\leq\ b\leq2\times10^5
  • 0 c d2×105 0\leq\ c\leq\ d\leq2\times10^5
  • 入力はすべて整数

Sample Explanation 1

例えば、次のようにして (1,2) (1,2) から (7,8) (7,8) へ移動することができます。 - 点 (7,0) (7,0) を選ぶ。高橋くんは (13,2) (13,-2) に移動する。 - 点 (9,3) (9,3) を選ぶ。高橋くんは (5,8) (5,8) に移動する。 - 点 (7,1) (7,1) を選ぶ。高橋くんは (9,6) (9,-6) に移動する。 - 点 (8,1) (8,1) を選ぶ。高橋くんは (7,8) (7,8) に移動する。 ![](https://img.atcoder.jp/abc289/d6d2cc458bbc92e975ba267856f673cf.png) 条件を満たす操作の列であれば何を出力しても正答となるので、例えば Yes 7 3 9 0 7 2 9 1 8 1 と出力しても正答となります。 ![](https://img.atcoder.jp/abc289/3faa56b1d245b87bd4cc36083495383c.png)

Sample Explanation 2

どのように操作しても点 (8,4) (8,4) に移動することはできません。 ![](https://img.atcoder.jp/abc289/eb363d09e74f89c5474a4fc7529308bc.png)

Sample Explanation 3

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