luogu#P6955. [NEERC2017] Designing the Toy
[NEERC2017] Designing the Toy
题目描述
You are the main toy producer in the city. Recently you bought a that provides you with an unprecedented opportunity for designing new fancy toys for children.
In a package with the there is a booklet containing several examples of what can be created with it. One of the examples is a figure that looks like a triangle, like a circle, or like a square depending on which of its sides you are looking at.
Unfortunately, it turned out that the booklet describes the most recent version of your printer. Your printer is only able to create figures that consist of voxels (three-dimensional pixels), i.e . figures that look like a union of a unit-length cubes that are the cells of a three-dimensional grid. Thus, you are not able to print any smooth
figures (like a sphere, for example) with it. On the other hand, important feature of your model is its ability to create figures whose parts are not even connected with each other by putting wires of a negligible thickness between them.
You like the idea of the figure in the booklet, so you decided to improve upon this idea. Instead of specifying shapes of figure projections from different perspectives, you would specify their areas. In this problem, a voxel is defined by a triple of integers , which corresponds to a unit cube [x , [y , [z ,
You are given three positive integers a , and . Your task is to find a description of a figure consisting of one or more voxels, for which the area of its orthogonal projection onto the plane Oxy is a , the area of its orthogonal projection onto the plane Oxz is , and the area of its orthogonal projection onto the plane Oyz is , or to determine that it is impossible.
输入格式
The only line of the input contains three integers a , , and a , -- the desired area of orthogonal projections onto the planes Oxy, Oxz, and Oyz correspondingly.
输出格式
If it is impossible to find the desired figure, print only the integer .
Otherwise, in the first line print the integer , defining the number of voxels in the figure. Then print triples defining the voxels of the figure. Voxels may be printed in any order, but no voxel may be repeated twice.
The number of voxels should not exceed
Any figure with the requested projection areas is accepted.
题目大意
题目描述
你是这里的玩具生产大佬。最近你买了一台 3D 打印机,它给你提供了一个大赚一笔创造新玩具的机会。
你的打印机只能打印由一个个单位方块(棱长为 的正方体)构成的几何体。因此,你不能打印出任何“光滑”的几何体(比如球体)。另外,这台打印机打印的几何体可以有完全不相连甚至浮空的部分。
建立空间直角坐标系。一个 的方块用整数三元组 表示。
现在你想指定打印出的几何体在平面 ,平面 和平面 上的投影面积。
给出三个正整数 ,依次表示几何体在平面 ,平面 和平面 上的投影面积。判断该集合体是否存在,若存在,找到满足条件的几何体。
输入格式
一行,包含 个正整数 。
输出格式
如果所求几何体不存在,输出 -1
。
否则,输出的第一行包含一个整数 ,表示图中方块的数量。
接下来 行,每行 个整数 表示每个方块的位置。方块可以按任意顺序输出,但不能重复。
的值不应超过 。
任何满足条件的几何体都算作正确。
提示
时间限制:3s,内存限制:512MB。
Translated by Georiky
4 3 5
6
0 0 0
0 1 0
0 2 0
0 2 2
1 2 2
0 0 2
100 1 1
-1
提示
Time limit: 3 s, Memory limit: 512 MB.