Connected?

AtCoder

IDarc076_c

Time2000ms

Memory256MB

Difficulty—

Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions $R × C$, filled with numbers. Each integer $i$ from $1$ through $N$ is written twice, at the coordinates $(x_{i,1},y_{i,1})$ and $(x_{i,2},y_{i,2})$. The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from $1$ through $N$. Here, the curves may not go outside the board or cross each other. Determine whether this is possible. ## Constraints * $1 ≤ R,C ≤ 10^8$ * $1 ≤ N ≤ 10^5$ * $0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)$ * $0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)$ * All given points are distinct. * All input values are integers. ## Input Input is given from Standard Input in the following format: $R$ $C$ $N$ $x_{1,1}$ $y_{1,1}$ $x_{1,2}$ $y_{1,2}$ : $x_{N,1}$ $y_{N,1}$ $x_{N,2}$ $y_{N,2}$ [samples]

Samples

Input #1

Output #1

YES

![image](https://atcoder.jp/img/arc076/hogehogehoge.png)
The above figure shows a possible solution.

Input #2

Output #2

NO

Input #3

Output #3

YES

Input #4

1 1 2
0 0 1 1
1 0 0 1

Output #4

NO

API Response (JSON)

{
  "problem": {
    "name": "Connected?",
    "description": {
      "content": "Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions $R × C$, filled with numbers. Each integer $i$ from $1$ through $N$ is written twice, at the coordinates $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc076_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions $R × C$, filled with numbers. Each integer $i$ from $1$ through $N$ is written twice, at the coordinates $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments