2760 「JOI 2014 Final」裁剪线

内存限制:256 MB 时间限制:3000 ms

题目描述

译自 JOI 2014 Final T5「切り取り線」

JOI 君对剪纸很感兴趣。今天 JOI 君也准备做剪纸。

首先,JOI 君根据设计图在一张长方形的纸上画了 $N$ 条裁剪线。每条裁剪线都是一条与纸的长或宽平行的线段。

从纸上切下来的所有部分都会被用作作品中的部件。可以理解的是,部件数量越多的作品制作起来越困难。JOI 君想知道,当他沿着每一条裁剪线把纸剪开之后,这张纸被分成了多少个部分。

任务

给出纸的大小和 $N$ 条裁剪线的相关信息,请求出沿着这些裁剪线剪开之后,这张纸被分成了多少个部分。

输入格式

第一行包含三个以空格分开的整数 $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

输入数据对应裁剪线位置如下图:

cutting1.png

因此,纸会被裁剪线划分成 4 个部分。另外,本组输入数据满足子任务 4 的条件。

样例 2

输入数据对应裁剪线位置如下图:

cutting2.png

因此,纸会被裁剪线划分成 5 个部分。另外,本组输入数据并不满足子任务 4 的条件。

数据范围与提示

全部的输入数据满足以下条件:

  • $1\le W\le 10^{9}$
  • $1\le H\le 10^{9}$
  • $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 分]

没有额外限制。

样例

样例输入 1

10 10 5 6 0 6 7 0 6 7 6 2 3 9 3 2 3 2 10 1 9 8 9

样例输出 1

4

样例输入 2

13 7 28 1 1 4 1 1 1 1 3 2 2 3 2 2 2 2 3 1 3 2 3 3 2 3 6 4 1 4 6 3 6 4 6 5 1 8 1 5 1 5 6 6 2 7 2 6 2 6 5 7 2 7 5 6 5 7 5 8 1 8 6 5 6 8 6 9 1 12 1 9 1 9 2 9 2 10 2 12 1 12 2 11 2 12 2 10 2 10 5 9 5 10 5 9 5 9 6 11 2 11 5 11 5 12 5 12 5 12 6 9 6 12 6

样例输出 2

5