Teleporter Takahashi

AtCoder

IDabc289_f

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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$ [samples]

高桥在 $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)$。 ## 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$ * 输入中的所有值均为整数。 ## Input 输入从标准输入按以下格式给出： $s _ x$ $s _ y$ $t _ x$ $t _ y$ $a$ $b$ $c$ $d$ [samples]

Samples

Input #1

1 2
7 8
7 9 0 3

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

![image](https://img.atcoder.jp/abc289/d6d2cc458bbc92e975ba267856f673cf.png)
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.
![image](https://img.atcoder.jp/abc289/3faa56b1d245b87bd4cc36083495383c.png)

Input #2

0 0
8 4
5 5 0 0

Output #2

No

No sequence of operations leads him to point $(8,4)$.
![image](https://img.atcoder.jp/abc289/eb363d09e74f89c5474a4fc7529308bc.png)

Input #3

1 4
1 4
100 200 300 400

Output #3

Yes

Takahashi may already be at the destination in the beginning.

Input #4

22 2
16 7
14 30 11 14

Output #4

No

API Response (JSON)

{
  "problem": {
    "name": "Teleporter Takahashi",
    "description": {
      "content": "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+",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc289_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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)$.\nOn the $xy$\\-plane is a rectangle $R\\coloneqq\\lbrace(x,y)\\mid a-0.5\\leq x\\leq b+...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "高桥在 $xy$ 平面上。初始时，他位于点 $(s _ x,s _ y)$，他希望到达点 $(t _ x,t _ y)$。\n在 $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$。考虑以下操作：\n\n* 选择矩形 $R$ 中的一个格点 $(x,y)$。高桥瞬移到他当...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments