아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

절취선

시간 제한3초메모리 제한256 MB

요약
W by H 직사각형을 축에 평행한 N개 선분을 따라 잘라 생기는 조각 수를 구합니다.
난이도

보통10점 중 7점

유형
기하, 유니온 파인드, 정렬, 수학
정답자
아직 제출이 없습니다

문제

직사각형 종이의 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위 꼭짓점을 각각 (0,0)(0,0), (W,0)(W,0), (0,H)(0,H), (W,H)(W,H)로 둔다. 종이에는 가로 또는 세로 변과 평행한 절취선 NN개가 그려져 있다. 각 절취선은 두 끝점 (Ai,Bi)(A_i,B_i), (Ci,Di)(C_i,D_i)로 주어지며, Ai=CiA_i=C_i와 Bi=DiB_i=D_i 중 정확히 하나만 성립한다. 평행한 두 절취선은 공통점을 갖지 않고, 평행한 절취선이 종이 변과 닿지도 않는다. 모든 절취선을 따라 잘랐을 때 종이가 몇 조각으로 나뉘는지 구하라.

입력

첫 줄에 WW, HH, NN이 주어진다. 이어지는 NN줄에 각 절취선의 (Ai,Bi)(A_i,B_i), (Ci,Di)(C_i,D_i)가 주어진다.

출력

잘린 뒤 종이 조각 수를 한 줄에 출력한다.

제한

1≤W,H≤1091 \le W,H \le 10^9, 1≤N≤1051 \le N \le 10^5.

예제2

  1. 예제 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
    
  2. 예제 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