bzoj#P1544. 立方镜子

立方镜子

题目描述

研究光路是很有意思的。 Doggy 最近正在研究一个叫做立方镜子的东西。

立方镜子是一个边长为 SS 的立方体。我们可以在一些整点上放一面平板镜子。镜子一共有 66 种摆放方向:

整个立方镜子里面放了 mm 面平面镜子,每个平面镜子都是双面的。现在 Doggy 把这个镜子放在阳光底下直射(阳光从 yy 轴负方向射向 yy 轴正方向):

我们只考虑射向整点的光线,那么这样的光线一共有 (s+1)×(s+1)(s+1)\times (s+1) 条。这些光线经过一系列平板镜子的反射(如果没有镜子阻挡也是可能直接射穿的)之后最终会从立方镜子的某个面出来(上图已经将面编号,并给定坐标轴方向)。现在你的任务就是求每个面出来的光线条数以及这些光线的反射次数和。

输入格式

第一行一个数 ss,为立方镜子的边长。

第二行一个数 mm,为镜子个数。

下接 mm 行,每行四个数描述一面镜子 xxyyzzdd 表示在坐标 (x,y,z)(x,y,z) 的点上有一面方向为 dd 的镜子。

输出格式

66 组,每组两行,按顺序分别输出从面 00 到面 55 的出射光线条数,以及这部分光线的总反射次数。

样例输入

5
4
4 4 0 0
1 3 0 1
1 1 0 0
4 1 0 1

样例输出

0
0
0
0
1
1
1
1
34
0
0
0

数据规模及约定

对于 100%100 \% 的数据: 1m2×1051 \le m \le 2 \times 10^51s2151 \le s \le 2^{15}0x,y0 \le x,yzsz \le s0d50 \le d \le 5

保证不会有两个镜子坐标相同。

提示

注:我们认为每个平板镜子都是无限薄的,即如果有一束光线从一个镜子的侧面射入,它会方向不变的射出。

样例解释:

22 号面射出去了一根光线:从 (4,0,0)(4,0,0) 落下击中 (4,1,0)(4,1,0) 处的镜子然后射出去。反射次数为 11

33 号面射出去了一根光线:从 (1,0,0)(1,0,0) 落下击中 (1,1,0)(1,1,0) 处的镜子然后射出去。反射次数为 11

剩余的的 362=3436-2=34 条光线没有经过任何反射直接从 44 号面射出。

(1,3,0)(1,3,0) 处的镜子与 (4,4,0)(4,4,0) 处的镜子没被用到。

题目来源

HNOI2009 集训 Day3