E - 切り取り線 (Cutting) Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点： 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

この入力の場合，切り取り線は下図のようになる．

2014-ho-t5-fig01.png

よって，切り取り線によって紙は 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

この入力の場合，切り取り線は下図のようになる．

2014-ho-t5-fig02.png

よって，切り取り線によって紙は 5 つの部分に分かれる．なお，この入力は小課題 4 の条件を満たしていない．

Source Name

JOI 2013/2014 本選 問題5