페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6124

자르기 4s 256MB

문제

JOI 군은 종이접기를 취미로 하고 있다. 오늘도 JOI 군은 종이접기 작품을 만들려고 한다.

먼저, JOI 군은 설계도에 따라 1장의 직사각형의 종이에 N개의 절단선을 인쇄했다. 각 절단선은 종이의 세로 또는 가로의 변에 평행한 선분이다.

종이를 잘라서 만들 수 있는 모든 부분은 작품의 부품으로 사용된다. 당연한 것이지만, 부품 수가 많은 작품은 제작이 힘들다. JOI 군은 모든 절단선에 따라 종이를 잘랐을 때, 종이가 몇 개의 부분으로 나뉘는지 알고 싶다.

종이의 크기와 N개의 절단선의 정보가 주어진다. 이들 절단선에 따라 종이를 잘랐을 때, 종이가 몇 개의 부분으로 나뉘는지를 구하는 프로그램을 작성하라.


입력

첫 번째 줄에는, 정수 W, H, N이 공백을 구분자로 하여 쓰여져 있다. W는 종이의 가로의 길이를, H는 종이의 세로의 길이를, N은 절단선의 개수를 각각 나타낸다. 종이의 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위를, 각각 좌표 (0, 0), (W, 0), (0, H), (W, H) 로 나타낸다. 이어지는 N행의 i행 (1 ≤ i ≤ N) 에는 정수 A_i, B_i, C_i, D_i (0 ≤ A_i ≤ C_i ≤ W, 0 ≤ B_i ≤ D_i ≤ H) 이 공백을 구분자로 하여 쓰여져 있다. 이는 i번째 절단선이 (A_i, B_i)와 (C_i, D_i) 를 잇는 선분이라는 것을 나타낸다. 이 선분은 종이의 어느 변에 평행한 선분이다. 즉, A_i = C_i 와 B_i = D_i 중에 정확히 1 개가 성립한다. 또한, 어떤 절단선과 그것에 평행한 다른 절단선이 공유점을 가지는 것은 없으며, 어떤 절단선과 그것에 평행한 종이의 변이 공유점을 가지는 것도 없다.

제한

  • 1 ≤ W ≤ 1\ 000\ 000\ 000

  • 1 ≤ H ≤ 1\ 000\ 000\ 000

  • 1 ≤ N ≤ 100\ 000


출력

종이가 몇 개의 부분으로 나뉘는지를 출력하라.


부분문제

번호 점수 조건
#15점

  • W ≤ 1\ 000

  • H ≤ 1\ 000

  • N ≤ 1\ 000

#25점

  • N ≤ 1\ 000

#320점

  • 공유점을 가지는 절단선의 쌍의 개수는 100\ 000 이하이다.

#420점

  • 절단선 위의 임의의 점에서 종이의 어떤 변 위의 점까지 몇 개의 절단선을 따라서 갈 수 있다.

#550점

  • 추가 제한 조건이 없다.


예제 #1

10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9
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
5

서브태스크 4의 조건을 만족하지 않는다.


출처

JOI 2014 5번
로그인해야 코드를 작성할 수 있어요.