南极的冰山下冰冻着许多奥秘。为了探究,跳蚤国王选定了一大片富含远古微生物的冰山样本,准备将其切割成小片以供研究。
冰山样本是一片面积巨大的矩形冰片。放置在地上时,可视为占据了平面直角坐标系的整个第一象限 [0, +\infty) \times [0, +\infty)。
为了切割冰片,跳蚤国王放置了 n+m 个激光发射器:
- 其中有 m 个竖直向上的激光发射器,第 i 个竖直向上的激光发射器位于 (i, 0),所发出的激光的强度为 10^{100};
- 其中有 n 个水平向右的激光发射器,第 i 个水平向右的激光发射器位于 (0, i),所发出的激光的强度为 l_i。
这里的激光发射器都是为切割冰片而量身定制的。所发射的激光在空气中几乎无法传播,但在冰中可以正常穿行,并会产生极高的温度。
最开始,所有光束发射器都是关闭的。在一次操作中,操作员需要按照某种顺序将它们依次激活。当一个发射器被激活时,它会瞬间向它所对应的方向发出一束激光。该激光会不断沿该射线方向延伸,直到碰到另一束激光已经融化过的点(即接触到空气),或延伸距离到达了这个激光发射器所发出的激光的强度。然后在很短的时间内,该激光所经过的路径上的冰会同时融化,从而达到切割的效果。
例如,m=n=3,l_1=1,l_2=4,l_3=2 时,如果依次激活位于 (3, 0), (0, 2), (2, 0), (0, 3), (0, 1), (1, 0) 的光束发射器,那么最后冰片被激光切割后的效果如下图所示:
