Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB
统计

译自 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\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 分]

没有额外限制。