#arc076c. [arc076_c]Connected?

[arc076_c]Connected?

题目描述

Snuke正在玩一个拼图游戏。在这个游戏中,给出一个尺寸为 R×CR × C 的矩形棋盘,上面填有数字。每个整数 ii (11NN) 在坐标 (xi,1,yi,1)(x_{i,1},y_{i,1})(xi,2,yi,2)(x_{i,2},y_{i,2}) 处各写了两次。

目标是绘制一条曲线连接每个整数从 11NN 的两个写有该整数的点。在这里,曲线不能超出棋盘,也不能交叉。

判断是否可能实现这个目标。

约束条件

  • 1R,C1081 \leq R, C \leq 10^8
  • 1N1051 \leq N \leq 10^5
  • 0xi,1,xi,2R0 \leq x_{i,1},x_{i,2} \leq R (1iN1 \leq i \leq N)
  • 0yi,1,yi,2C0 \leq y_{i,1},y_{i,2} \leq C (1iN1 \leq i \leq N)
  • 所有给定的点都是不同的。
  • 所有输入值都是整数。

输入

输入以以下格式从标准输入中给出:

RR CC NN x1,1x_{1,1} y1,1y_{1,1} x1,2x_{1,2} y1,2y_{1,2} : xN,1x_{N,1} yN,1y_{N,1} xN,2x_{N,2} yN,2y_{N,2}

输出

如果可以实现目标,打印 YES;否则打印 NO

示例输入1

4 2 3
0 1 3 1
1 1 4 1
2 0 2 2

示例输出1

YES

上图显示了一个可能的解决方案。

示例输入2

2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1

示例输出2

NO

示例输入3

5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1

示例输出3

YES

示例输入4

1 1 2
0 0 1 1
1 0 0 1

示例输出4

NO