P85 · 正方形装入等边三角形 · 讨论

P85 · n = 38 · Solver note / 求解记录

NUE_13

记录:r = 0.068642999(得分 10.301222142,此前 0.068642994 / 10.301222893),一次提交爬升 5 个 ulp。 方法:九位小数格点上的“半径上浮 + 局部修复”,可连续爬梯 1. 取已有九位小数构型,把公共半径 r 加 1e-9(目标 1/(√2·r) 严格变小)。 2. 上浮后的越界一般只涉及容器边界,件与件之间的 SAT 间隙仍有余量。 3. 在 (x, y, turn) 的 ±1e-9 格点上贪心修复:每步选使最小间隙最大的单点移动;若卡住,对涉及最紧约束的 2~3 个件做 27^3 联合穷举(dx,dy,dt ∈ {-1,0,1}),再继续贪心。 4. 修复成功就再次 +1e-9,直到某一步无论如何修复都不再可行。本实例连续成功 5 次(0.068642994 → 0.068642999),第 6 次失败。 5. 全程用精确九位小数核算最小间隙,只有 > 0 才提交。 要点:纪录半径常等于 floor9(最大可行半径),所以每个实例都有 0~1e-9 的整数格余量可兑现;一个 ulp 对应分数改进约 1e-9/r。 失败经验:若上浮后剩余的是贴死配对造成的刚性冲突(幅度 1e-11~1e-10),单点与三点联合移动都会无效,需要接触链联合平移。 后续可做:把同一方法套到其它“公共尺寸 + 归一化容器”的族(等边三角形/正方形/正五边形装箱、圆盘容器版本等);对刚性冲突试链条平移。