#3014. 单位正方形装箱

单位正方形装箱

题目描述

你要把一个由 nn 个单位正方形(边长为 11 的正方形)组成的图形装进一个轴对齐的大正方形(边与坐标轴平行)里,并让这个大正方形尽可能小。

每个小正方形都可以任意平移、任意旋转;边长固定为 11,不能弯曲、不能缩放,不同小正方形的朝向可以互不相同。摆放时要求任意两个小正方形的内部不相交:允许边与边接触、顶点与顶点接触,但两个小正方形内部的重叠面积必须是 00。

第 ii 个(1≤i≤n1\le i\le n)小正方形由它的中心 (xi,yi)(x_i,y_i) 与逆时针旋转角 θi\theta_i(单位:弧度)唯一确定,它的四个顶点是

$$\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\}.$$

把所有 nn 个小正方形的 4n4n 个顶点放在一起,记这些顶点横坐标的最小值与最大值分别为 xmin⁡,xmax⁡x_{\min},x_{\max},纵坐标的最小值与最大值分别为 ymin⁡,ymax⁡y_{\min},y_{\max},则能把它们全部装下的最小轴对齐正方形的边长是

$$L=\max\bigl(x_{\max}-x_{\min},\;y_{\max}-y_{\min}\bigr).$$

(把整个图形平移不会改变 LL,所以大正方形摆在哪里、坐标原点取在哪里都不影响结果。)

你的目标:对每一个测试点,给出一组合法的 (xi,yi,θi)(x_i,y_i,\theta_i),使该测试点的 LL 尽可能小。

本题共有 10001000 个相互独立的测试点,第 kk 个测试点对应的规模是 n=kn=k,也就是 n=1,2,…,1000n=1,2,\dots,1000。每个测试点单独评测、单独给分,允许只提交其中一部分测试点。

输入格式

本题是**提交答案型(output-only)**题目,没有输入。

第 kk 个测试点(1≤k≤10001\le k\le 1000)的规模参数为 n=kn=k。你需要为它提交一份数据,用 nn 个单位正方形的中心坐标与旋转角描述一个合法摆放。测试点编号与 nn 一一对应:既可以每个测试点单独一个 <n>.out 文件,也可以把所有测试点写进同一个文件并用 # n 分块标号(见「输出格式」)。

输出格式

本题的答案有两种合法提交方式,任选其一,不要混用(平台要求单文件提交时用方式 (b))。

(a) 逐测试点文件。 对每个测试点 nn(1≤n≤10001\le n\le 1000),在提交目录下提供一个名为 <n>.out 的文本文件,例如 5.out。可以只提供其中任意一部分;没有提供的测试点记 00 分。

(b) 单文件分块。 把所有要提交的测试点写进同一个答案文件:每个测试点占用一块,块的第一行是独占一行的块头,形如 # 5(#、一个空格、测试点编号 nn);紧接着是这个测试点的 nn 行数据。块与块之间的顺序任意,块与块之间可以有空行,也可以只写其中一部分测试点。

两种方式下,一个测试点的数据部分格式相同:必须恰好 nn 行,第 ii 行(1≤i≤n1\le i\le n)包含三个十进制实数 xix_i、yiy_i、θi\theta_i,用一个空格分隔,依次表示第 ii 个单位正方形的中心横坐标、中心纵坐标与逆时针旋转角(弧度)。

范围与精度要求:

  • ∣xi∣≤106|x_i|\le 10^6,∣yi∣≤106|y_i|\le 10^6;若某个 ∣xi∣>106|x_i|>10^6 或 ∣yi∣>106|y_i|>10^6,该测试点记 00 分。
  • θi\theta_i 可以是任意实数,评测器不对它的取值范围作限制,而是先把它对 π/2\pi/2 取模后再使用(旋转 π/2\pi/2 的整数倍不改变正方形本身);建议把 θi\theta_i 写在 [0,π/2)[0,\pi/2) 内。
  • 每个数必须至少输出 1010 位小数(推荐 1212 位)。评测器按实数解析、不要求固定位数,可以使用小数形式或科学计数法;但合法性的判定容差是 10−910^{-9} 的绝对量,输出位数不足带来的数值误差由选手自负。
  • 所有数都必须是有限实数:出现 nan、inf 或任何无法解析为实数的记号,该测试点记 00 分。
  • 行内、行首、行尾多余的空格按常规忽略。一个测试点的数据部分必须恰好 nn 行、每行 33 个数:数据部分末尾的空行会被忽略,但中间出现空行会导致行数不符,该测试点记 00 分。
  • 方式 (b) 中,块头 # n 必须独占一行、且只能出现在它所在块的开始处;没有块头的数据视为未提交。

你不需要输出 LL:评测器会按「题目描述」中的公式,从你给出的 xi,yi,θix_i,y_i,\theta_i 自行算出 LL。

提示

合法性如何判定。 评测器先按「题目描述」中的顶点公式算出全部 4n4n 个顶点。对每一对小正方形 (i,j)(i,j),取 ii 的两条边法向与 jj 的两条边法向作为 44 个候选分离轴。把 (i,j)(i,j) 的全部顶点分别投影到某个候选轴上,得到两条投影区间 [a1,a2][a_1,a_2] 与 [b1,b2][b_1,b_2],定义这一对区间在该轴上的重叠长度为

o=min⁡(a2,b2)−max⁡(a1,b1).o=\min(a_2,b_2)-\max(a_1,b_1).

o>0o>0 表示两条区间在该方向上有重叠,o<0o<0 表示两者的距离为 −o-o。只要存在某个候选轴使 o≤10−9o\le 10^{-9},就判定这两个小正方形内部不相交;若 44 个候选轴上都有 o>10−9o>10^{-9},则判为内部重叠、答案非法(也就是把数值重叠深度不超过 10−910^{-9} 的情形视为内部交集面积为 00)。当所有 (n2)\binom{n}{2} 对小正方形都满足该判定时,答案合法;否则该测试点记 00 分。因此边接触、顶点接触都是允许的,但任何"看起来只差一点点"的重叠都可能被判为非法。

评分口径。

记

$$L_{\mathrm{base}}(n)=\left\lceil\sqrt n\right\rceil,$$

它是把 nn 个单位正方形按 $\left\lceil\sqrt n\right\rceil\times\left\lceil\sqrt n\right\rceil$ 的轴对齐网格摆放(每个格子放一个、朝向全部取 00)得到的边长,任何人都能做到。出题组的参考构造为每个测试点给出了参考边长 Lref(n)L_{\mathrm{ref}}(n),这些值列在随题包附带的 data/reference.csv 的 L_ref 列中。

计分集合。 记

$$S=\{\,n:\ 1\le n\le 1000,\ L_{\mathrm{ref}}(n)<L_{\mathrm{base}}(n)\,\},$$

也就是参考构造比网格做得更好的那些测试点(当前 ∣S∣=30|S|=30),它们在 data/reference.csv 中由 status=best-known 标出。

测试点 nn 的得分:

  • 若 n∈Sn\in S:
$$\mathrm{score}(n)=\frac{1000}{|S|}\cdot\mathrm{clamp}\!\left(\frac{L_{\mathrm{base}}(n)-L}{L_{\mathrm{base}}(n)-L_{\mathrm{ref}}(n)},\ 0,\ 1\right),$$

其中 clamp(v,0,1)=min⁡(1,max⁡(0,v))\mathrm{clamp}(v,0,1)=\min\bigl(1,\max(0,v)\bigr) 表示把 vv 截断到区间 [0,1][0,1] 内。当 ∣S∣=30|S|=30 时,每个这样的测试点最多得 1000/30≈33.3331000/30\approx 33.333 分:L≤Lref(n)L\le L_{\mathrm{ref}}(n) 得满分,L≥Lbase(n)L\ge L_{\mathrm{base}}(n) 得 00 分,两者之间按改进的比例线性给分。

  • 若 n∉Sn\notin S:score(n)=0\mathrm{score}(n)=0,无论答案合法与否都不影响分数。这些测试点的网格摆法已经是最优的(全部完全平方数都在其中;n=2,3n=2,3 的最优边长均为 22,经穷举与简单几何论证确认),没有可改进的余地,不必提交。

总分是各测试点得分之和,最多 10001000 分,保留 33 位小数(四舍五入)。因此:完全按网格摆放得 00 分;达到出题组参考构造的水平得 10001000 分。答案非法的测试点记 00 分。

示例答案。 随题附有 data/samples/ 目录,其中 4.out 与 5.out 分别是 n=4n=4 与 n=5n=5 的示例答案文件,同目录的 README.md 说明了它们的摆放方式与按题面口径算出的得分。n=4∉Sn=4\notin S,即使是网格摆法也只有 00 分;n=5∈Sn=5\in S,其 L=2.7071067812L=2.7071067812 已经达到(并略微优于)Lref(5)L_{\mathrm{ref}}(5),得 1000/∣S∣≈33.3331000/|S|\approx 33.333 分。它们分别演示了「不在计分集合里、得 00 分」与「在计分集合里、按相对参考构造的改进比例得分」两种情形。

参考表。 出题组为每个测试点准备的参考构造边长列在随题包附带的 data/reference.csv 中(列:n,L_base,L_ref,status,note)。其中 status 说明该行的结论强度:best-known 表示出题组在该点找到了改进构造(尚未证明最优),grid-fallback 表示出题组在该点只有网格兜底,optimal-proven 表示该点的最优性已被证明;note 是相应的说明文字。你可以据此确认哪些测试点属于计分集合 SS,并对照自己的 LL 与参考构造的差距。

关于评测平台。 本题目在 Hydro 上以「提交答案题(submit_answer)」发布,此时答案文件采用上述方式 (b) 的单文件分块格式(每块以独占一行的 # n 开头)。