bzoj#P1541. [POI2005]Lus- Mirror trap
[POI2005]Lus- Mirror trap
题目描述
A mirror trap is a cuboid made of mirrors, the reflecting sides of which are facing the interior of the cuboid. Precisely in the geometric centre of the cuboid there is a miniature laser (whose dimensions we shall neglect). The task is to aim the laser in such a way that the beam travels the longest total distance possible and returns to the laser itself. By total distance we shall denote the sum of distances traveled by the laser beam in each of the three directions parallel to the edges of the mirrors (i.e. we are using the so called Manhattan (city) metric).
镜子陷阱是由镜子构成的长方体,镜子的反射面对着长方体的内部。在长方体的几何中心放入一个微型激光器(尺寸忽略)。现在我们的任务是把激光向某一个方向发射,并且使光束在回到激光器自身之前,通过的总距离尽可能长。通过的总距离表示为激光束在与镜子反射面平行的三个方向的距离之和,也就是曼哈顿(城市)度量。
The dimensions of the trap are even integers. The edges and vertices of the trap, where distinct sides meet, do not reflect the laser beam. Inside the cuboid we shall introduce a cartesian coordinate system. Its axes are parallel to the edges of the trap and the laser shall be placed in the origin. The laser may be aimed at any integer point (a point whose all coordinates are integers) within the trap, the points on the surface of the mirrors included (with the single exception of the laser itself, i.e. the point ).
不同的侧面相遇的陷阱的边和顶点不会反射激光束,且陷阱的边长是整数。在长方形陷阱中,使用笛卡尔坐标系。坐标系的纵横轴分别平行于陷阱的长和宽,激光器的位置在原点。激光器可以瞄准陷阱内的任意一个点包括反射镜的表面上的点(唯一的例外就是激光器本身,点 )。
TaskWrite a programme which:
reads from the standard input the dimensions of the mirror trap,calculates such a point, that a laser beam fired from the laser it the direction of this point:
shall be reflected from the mirrors (but not necessarily from all of them), shall neither intersect an edge nor a vertex of the mirror trap, shall return to the laser, possibly from a different direction, shall travel the longest total distance possible (in the sense of the definition provided).
writes the outcome to the standard output.
我们的任务:
输入这个镜子陷阱的尺寸,通过编写的程序计算出一个点,即激光器指向这一点:这一束激光应在反射镜(但不一定是所有反射镜)反射,但是不与陷阱的边、顶点相交,最后需要回到激光器本身(不需要一定的方向)同时尽可能使得总距离长。
输入格式
A single test consists of many mirror traps to be analysed. The first line of the standard input contains a single integer , denoting the number of traps to be analysed. In the lines there are descriptions of the traps, a single per line. The description of the trap consists of three numbers , separated by single spaces. The mirror trap has the dimensions of .
输入有多个陷阱。输入的第一行包含一个整数 ,表示要分析的陷阱数。在 行中,有一个陷阱的描述,每行一个。陷阱的描述由三个用空格分隔的数字 , , 组成。 镜面陷阱的尺寸为 。
输出格式
Your programme should write exactly lines to the standard output. The 'th line should contain a solution for the 'th trap: three integers separated by single spaces, , , ,. Those numbers signify that in the 'th trap the laser should be aimed at the point, whose coordinates are .
Should there be a greater number of correct solutions, your programme ought to output any one of them.
输出 行。 第 行应包含第 个陷阱的解决方案,由空格分隔的 个数 ,,,表示激光器需要瞄准的点的坐标。
如果有多个不同的正确解决方案,则任意的输出一个。
输入样例
2
5 6 7
5 6 6
输出样例
4 5 6
4 6 5
数据规模及约定
对于 的数据:,