QOJ.ac

QOJ

时间限制: 20 s 内存限制: 1024 MB 总分: 32

#12071. 立方体 UFO

统计

一个神秘的立方体外星飞船出现在多伦多上空!在本题中,多伦多被视为三维空间中一个平行于 $xz$ 平面且位于 $y = -3$ km 处的平面。该外星飞船是一个边长为 $1$ km 的实心立方体,中心位于 $(0 \text{ km}, 0 \text{ km}, 0 \text{ km})$,其八个角位于 $(\pm 0.5 \text{ km}, \pm 0.5 \text{ km}, \pm 0.5 \text{ km})$。飞船在平面上投下了阴影;形式上,阴影是立方体在平面上的正交投影。(我们认为太阳位于多伦多平面上方沿 $y$ 轴无限远处的点。)

军方愿意容忍这艘飞船,只要外星人满足他们的官僚要求:阴影覆盖平面的面积必须与 $A \text{ km}^2$ 足够接近(具体定义见“输出格式”部分)。他们聘请了身为几何语言学专家的你,将这一要求传达给外星人。在目前的交流中,你已经了解到飞船的大小不能改变,飞船的中心不能移动,但飞船可以在原地进行任意旋转。

请找到一种方法,让外星人旋转飞船,使得阴影面积接近 $A$。请用三个点来表示你的旋转:任意三个非对立面的中心。

输入格式

第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例;每个测试用例包含一行,给出一个有理数 $A$,即所需的阴影面积(单位为 $\text{km}^2$),小数点后恰好有六位数字。

保证对于本题中允许的 $A$ 值,总有一种旋转飞船的方式能满足要求。

输出格式

对于每个测试用例,首先输出一行 Case #x:,其中 $x$ 是测试用例编号(从 $1$ 开始)。然后,再输出三行,每行包含三个有理数:即你所提供的三个面中心之一的 $x, y, z$ 坐标。你可以使用小数(例如 0.000123456)或科学计数法(例如 1.23456e-4)。

你的答案被认为是正确的,当且仅当以下所有条件成立:

  1. 每个点到原点的距离(单位为 $\text{km}$)必须在 $0.5 - 10^{-6}$ 到 $0.5 + 10^{-6}$ 之间(包含边界)。
  2. 连接原点到每个点的线段之间的夹角(单位为弧度)必须在 $\pi/2 - 10^{-6}$ 到 $\pi/2 + 10^{-6}$ 之间(包含边界)。
  3. 阴影面积(单位为 $\text{km}^2$),通过将所有 $8$ 个顶点投影到 $y = -3$ 平面上并计算这些投影点的凸包面积得出,必须在 $A - 10^{-6}$ 到 $A + 10^{-6}$ 之间(包含边界)。我们将通过 $\pm p_1 \pm p_2 \pm p_3$ 计算顶点(即对于每个 $p_i$,我们使用向量加法加上 $p_i$ 或 $-p_i$),其中 $p_1, p_2, p_3$ 是你提供的面中心。

请注意,你可能需要输出小数点后超过 $6$ 位数字,以确保通过上述检查。如果存在多个可接受的答案,你可以输出其中任何一个。

数据范围

$1 \le T \le 100$。

测试集 1(可见)

$1.000000 \le A \le 1.414213$

测试集 2(隐藏)

$1.000000 \le A \le 1.732050$

样例

输入 1

2
1.000000
1.414213

输出 1

Case #1:
0.5 0 0
0 0.5 0
0 0 0.5
Case #2:
0.3535533905932738
0.3535533905932738 0
-0.3535533905932738
0.3535533905932738 0
0 0 0.5

说明

在样例 1 中,无需旋转立方体;由于其两个面已经平行于平面,立方体投下的阴影已经是一个边长为 $1$ 的正方形。

在样例 2 中,一种可能的解决方案是告诉外星人将立方体绕 $x = y = 0$ 线旋转 $45$ 度,从而产生一个尺寸为 $1$ 和 $\sqrt{2}$ 的矩形阴影。

以下粗略图像展示了样例 1 和样例 2 的立方体及其阴影。图中显示了太阳以示清晰,但请记住,它实际上是沿 $y$ 轴无限远处的点。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.