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

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

접힌 종이 색칠하기

시간 제한2초메모리 제한128 MB

요약
W 곱하기 H 직사각형을 세로선과 여러 번의 가로 접기로 K번 접고, 각 회차마다 직사각형 하나를 모든 겹에 칠한 뒤 펼쳤을 때 마지막에 칠해지지 않은 넓이를 구한다.
난이도

어려움10점 중 9점

유형
기하, 시뮬레이션, 구현, 분할 정복
정답자
아직 제출이 없습니다

문제

지민이는 가로가 W, 세로가 H인 직사각형 종이를 가지고 있다. 지민이는 다음 과정을 K번 반복해 종이에 색을 칠한다. 0 <= i < K인 i번째 과정은 다음과 같다.

  1. 종이를 직선 x = f[i]를 따라 접는다. 왼쪽 부분이 오른쪽 부분 위로 올라가도록 접는다.
  2. 현재 종이를 가로 방향으로 c[i] + 1개의 높이가 같은 구간으로 나눈 뒤, 위쪽 구간부터 차례대로 c[i]번 접는다.
  3. 현재 접힌 상태에서 가장 왼쪽 아래 점을 (0, 0)으로 잡는다. 왼쪽 아래 꼭짓점이 (x1[i], y1[i])이고 오른쪽 위 꼭짓점이 (x2[i], y2[i])인 직사각형 영역을 칠한다. 물감은 겹쳐진 모든 종이층에 스며든다.
  4. 종이를 다시 펼친다.

모든 과정이 끝난 뒤, 색칠되지 않은 영역의 넓이를 구하시오.

입력

첫째 줄에 세 정수 W, H, K가 주어진다.

다음 K개의 줄에는 각각 한 번의 접기와 색칠 정보를 나타내는 여섯 정수 f[i], c[i], x1[i], y1[i], x2[i], y2[i]가 주어진다.

출력

색칠되지 않은 영역의 넓이를 출력한다.

제한

  • 1 <= W, H <= 10^9
  • 1 <= K <= 50
  • 0 <= f[i] <= W
  • 0 <= c[i] <= 1,000
  • c[i] + 1은 H의 약수이다
  • 0 <= x1[i] < x2[i] <= max(f[i], W - f[i])
  • 0 <= y1[i] < y2[i] <= H / (c[i] + 1)

예제7

  1. 예제 1

    입력
    6 6 2
2 1 1 2 3 3
5 2 2 0 4 2
    예상 출력
    18

  2. 예제 2

    입력
    5 6 1
2 2 1 1 3 2
    예상 출력
    21

  3. 예제 3

    입력
    2 4 2
0 1 0 1 2 2
0 0 0 1 1 4
    예상 출력
    3

  4. 예제 4

    입력
    21 30 5
3 4 4 2 7 5
21 14 0 0 19 2
7 9 2 1 6 2
11 5 5 2 11 4
13 4 9 3 12 5
    예상 출력
    27

  5. 예제 5

    입력
    30 42 5
16 5 3 0 14 2
24 1 1 1 22 15
25 6 5 0 12 1
21 13 8 0 18 1
4 20 9 1 13 2
    예상 출력
    336

  6. 예제 6

    입력
    26 60 5
17 4 9 1 13 3
17 1 1 3 4 14
24 11 20 0 23 1
4 0 18 45 19 46
21 2 7 12 13 14
    예상 출력
    1319

  7. 예제 7

    입력
    17 3 6
17 2 7 0 12 1
2 0 6 0 10 3
10 0 4 1 6 2
2 2 11 0 12 1
10 0 0 1 4 2
13 0 5 1 12 2
    예상 출력
    20