로스웰의 UFO 정육면체

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

요약

정수 좌표에 놓인 거울이 있는 정육면체에서 아래로 들어오는 모든 광선을 추적해 각 면으로 나가는 광선 수와 반사 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 시뮬레이션, 구현, 해시맵, 기하
정답자: 아직 제출이 없습니다

문제

밥(Bob)과 앨리스(Alice)는 미국 뉴멕시코주 로스웰에 산다. 두 사람은 미확인 비행 물체(UFO)가 남기고 간 이상한 물건을 주웠다. 이 물건은 아주 작은 구멍이 촘촘히 뚫린, 한 변의 길이가 $s$ ( $1 \le s \le 2^{15}$ )인 커다란 정육면체이며, 각 면마다 다르게 빛난다. 정육면체 내부의 어떤 장치가 햇빛을 반사하여, 각 면의 구멍 중 일부에서만 빛이 새어 나온다.

관찰 결과, 정육면체 안에는 서로 다른 정수 좌표에 놓인 양면 거울이 $n$ ( $1 \le n \le 10^6$ )개 들어 있다. 각 거울은 아주 작으며(지름이 1 단위 미만), $45^\circ$ 기울어져 아래 여섯 가지 방향( $0$ 부터 $5$ ) 중 하나로 놓여 있다. 각 방향은 두 축을 짝지어 광선을 $90^\circ$ 꺾으며, 짝지어지지 않은 나머지 한 축 방향으로 진행하는 광선(즉 진행 방향이 거울 평면 안에 있는 광선)은 거울과 상호작용하지 않고 그대로 통과한다.

번호	거울 평면	반사 (나머지 한 축 방향은 그대로 통과)
0	x-y	+x ↔ −y, +y ↔ −x; ±z 통과
1	x-y	+x ↔ +y, −x ↔ −y; ±z 통과
2	y-z	+y ↔ −z, −y ↔ +z; ±x 통과
3	y-z	+y ↔ +z, −y ↔ −z; ±x 통과
4	z-x	+z ↔ −x, −z ↔ +x; ±y 통과
5	z-x	+z ↔ +x, −z ↔ −x; ±y 통과

정육면체는 $0 \le x, y, z \le s$ 영역을 차지한다. 태양은 위쪽에 있으므로 빛은 $+y$ 방향(아래쪽)으로 들어온다. 윗면( $y = 0$ )의 모든 정수 좌표, 즉 $0 \le x \le s$ 이고 $0 \le z \le s$ 인 각 점 $(x, 0, z)$ 마다 빛 한 단위가 $+y$ 방향으로 정육면체에 들어온다. 따라서 들어오는 광선은 모두 $(s+1)^2$ 개이다. 각 광선은 직진하다가 상호작용하는 거울을 만나면 $90^\circ$ 꺾이고, 더 이상 거울을 만나지 않으면 여섯 면 중 하나를 통해 밖으로 나간다.

여섯 면의 번호 $0$ 부터 $5$ 는 다음과 같다.

면 번호	평면
0	z = s
1	z = 0
2	x = s
3	x = 0
4	y = s (아랫면)
5	y = 0 (윗면, 빛이 들어오는 면)

각 면에 대해, 그 면으로 나가는 광선의 개수와, 그 광선들이 나가기까지 꺾인 횟수의 총합을 구하여라.

입력과 출력

첫째 줄에 정육면체의 크기 $s$ 가 주어진다.

둘째 줄에 거울의 개수 $n$ 이 주어진다.

이어지는 $n$ 개의 줄에는 각 거울의 정보가 네 정수 $x$ , $y$ , $z$ , $o$ 로 주어진다. $(x, y, z)$ 는 거울의 좌표( $0 \le x, y, z \le s$ )이고 $o$ 는 그 방향( $0 \le o \le 5$ )이다. 어떤 두 거울도 같은 좌표에 있지 않다.

출력은 12개의 정수이며 한 줄에 하나씩 출력한다. 이 정수들은 두 개씩 여섯 묶음을 이루고, 각 묶음은 면 번호 $0, 1, 2, 3, 4, 5$ 순서대로 각 면에 대응한다. 각 묶음에서 첫 번째 정수는 그 면으로 나간 광선의 개수이고, 두 번째 정수는 그 광선들이 꺾인 횟수의 총합이다.

예제3

예제 1

입력

예상 출력

예제 2
입력
```
3
1
1 1 1 0
```
예상 출력
```
0
0
0
0
0
0
1
1
15
0
0
0
```
예제 3
입력
```
4
1
2 2 2 3
```
예상 출력
```
1
1
0
0
0
0
0
0
24
0
0
0
```