#3014. 单位正方形装箱
单位正方形装箱
题目描述
你要把一个由 个单位正方形(边长为 的正方形)组成的图形装进一个轴对齐的大正方形(边与坐标轴平行)里,并让这个大正方形尽可能小。
每个小正方形都可以任意平移、任意旋转;边长固定为 ,不能弯曲、不能缩放,不同小正方形的朝向可以互不相同。摆放时要求任意两个小正方形的内部不相交:允许边与边接触、顶点与顶点接触,但两个小正方形内部的重叠面积必须是 。
第 个()小正方形由它的中心 与逆时针旋转角 (单位:弧度)唯一确定,它的四个顶点是
$$\left(x_i+\frac{\sigma_1\cos\theta_i-\sigma_2\sin\theta_i}{2},\quad y_i+\frac{\sigma_1\sin\theta_i+\sigma_2\cos\theta_i}{2}\right), \qquad \sigma_1,\sigma_2\in\{+1,-1\}.$$把所有 个小正方形的 个顶点放在一起,记这些顶点横坐标的最小值与最大值分别为 ,纵坐标的最小值与最大值分别为 ,则能把它们全部装下的最小轴对齐正方形的边长是
$$L=\max\bigl(x_{\max}-x_{\min},\;y_{\max}-y_{\min}\bigr).$$(把整个图形平移不会改变 ,所以大正方形摆在哪里、坐标原点取在哪里都不影响结果。)
你的目标:对每一个测试点,给出一组合法的 ,使该测试点的 尽可能小。
本题共有 个相互独立的测试点,第 个测试点对应的规模是 ,也就是 。每个测试点单独评测、单独给分,允许只提交其中一部分测试点。
输入格式
本题是**提交答案型(output-only)**题目,没有输入。
第 个测试点()的规模参数为 。你需要为它提交一份数据,用 个单位正方形的中心坐标与旋转角描述一个合法摆放。测试点编号与 一一对应:既可以每个测试点单独一个 <n>.out 文件,也可以把所有测试点写进同一个文件并用 # n 分块标号(见「输出格式」)。
输出格式
本题的答案有两种合法提交方式,任选其一,不要混用(平台要求单文件提交时用方式 (b))。
(a) 逐测试点文件。 对每个测试点 (),在提交目录下提供一个名为 <n>.out 的文本文件,例如 5.out。可以只提供其中任意一部分;没有提供的测试点记 分。
(b) 单文件分块。 把所有要提交的测试点写进同一个答案文件:每个测试点占用一块,块的第一行是独占一行的块头,形如 # 5(#、一个空格、测试点编号 );紧接着是这个测试点的 行数据。块与块之间的顺序任意,块与块之间可以有空行,也可以只写其中一部分测试点。
两种方式下,一个测试点的数据部分格式相同:必须恰好 行,第 行()包含三个十进制实数 、、,用一个空格分隔,依次表示第 个单位正方形的中心横坐标、中心纵坐标与逆时针旋转角(弧度)。
范围与精度要求:
- ,;若某个 或 ,该测试点记 分。
- 可以是任意实数,评测器不对它的取值范围作限制,而是先把它对 取模后再使用(旋转 的整数倍不改变正方形本身);建议把 写在 内。
- 每个数必须至少输出 位小数(推荐 位)。评测器按实数解析、不要求固定位数,可以使用小数形式或科学计数法;但合法性的判定容差是 的绝对量,输出位数不足带来的数值误差由选手自负。
- 所有数都必须是有限实数:出现
nan、inf或任何无法解析为实数的记号,该测试点记 分。 - 行内、行首、行尾多余的空格按常规忽略。一个测试点的数据部分必须恰好 行、每行 个数:数据部分末尾的空行会被忽略,但中间出现空行会导致行数不符,该测试点记 分。
- 方式 (b) 中,块头
# n必须独占一行、且只能出现在它所在块的开始处;没有块头的数据视为未提交。
你不需要输出 :评测器会按「题目描述」中的公式,从你给出的 自行算出 。
提示
合法性如何判定。 评测器先按「题目描述」中的顶点公式算出全部 个顶点。对每一对小正方形 ,取 的两条边法向与 的两条边法向作为 个候选分离轴。把 的全部顶点分别投影到某个候选轴上,得到两条投影区间 与 ,定义这一对区间在该轴上的重叠长度为
表示两条区间在该方向上有重叠, 表示两者的距离为 。只要存在某个候选轴使 ,就判定这两个小正方形内部不相交;若 个候选轴上都有 ,则判为内部重叠、答案非法(也就是把数值重叠深度不超过 的情形视为内部交集面积为 )。当所有 对小正方形都满足该判定时,答案合法;否则该测试点记 分。因此边接触、顶点接触都是允许的,但任何"看起来只差一点点"的重叠都可能被判为非法。
评分口径。
记
$$L_{\mathrm{base}}(n)=\left\lceil\sqrt n\right\rceil,$$它是把 个单位正方形按 $\left\lceil\sqrt n\right\rceil\times\left\lceil\sqrt n\right\rceil$ 的轴对齐网格摆放(每个格子放一个、朝向全部取 )得到的边长,任何人都能做到。出题组的参考构造为每个测试点给出了参考边长 ,这些值列在随题包附带的 data/reference.csv 的 L_ref 列中。
计分集合。 记
$$S=\{\,n:\ 1\le n\le 1000,\ L_{\mathrm{ref}}(n)<L_{\mathrm{base}}(n)\,\},$$也就是参考构造比网格做得更好的那些测试点(当前 ),它们在 data/reference.csv 中由 status=best-known 标出。
测试点 的得分:
- 若 :
其中 表示把 截断到区间 内。当 时,每个这样的测试点最多得 分: 得满分, 得 分,两者之间按改进的比例线性给分。
- 若 :,无论答案合法与否都不影响分数。这些测试点的网格摆法已经是最优的(全部完全平方数都在其中; 的最优边长均为 ,经穷举与简单几何论证确认),没有可改进的余地,不必提交。
总分是各测试点得分之和,最多 分,保留 位小数(四舍五入)。因此:完全按网格摆放得 分;达到出题组参考构造的水平得 分。答案非法的测试点记 分。
示例答案。 随题附有 data/samples/ 目录,其中 4.out 与 5.out 分别是 与 的示例答案文件,同目录的 README.md 说明了它们的摆放方式与按题面口径算出的得分。,即使是网格摆法也只有 分;,其 已经达到(并略微优于),得 分。它们分别演示了「不在计分集合里、得 分」与「在计分集合里、按相对参考构造的改进比例得分」两种情形。
参考表。 出题组为每个测试点准备的参考构造边长列在随题包附带的 data/reference.csv 中(列:n,L_base,L_ref,status,note)。其中 status 说明该行的结论强度:best-known 表示出题组在该点找到了改进构造(尚未证明最优),grid-fallback 表示出题组在该点只有网格兜底,optimal-proven 表示该点的最优性已被证明;note 是相应的说明文字。你可以据此确认哪些测试点属于计分集合 ,并对照自己的 与参考构造的差距。
关于评测平台。 本题目在 Hydro 上以「提交答案题(submit_answer)」发布,此时答案文件采用上述方式 (b) 的单文件分块格式(每块以独占一行的 # n 开头)。