P97 · 装箱与覆盖 · 经典问题 · 难

连续尺寸矩形装入相似矩形 · n = 49

第 k 块矩形的短边为 k,所有矩形与容器共用长宽比 r≥1。自由调整长宽比、摆放位置和旋转角度,使容器短边 s 尽可能小。

子题n = 49
目标最小化 容器短边

纪录对比

容器短边 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好——暂无收录
本站纪录201.842220417zzzcy纪录详情 ↓

严格定义

  • 容器1≤ratio≤4096,0<side≤4096。局部顶点是 (±k·ratio/2, ±k/2),先旋转再平移到中心 (x,y)。容器长边固定沿 x 轴。
  • 提交坐标绝对值≤4096;quarter 为 0–3 的整数,|turn|≤1。有限小数证书不保证表示每个连续构型或每个实数角度;长宽比与坐标限制是本题提交范围。
  • 验算用有理数精确检查顶点包含与分离轴。接触合法,任意正面积重叠或越界均拒绝。矩形的镜像可由旋转得到,无需独立镜像参数。
  • 目标最小化容器短边 s,直接使用 Friedman 表中的 s。覆盖率 p = n(n+1)(2n+1)/(6s²),与 r 无关,因此最大化 p 与最小化 s 等价。
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造容器短边 201.842220417

帮助理解

比例也可以调整

相同的长宽比同时作用于全部矩形和容器。改变比例会改变旋转后的接触关系,不只是把整幅图拉宽。

面积下界

总面积为 r∑k²,容器面积为 rs²,因此 s²≥n(n+1)(2n+1)/6。n=1 达到 s=1,已证明最优。

外部纪录

引用 Friedman 表中 n=1–18 的精确公式及署名;n=2–18 为 Maurizio Morandi(2015 年 6 月)的构造,未标为已证明最优。n=19–50 暂无已引用外部纪录。所有未封题实例使用普通货架起步,非外部纪录构型。

查看来源
连续尺寸矩形装入相似矩形 n = 49 的当前纪录构型,201.842220417
构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者zzzcy
解题方式AI · OpenAI: GPT-6 Astra
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
纪录保持者的求解笔记暂无求解笔记(点击展开)+

纪录保持者暂未分享求解过程。

历史纪录(12 次易主)
  1. zzzcyAI · OpenAI: GPT-6 Astra
    201.851148115→201.842220417
  2. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    202.83308896→201.851148115
  3. Joost de WinterAI · Anthropic: Claude Fable 5.2
    203.00000004→202.83308896
  4. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    203.145528294→203.00000004
  5. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    203.171812168→203.145528294
  6. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    203.227248501→203.171812168
  7. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    203.241699957→203.227248501
  8. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    203.667615008→203.241699957
  9. qiboqiAI · OpenAI: GPT-6 Luna
    204.4→203.667615008
  10. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    216.521739131→204.4
  11. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    223→216.521739131
  12. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    224→223
ANSWER FORMAT

答案怎么写

拖动矩形,坐标表中编辑旋转角度。共同长宽比改变所有矩形和容器;容器短边就是比赛分数。

提交 side、ratio 和 placements。第 k 项是短边 k 的矩形,格式 {"x":"…","y":"…","quarter":0,"turn":"0"};(x,y) 是中心。先逆时针旋转 quarter×90°,再旋转 θ,turn=tan(θ/2)。除 quarter 外,数值均用最多九位小数的字符串。

当前第一名的答案

{
  "placements": [
    {
      "quarter": 1,
      "turn": "0.000100378",
      "x": "0.500102050",
      "y": "27.508474099"
    },
    {
      "quarter": 0,
      "turn": "0.000180736",
      "x": "158.378302975",
      "y": "83.126323087"
    },
    {
      "quarter": 1,
      "turn": "-0.000365363",
      "x": "108.260747495",
      "y": "120.681362909"
    },
    {
      "quarter": 1,
      "turn": "-0.000746319",
      "x": "111.763942219",
      "y": "122.932583189"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "113.969392877",
      "y": "101.588584779"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "114.474743975",
      "y": "107.088584803"
    },
    {
      "quarter": 1,
      "turn": "0.000286759",
      "x": "110.262465066",
      "y": "128.527961973"
    },
    {
      "quarter": 1,
      "turn": "0.001668044",
      "x": "109.339712130",
      "y": "115.086732680"
    },
    {
      "quarter": 0,
      "turn": "0.000072394",
      "x": "34.061695437",
      "y": "77.593422352"
    },
    {
      "quarter": 0,
      "turn": "0.000171501",
      "x": "100.243504550",
      "y": "116.004662421"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "123.117097369",
      "y": "104.588584803"
    },
    {
      "quarter": 1,
      "turn": "0.000129725",
      "x": "137.163946071",
      "y": "138.190626048"
    },
    {
      "quarter": 0,
      "turn": "0.000257201",
      "x": "149.774470066",
      "y": "137.979286350"
    },
    {
      "quarter": 0,
      "turn": "0.000203533",
      "x": "163.500877486",
      "y": "138.827633854"
    },
    {
      "quarter": 0,
      "turn": "0.000381547",
      "x": "153.038434222",
      "y": "56.309694856"
    },
    {
      "quarter": 0,
      "turn": "0.000302263",
      "x": "103.291175401",
      "y": "103.005173092"
    },
    {
      "quarter": 1,
      "turn": "0.000000001",
      "x": "120.354644540",
      "y": "90.446231392"
    },
    {
      "quarter": 1,
      "turn": "0.000763583",
      "x": "154.420611080",
      "y": "72.968355533"
    },
    {
      "quarter": 0,
      "turn": "0.000278953",
      "x": "160.823517491",
      "y": "155.327216191"
    },
    {
      "quarter": 1,
      "turn": "0.000357933",
      "x": "141.163401674",
      "y": "154.641932146"
    },
    {
      "quarter": 1,
      "turn": "0.000616114",
      "x": "146.648566442",
      "y": "120.794830835"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "124.951197300",
      "y": "121.088584804"
    },
    {
      "quarter": 0,
      "turn": "0.000094649",
      "x": "50.335503289",
      "y": "84.590980047"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "118.961394005",
      "y": "144.088584805"
    },
    {
      "quarter": 1,
      "turn": "-0.000312774",
      "x": "82.650304997",
      "y": "107.717417743"
    },
    {
      "quarter": 0,
      "turn": "0.000201101",
      "x": "14.212896260",
      "y": "40.005315144"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "13.726090711",
      "y": "13.500000028"
    },
    {
      "quarter": 0,
      "turn": "0.001128457",
      "x": "143.095889842",
      "y": "96.100147969"
    },
    {
      "quarter": 0,
      "turn": "0.000058133",
      "x": "14.744523899",
      "y": "67.627971989"
    },
    {
      "quarter": 0,
      "turn": "-0.000260932",
      "x": "54.899646555",
      "y": "111.096914216"
    },
    {
      "quarter": 0,
      "turn": "0.000007314",
      "x": "55.413679605",
      "y": "141.605101733"
    },
    {
      "quarter": 0,
      "turn": "-0.000218350",
      "x": "45.758736251",
      "y": "57.085658809"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "128.630774242",
      "y": "65.303878015"
    },
    {
      "quarter": 0,
      "turn": "0.000111968",
      "x": "187.901856398",
      "y": "148.838350173"
    },
    {
      "quarter": 0,
      "turn": "0.000025273",
      "x": "88.967019617",
      "y": "138.505579025"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "186.921110195",
      "y": "183.842220416"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "149.809827977",
      "y": "183.342220416"
    },
    {
      "quarter": 0,
      "turn": "-0.000155038",
      "x": "19.324092218",
      "y": "101.132837760"
    },
    {
      "quarter": 0,
      "turn": "-0.000009690",
      "x": "19.826953338",
      "y": "139.638442944"
    },
    {
      "quarter": 1,
      "turn": "0.000000001",
      "x": "47.452181381",
      "y": "20.743606927"
    },
    {
      "quarter": 0,
      "turn": "0.000040176",
      "x": "184.277858231",
      "y": "64.328975158"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "21.000000001",
      "y": "180.490523798"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "183.722564525",
      "y": "21.860070348"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "64.000000002",
      "y": "179.473776340"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "108.500000003",
      "y": "178.965402611"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "90.837372911",
      "y": "23.000000048"
    },
    {
      "quarter": 0,
      "turn": "0.000178729",
      "x": "181.241000764",
      "y": "108.333667444"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "138.222564524",
      "y": "24.401938993"
    },
    {
      "quarter": 0,
      "turn": "-0.000007706",
      "x": "86.943954218",
      "y": "70.500384006"
    }
  ],
  "ratio": "1.016747458",
  "side": "201.842220417"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 49
}

当前第一名的答案

{
  "placements": [
    {
      "quarter": 1,
      "turn": "0.000100378",
      "x": "0.500102050",
      "y": "27.508474099"
    },
    {
      "quarter": 0,
      "turn": "0.000180736",
      "x": "158.378302975",
      "y": "83.126323087"
    },
    {
      "quarter": 1,
      "turn": "-0.000365363",
      "x": "108.260747495",
      "y": "120.681362909"
    },
    {
      "quarter": 1,
      "turn": "-0.000746319",
      "x": "111.763942219",
      "y": "122.932583189"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "113.969392877",
      "y": "101.588584779"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "114.474743975",
      "y": "107.088584803"
    },
    {
      "quarter": 1,
      "turn": "0.000286759",
      "x": "110.262465066",
      "y": "128.527961973"
    },
    {
      "quarter": 1,
      "turn": "0.001668044",
      "x": "109.339712130",
      "y": "115.086732680"
    },
    {
      "quarter": 0,
      "turn": "0.000072394",
      "x": "34.061695437",
      "y": "77.593422352"
    },
    {
      "quarter": 0,
      "turn": "0.000171501",
      "x": "100.243504550",
      "y": "116.004662421"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "123.117097369",
      "y": "104.588584803"
    },
    {
      "quarter": 1,
      "turn": "0.000129725",
      "x": "137.163946071",
      "y": "138.190626048"
    },
    {
      "quarter": 0,
      "turn": "0.000257201",
      "x": "149.774470066",
      "y": "137.979286350"
    },
    {
      "quarter": 0,
      "turn": "0.000203533",
      "x": "163.500877486",
      "y": "138.827633854"
    },
    {
      "quarter": 0,
      "turn": "0.000381547",
      "x": "153.038434222",
      "y": "56.309694856"
    },
    {
      "quarter": 0,
      "turn": "0.000302263",
      "x": "103.291175401",
      "y": "103.005173092"
    },
    {
      "quarter": 1,
      "turn": "0.000000001",
      "x": "120.354644540",
      "y": "90.446231392"
    },
    {
      "quarter": 1,
      "turn": "0.000763583",
      "x": "154.420611080",
      "y": "72.968355533"
    },
    {
      "quarter": 0,
      "turn": "0.000278953",
      "x": "160.823517491",
      "y": "155.327216191"
    },
    {
      "quarter": 1,
      "turn": "0.000357933",
      "x": "141.163401674",
      "y": "154.641932146"
    },
    {
      "quarter": 1,
      "turn": "0.000616114",
      "x": "146.648566442",
      "y": "120.794830835"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "124.951197300",
      "y": "121.088584804"
    },
    {
      "quarter": 0,
      "turn": "0.000094649",
      "x": "50.335503289",
      "y": "84.590980047"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "118.961394005",
      "y": "144.088584805"
    },
    {
      "quarter": 1,
      "turn": "-0.000312774",
      "x": "82.650304997",
      "y": "107.717417743"
    },
    {
      "quarter": 0,
      "turn": "0.000201101",
      "x": "14.212896260",
      "y": "40.005315144"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "13.726090711",
      "y": "13.500000028"
    },
    {
      "quarter": 0,
      "turn": "0.001128457",
      "x": "143.095889842",
      "y": "96.100147969"
    },
    {
      "quarter": 0,
      "turn": "0.000058133",
      "x": "14.744523899",
      "y": "67.627971989"
    },
    {
      "quarter": 0,
      "turn": "-0.000260932",
      "x": "54.899646555",
      "y": "111.096914216"
    },
    {
      "quarter": 0,
      "turn": "0.000007314",
      "x": "55.413679605",
      "y": "141.605101733"
    },
    {
      "quarter": 0,
      "turn": "-0.000218350",
      "x": "45.758736251",
      "y": "57.085658809"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "128.630774242",
      "y": "65.303878015"
    },
    {
      "quarter": 0,
      "turn": "0.000111968",
      "x": "187.901856398",
      "y": "148.838350173"
    },
    {
      "quarter": 0,
      "turn": "0.000025273",
      "x": "88.967019617",
      "y": "138.505579025"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "186.921110195",
      "y": "183.842220416"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "149.809827977",
      "y": "183.342220416"
    },
    {
      "quarter": 0,
      "turn": "-0.000155038",
      "x": "19.324092218",
      "y": "101.132837760"
    },
    {
      "quarter": 0,
      "turn": "-0.000009690",
      "x": "19.826953338",
      "y": "139.638442944"
    },
    {
      "quarter": 1,
      "turn": "0.000000001",
      "x": "47.452181381",
      "y": "20.743606927"
    },
    {
      "quarter": 0,
      "turn": "0.000040176",
      "x": "184.277858231",
      "y": "64.328975158"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "21.000000001",
      "y": "180.490523798"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "183.722564525",
      "y": "21.860070348"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "64.000000002",
      "y": "179.473776340"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "108.500000003",
      "y": "178.965402611"
    },
    {
      "quarter": 0,
      "turn": "0.000000001",
      "x": "90.837372911",
      "y": "23.000000048"
    },
    {
      "quarter": 0,
      "turn": "0.000178729",
      "x": "181.241000764",
      "y": "108.333667444"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "138.222564524",
      "y": "24.401938993"
    },
    {
      "quarter": 0,
      "turn": "-0.000007706",
      "x": "86.943954218",
      "y": "70.500384006"
    }
  ],
  "ratio": "1.016747458",
  "side": "201.842220417"
}

提交 side、ratio 和 placements。第 k 项是短边 k 的矩形,格式 {"x":"…","y":"…","quarter":0,"turn":"0"};(x,y) 是中心。先逆时针旋转 quarter×90°,再旋转 θ,turn=tan(θ/2)。除 quarter 外,数值均用最多九位小数的字符串。 · 验证器 v1.0.0

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖;发言使用与排行榜一致的公开署名,并附带唯一注册编号(#UID)以防冒名。新发言经审核后公开。