Page not loading? Try clicking here.
Placeholder

#1450

케이크자르기 1s 64MB

Problems

"바시니아"라는 역사속에 남아있는 작은 마을에선 결혼식날 기념으로 사각형으로 만들어진 케익을, 다양한 모양의 사각형의 틀로 여러번 잘라서 결혼하는 사람들을 축하해줬다.

이번 문제에서는 사각형의 틀을 사용해서 케익을 잘랐을때 나오게 되는 케익 조각의 수를 알고자 한다. 여기서 조각의 수란, 잘라지지 않고 이어져 있는 덩어리를 뜻한다.

예를 들어 3 x 5크기의 케이크를 다음 그림과 같이 잘랐다고 하자.

이 경우 총 6개의 조각이 나오게 된다.


Input

입력의 첫 번째 줄에는 케익의 크기 H, W가 입력된다(1≤ H, W≤ 20).

H는 높이, W는 너비를 뜻한다. 그리고 그 다음 줄에는 사용된 사각형틀의 개수 N(0≤N≤50)이 입력된다.

사각형 틀의 정보는 x_1, y_1, x_2, y_2 가 입력되는데 x_i는 케이크의 맨 왼쪽에서의 거리를 뜻하고 y_i는 맨 아래쪽에서의 거리를 뜻하며 점(x_1, y_1)에서 점(x_2, y_2)를 이용해 만들어지는 사각형을 통해서 만들어지는 사각형의 둘레를 틀을 이용해서 케이크를 자른 것이다(0 ≤ x_1, x_2 ≤ W,  0 ≤ y_1, y_2 ≤ H), x_1, x_2, y_1, y_2는 정수로 주어진다.


Output

케이크가 몇 조각으로 나눠지는지를 출력한다.


Example 

3 5

3

1 1 3 2

4 0 2 3

4 0 5 1
6

Source

Tehran 2006 Preliminary, poj 3338
You must sign in to write code.