시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 1024 MB | 113 | 23 | 20 | 21.053% |
오래된 컴퓨터에서 그림판을 사용하고 있다. 그림판의 화면은 픽셀이라 부르는 칸을 가진 격자 모양이다. 가장 왼쪽 아래 픽셀의 좌표를 $(1, 1)$로 하고, 오른쪽으로 $a$번째 위쪽으로 $b$번째 픽셀의 좌표를 $(a, b)$로 한다. 초기 화면에는 수직, 수평 변을 가진 $N$개의 직사각형들이 그려져 있다. 직사각형은 이 구역안에 포함된 픽셀들로 표현된다.
$N$개의 직사각형에 $M$개의 이동 명령이 수행될 것이다. 직사각형의 이동은 동, 서, 남, 북의 4방향과 북동, 북서, 남동, 남서(수평축과 45도 방향) 4방향으로 이루어진다. 또한 이동 거리 $d$가 주어진다. 다시 말해서, 이동 명령은 방향과 거리로 주어진다. 구체적으로, 직사각형의 가장 왼쪽, 아래 모서리 픽셀의 좌표가 $(a, b)$라 하면, 동, 북, 서, 남 방향으로 거리 $d$만큼의 이동은 모서리가 각각 $(a+d, b)$, $(a, b+d)$, $(a-d, b)$, $(a, b-d)$가 된다. 또한 북동, 북서, 남서, 남동 방향으로 거리 $d$만큼의 이동은 각각 $(a+d, b+d)$, $(a-d, b+d)$, $(a-d, b-d)$, $(a+d, b-d)$가 된다 (그림 1).
그림 1
화면에서 직사각형 $R$의 거리 $d$만큼 이동은 초기 위치를 포함해서 $R$이 거리 1 만큼 이동할 때마다 $R$의 모습을 순서대로 빠르게 나타냄으로서 구현된다. 하지만 우리의 컴퓨터는 아주 오래 되어서 $R$의 이동 시 렉이 심하게 걸린다. 결과적으로 $R$의 이동에서 그리게 되는 모든 $R$의 모습이 화면에 그대로 남아있게 된다. 따라서 $R$이 거리 $d$만큼 이동하면, $d$개의 직사각형들이 새롭게 화면에 만들어진다. 예를 들어, 아래 그림 2에서 직사각형이 북동방향으로 거리 3만큼 이동하면, 3개의 직사각형들이 만들어져서 총 4개의 직사각형이 화면 위에 남게 된다. 물론, 이동 후에는 북동 방향 끝에 있는 직사각형이 $R$ 이 된다.
그림 2
$M$개의 이동 명령을 수행한 후 $Q$개의 질의가 주어질 것이다. 각 질의는 평면 상의 픽셀 $p$로 주어진다. 질의에 대한 대답으로 픽셀 $p$를 포함하는 직사각형들의 개수를 출력한다.
첫째 줄에 공백으로 구분된 세 정수 $N$, $M$, $Q$가 주어진다.
다음 $N$개의 줄에는 공백으로 구분된 네 개의 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어지며, 직사각형의 가장 왼쪽 아래 픽셀의 좌표가 $(x_1, y_1)$, 가장 오른쪽 위 픽셀의 좌표가 $(x_2, y_2)$임을 의미한다. 직사각형은 $1$부터 $N$의 정수로 나타내며, $1$번 직사각형부터 순서대로 주어진다.
다음 $M$개의 줄에는 공백으로 구분된 세 개의 정수 $v_i$, $x_i$, $d_i$가 주어진다. $x_i$번째 직사각형이 $v_i$ 방향으로 $d_i$만큼 이동함을 나타낸다. $v_i$의 값은 다음과 같다.
다음 $Q$개의 줄에는 공백으로 구분된 두 정수 $x$, $y$가 주어지며, 질의에 해당하는 평면 상의 픽셀 $p$의 좌표 $(x, y)$를 나타낸다.
각각의 질의마다 질의의 픽셀 $p$를 포함하는 직사각형들의 개수를 출력한다. $i$번째 줄에는 $i$번 질의의 결과를 출력해야 한다. ($0 ≤ i ≤ Q-1$)
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | $N \le 100, M = 0$ |
2 | 8 | $M = 0$ |
3 | 11 | $M \le 100$ |
4 | 13 | $v_i \in \{0, 2, 4, 6\}$ ($0 \le i \le M-1$). 즉, 직사각형은 상하좌우로만 움직인다. |
5 | 12 | $x_1 = x_2, y_1 = y_2$ |
6 | 48 | 추가적인 제약 조건이 없다. |
1 8 3 2 1 2 1 0 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 1 1 2 1 4 2
0 2 1
2 0 3 3 3 7 7 4 4 6 6 5 5 3 7 8 8
2 1 0
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon F번
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2021 > 1차 선발고사 3번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon F번