← 返回题目列表

AtCoder · joi2014ho5

E. 切割线(切割)

中文机器翻译题面 查看原题

配点: 100 点

JOI 君从事纸工艺。今天 JOI 君也打算制作纸工艺作品。

首先,JOI 君按照设计图 1 张长方形的纸上 N 打印书的裁切线。每条裁切线都是与纸张的纵边或横边平行的线段。切割纸张所得到的所有部分都将作为作品中的某些部件使用。理所当然,部件数量多的作品制作起来也更费力。JOI君想知道,如果按照所有裁切线将纸切开,纸会被分成多少个部分。

課題

给出纸的大小,N 以及书的裁切线信息。根据这些裁切线切割纸张时,编写程序求出纸会被分成多少个部分。


入力

从标准输入读取以下数据。

  • 1 行表示整数 W, H, N 使用空格作为分隔符。W 表示纸的横边长度,H 表示纸的纵边长度,N 表示裁切线的数量。纸的左下角、右下角、左上角和右上角分别用坐标 (0, 0), (W, 0), (0, H), (W, H) 表示。
  • 继续 N 行 i 行目 (1 \leqq i \leqq N) 中,整数 A_i, B_i, C_i, D_i (0 \leqq A_i \leqq C_i \leqq W,0 \leqq B_i \leqq D_i \leqq H) 以空格分隔书写。这表示第 i 条切割线是连接 (A_i, B_i) 和 (C_i, D_i) 的线段。这条线段是与纸张某条边平行的线段。也就是说,在A_i = C_i 和 B_i = D_i 中正好有 1 条成立。此外,某条切割线与平行它的其他切割线不会有交点,某条切割线与平行的纸边也不会有交点。在标准输出中,输出表示纸张被分成多少部分的整数

出力

所有输入数据满足以下条件 1 行上。


制限

满足以下条件

  • 1 \leqq W \leqq 1\,000\,000\,000.
  • 1 \leqq H \leqq 1\,000\,000\,000.
  • 1 \leqq N \leqq 100\,000.

小課題

小課題 1 [5 点]

不同的切割线形成的有交点的组合数量为

  • W \leqq 1\,000.
  • H \leqq 1\,000.
  • N \leqq 1\,000.

小課題 2 [5 点]

不同的切割线形成的有交点的组合数量为

  • N \leqq 1\,000.

小課題 3 [20 点]

条切割线的组数为 2 不超过100\,000 。

小課題 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

在这个输入的情况下,切割线如下面的图所示。

因此,纸张通过切割线被分成 4 个部分。顺便提一下,这个输入满足小课题的条件。 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

在这个输入的情况下,切割线如下面的图所示。

因此,纸张通过切割线被分成 5 个部分。顺便提一下,这个输入满足小课题的条件。 4 条件。