P15815 [JOI 2014 Final] 裁剪线 / Cutting

JOI 君喜欢做纸艺。今天 JOI 君也打算制作一个纸艺作品。首先，JOI 君按照设计图在一张长方形纸上印刷了 $N$ 条切割线。每条切割线都是与纸的纵边或横边平行的线段。 通过切割纸张得到的所有部分都将作为作品中的某些部件使用。显然，部件数量多的作品制作起来更麻烦。JOI 君想知道，如果按照所有切割线切割纸张，纸张会被分成多少部分。 ### 任务 给定纸张的大小和 $N$ 条切割线的信息。编写程序，求出按照这些切割线切割后，纸张会被分成多少部分。

从标准输入读取以下数据。 - 第 1 行包含以空格分隔的整数 $W, H, N$。$W$ 表示纸张横向边的长度，$H$ 表示纸张纵向边的长度，$N$ 表示切割线的数量。纸张的左下、右下、左上、右上顶点分别用坐标 $(0,0), (W,0), (0,H), (W,H)$ 表示。 - 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含以空格分隔的整数 $A_i, B_i, C_i, D_i$ ($0 \le A_i \le C_i \le W$, $0 \le B_i \le D_i \le H$)。表示第 $i$ 条切割线是连接 $(A_i, B_i)$ 和 $(C_i, D_i)$ 的线段。这条线段与纸的某条边平行。也就是说，$A_i = C_i$ 与 $B_i = D_i$ 这两个条件恰好有一个成立。此外，任意一条切割线与其平行的其他切割线没有公共点，任意一条切割线与其平行的纸的边也没有公共点。

向标准输出输出一行，包含一个整数，表示纸张被分成的部分数量。

### 样例解释 1 对于此输入，切割线如下图所示。 :::align{center}  ::: 因此，切割线将纸张分成了 $4$ 个部分。注意，此输入满足子任务 4 的条件。 ### 样例解释 2 对于此输入，切割线如下图所示。 :::align{center}  ::: 因此，切割线将纸张分成了 $5$ 个部分。注意，此输入不满足子任务 4 的条件。 ### 数据范围 所有输入数据满足以下条件。 - $1 \le W \le 1000000000$ - $1 \le H \le 1000000000$ - $1 \le N \le 100000$ ### 子任务 #### 子任务 1 [5 分] 满足以下条件。 - $W \le 1000$ - $H \le 1000$ - $N \le 1000$ #### 子任务 2 [5 分] 满足以下条件。 - $N \le 1000$ #### 子任务 3 [20 分] 存在公共点的不同切割线对的数量不超过 $100000$。 #### 子任务 4 [20 分] 从任意一条切割线上的任意一点出发，都可以沿着若干条切割线到达纸的某条边上的点。 #### 子任务 5 [50 分] 没有额外限制。 --- 翻译由 DeepSeek V3.2 完成