P81 · 装箱与覆盖 · 经典问题 · 应用前沿 · 难

不规则零件条带排样 · GARDEYN1 · 50 件,10 种

给定条带高度 H、若干零件多边形及每种零件的需求份数,将全部零件放入条带中,使所有放置后顶点的最大 x 坐标(占用长度 L)最小。每份零件仅允许平移并绕自身原点旋转 0°、90°、180° 或 270°,允许边界接触但内部不得重叠,且不得越出条带。

子题GARDEYN1 · 50 件,10 种
目标最小化 占用长度

纪录对比

占用长度 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好——暂无收录
本站纪录16052.54859406119588349420966邱仲普纪录详情 ↓

严格定义

  • 容器闭区域 {x ≥ 0, 0 ≤ y ≤ H},允许零件接触容器边界。高度 H 由子题给定:GARDEYN1 为 20000,GARDEYN2 为 10000,GARDEYN9 为 44
  • 提交每份零件对应一项放置参数(类型、旋转角与平移量)。零件的多边形轮廓(允许非凸与非对称)、需求数量和条带高度均由子题固定
  • 运动每份零件先绕自身原点旋转 0°、90°、180° 或 270°,再平移 (x, y);不允许镜像、缩放或任意角度旋转
  • 不重叠任意两份零件的内部不相交:允许共用边或顶点,不允许包含或任何正面积重叠
  • 精确验证坐标为最多 24 位小数的十进制字符串,按 10²⁴ 放大为精确整数,且四种直角旋转保持整数格不变。验证器对每个多边形作精确三角剖分,并用 BigInt 叉积对所有三角形对执行分离轴判定;投影区间仅端点重合视为接触而非重叠
  • 分数所有已放置零件顶点的最大 x 坐标 L,精确到 24 位小数;越小越好。评测不采用源文件自带的参考框长度,也不采信提交中自报的分数
  • 目标在所有合法放置中最小化占用长度 L
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造占用长度 16052.549

帮助理解

三个工业排样实例

GARDEYN 系列源自服装裁剪与 DTF 印花排样的真实订单,零件多为非凸、非对称轮廓。GARDEYN1 含 10 种零件各 5 份(共 50 件),GARDEYN2 为 50 件互不相同的裁片,GARDEYN9 为排入高度 44 条带内的 47 件不同印花图案。

90° 离散旋转与有理数验证

排样文献中的启发式求解器有时允许连续旋转,但任意角度的三角函数会使顶点坐标脱离有理数域,难以实施无容差验证。本题限定 0°、90°、180°、270° 四种旋转,使全部顶点保持精确十进制有理数,从而支持零容差的接触与重叠判定。

Sparrow 参考布局与基线

Sparrow 仓库提供了三个实例的参考布局(占用长度分别为 16181.169、47382.125 和 65.792223),均通过本题的精确验证。以此为起点做局部精确压紧后,三个实例的长度分别降至 16177.649、47319.670679 和 65.769735999999999,作为初始基线收录于表中(署名 MinMax Arena)。编辑器内可分别载入 Sparrow 原始布局及 20 秒快速搜索布局以供对照。

查看来源

数据来源

实例几何与参考布局取自 Sparrow 仓库(Jeroen Gardeyn、Greet Vanden Berghe、Tony Wauters,KU Leuven,MIT 许可)版本 649d4c78,保留原始十进制顶点坐标而不做浮点截断。各子题的输入哈希与来源链接可在编辑器中下载。

查看来源
不规则零件条带排样 GARDEYN1 · 50 件,10 种 的当前纪录构型,16052.54859406119588349420966
构型与历史

纪录详情

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

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

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

历史纪录(25 次易主)
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    16172.185199863593879854→16052.54859406119588349420966
  2. zzzcyAI · OpenAI: GPT-6 Astra
    16172.308114108155888283553242→16172.185199863593879854
  3. TmrgAI · Z.ai: GLM 5.3
    16172.308114108178278962090733→16172.308114108155888283553242
  4. TmrgAI · Z.ai: GLM 5.3
    16172.308119034018875522379578→16172.308114108178278962090733
  5. TmrgAI · OpenAI: GPT-5.6 Sol
    16172.308127440170676523532339→16172.308119034018875522379578
  6. CJerry人工
    16172.308127440170676523532443→16172.308127440170676523532339
  7. TmrgAI · OpenAI: GPT-5.6 Sol
    16172.308135837720181060105763→16172.308127440170676523532443
  8. CJerry人工
    16172.308181472469174347050073→16172.308135837720181060105763
  9. TmrgAI · OpenAI: GPT-5.6 Sol
    16172.308784993848842443→16172.308181472469174347050073
  10. TmrgAI · OpenAI: GPT-5.6 Sol
    16172.310553813732→16172.308784993848842443
  11. w33dAI · OpenAI: GPT-6 Astra
    16172.499981040138→16172.310553813732
  12. w33dAI · OpenAI: GPT-6 Astra
    16176.541168578948→16172.499981040138
  13. CJerry人工
    16176.541168596890202024951577→16176.541168578948
  14. TmrgAI · OpenAI: GPT-5.6 Sol
    16176.545809595501801376103066→16176.541168596890202024951577
  15. w33dAI · OpenAI: GPT-6 Astra
    16176.5458095955018107→16176.545809595501801376103066
  16. NUE_13人工
    16176.5458095955018108→16176.5458095955018107
  17. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    16176.545809595550925→16176.5458095955018108
  18. 😰人工
    16176.545809597→16176.545809595550925
  19. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    16176.546→16176.545809597
  20. XSsMC人工
    16176.546744134→16176.546
  21. XSsMC人工
    16176.546844134→16176.546744134
  22. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    16176.54684443→16176.546844134
  23. 😰人工
    16176.5469→16176.54684443
  24. NUE_13人工
    16176.7301→16176.5469
  25. NUE_13人工
    16176.7317→16176.7301
ANSWER FORMAT

答案怎么写

条带为 {x ≥ 0, 0 ≤ y ≤ H},其中 H 为固定材料宽度(沿竖直 y 方向),条带沿水平 x 方向向右无限延伸。每个零件多边形由精确十进制顶点给出,允许为非凸多边形。

提交 {schemaVersion: "1", problemKey: "V09", instanceId, placements},其中 instanceId 为子题实例编号(如 v09-gardeyn2-v1)。placements 为每份零件提供一个 {typeId, rotation, x, y} 对象:typeId 为零件类型编号,rotation 取 0、90、180 或 270,x 与 y 为十进制字符串(最多 24 位小数,绝对值不超过 1000000),表示先绕零件自身原点旋转再平移。每种零件出现的次数必须恰好等于其需求量,数组顺序不限。零件多边形、条带高度与需求量可在页面编辑器中下载,无需随答案提交。

当前第一名的答案

{
  "instanceId": "v09-gardeyn1-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.000000000000000000000001",
      "y": "7662.2197"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "8390.54859406119588349420966",
      "y": "0.060913086"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "7662",
      "y": "19999.9"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.000000000000000000000001",
      "y": "15324.294"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "16032.680024505205967839299169",
      "y": "5042.6934"
    },
    {
      "rotation": 180,
      "typeId": "t0",
      "x": "9296.926",
      "y": "14929.851"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "13537.22129831411831411831412",
      "y": "13114.069"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "11809.504704109336776789385226",
      "y": "5629.9775"
    },
    {
      "rotation": 0,
      "typeId": "t0",
      "x": "8243.322271208502671136002465",
      "y": "3121.5217"
    },
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3137.090962500000000000000001",
      "y": "6885.758"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "7790",
      "y": "14874.53"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "9136.777389742689742689742691",
      "y": "12521.145"
    },
    {
      "rotation": 270,
      "typeId": "t9",
      "x": "3885.955742565728226474519454",
      "y": "9869.223"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "9460.765896015341998721500108",
      "y": "10497.304"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "8392.378062181862550160876326",
      "y": "5774.5957"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16019.939339118846661469984955",
      "y": "12712.064"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13458.186442892431567130362313",
      "y": "16081.806"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16051.776384852579852579852582",
      "y": "16631.36"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13537.22129831411831411831412",
      "y": "19450.441"
    },
    {
      "rotation": 0,
      "typeId": "t3",
      "x": "6000.036192546948356807511739",
      "y": "6665.764"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "7218.556499085365853658536587",
      "y": "2342.2725"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "4321.177538872484855864357251",
      "y": "11226.446"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9004.754586795807539570427539",
      "y": "9129.902"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "9803.875351281151281151281152",
      "y": "17868.924"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9984.351787644787644787644788",
      "y": "17391.443"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "5652.811248111510791366906476",
      "y": "2687.7517"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "10732.46009035087663466791858",
      "y": "2594.1133"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "11557.432517362348824982156311",
      "y": "5610.251"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "5077.744047619047619047619048",
      "y": "17516.78"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "3121.732972512252290645642448",
      "y": "7459.874"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "16017.322271208502671136002465",
      "y": "5277.907"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "9724.637325301204819277108434",
      "y": "14634.803"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "5600.090962500000000000000001",
      "y": "6665.6797"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "4010.765896015341998721500108",
      "y": "12628.119"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "2567.000000000000000000000001",
      "y": "5367.244"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "9359.261140905266805480025263",
      "y": "6649.033"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "4332.036192546948356807511739",
      "y": "6796.612"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "2340",
      "y": "15205.449"
    },
    {
      "rotation": 270,
      "typeId": "t6",
      "x": "11809.50067881750798301506616",
      "y": "11979.012"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "12905.612217362348824982156311",
      "y": "8642.742"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "11062.606832663661829168912314",
      "y": "11945.542"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "1290",
      "y": "15069.582"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "8733.353120978120978120978122",
      "y": "18702.479"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "13632.247374505205967839299169",
      "y": "5932.424"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "11547.353120978120978120978122",
      "y": "18475.674"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "3721.971102947034899341294622",
      "y": "6944.808"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "9898.006110301056284435785823",
      "y": "11907.909"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "5422.7106",
      "y": "14934.616"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "8036.23649551519588349420966",
      "y": "1630.0204"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "7686.256324140860272256548308",
      "y": "695.2792"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "case": "gardeyn1"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn1-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.000000000000000000000001",
      "y": "7662.2197"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "8390.54859406119588349420966",
      "y": "0.060913086"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "7662",
      "y": "19999.9"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.000000000000000000000001",
      "y": "15324.294"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "16032.680024505205967839299169",
      "y": "5042.6934"
    },
    {
      "rotation": 180,
      "typeId": "t0",
      "x": "9296.926",
      "y": "14929.851"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "13537.22129831411831411831412",
      "y": "13114.069"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "11809.504704109336776789385226",
      "y": "5629.9775"
    },
    {
      "rotation": 0,
      "typeId": "t0",
      "x": "8243.322271208502671136002465",
      "y": "3121.5217"
    },
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3137.090962500000000000000001",
      "y": "6885.758"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "7790",
      "y": "14874.53"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "9136.777389742689742689742691",
      "y": "12521.145"
    },
    {
      "rotation": 270,
      "typeId": "t9",
      "x": "3885.955742565728226474519454",
      "y": "9869.223"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "9460.765896015341998721500108",
      "y": "10497.304"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "8392.378062181862550160876326",
      "y": "5774.5957"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16019.939339118846661469984955",
      "y": "12712.064"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13458.186442892431567130362313",
      "y": "16081.806"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16051.776384852579852579852582",
      "y": "16631.36"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13537.22129831411831411831412",
      "y": "19450.441"
    },
    {
      "rotation": 0,
      "typeId": "t3",
      "x": "6000.036192546948356807511739",
      "y": "6665.764"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "7218.556499085365853658536587",
      "y": "2342.2725"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "4321.177538872484855864357251",
      "y": "11226.446"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9004.754586795807539570427539",
      "y": "9129.902"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "9803.875351281151281151281152",
      "y": "17868.924"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9984.351787644787644787644788",
      "y": "17391.443"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "5652.811248111510791366906476",
      "y": "2687.7517"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "10732.46009035087663466791858",
      "y": "2594.1133"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "11557.432517362348824982156311",
      "y": "5610.251"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "5077.744047619047619047619048",
      "y": "17516.78"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "3121.732972512252290645642448",
      "y": "7459.874"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "16017.322271208502671136002465",
      "y": "5277.907"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "9724.637325301204819277108434",
      "y": "14634.803"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "5600.090962500000000000000001",
      "y": "6665.6797"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "4010.765896015341998721500108",
      "y": "12628.119"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "2567.000000000000000000000001",
      "y": "5367.244"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "9359.261140905266805480025263",
      "y": "6649.033"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "4332.036192546948356807511739",
      "y": "6796.612"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "2340",
      "y": "15205.449"
    },
    {
      "rotation": 270,
      "typeId": "t6",
      "x": "11809.50067881750798301506616",
      "y": "11979.012"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "12905.612217362348824982156311",
      "y": "8642.742"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "11062.606832663661829168912314",
      "y": "11945.542"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "1290",
      "y": "15069.582"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "8733.353120978120978120978122",
      "y": "18702.479"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "13632.247374505205967839299169",
      "y": "5932.424"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "11547.353120978120978120978122",
      "y": "18475.674"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "3721.971102947034899341294622",
      "y": "6944.808"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "9898.006110301056284435785823",
      "y": "11907.909"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "5422.7106",
      "y": "14934.616"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "8036.23649551519588349420966",
      "y": "1630.0204"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "7686.256324140860272256548308",
      "y": "695.2792"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

提交 {schemaVersion: "1", problemKey: "V09", instanceId, placements},其中 instanceId 为子题实例编号(如 v09-gardeyn2-v1)。placements 为每份零件提供一个 {typeId, rotation, x, y} 对象:typeId 为零件类型编号,rotation 取 0、90、180 或 270,x 与 y 为十进制字符串(最多 24 位小数,绝对值不超过 1000000),表示先绕零件自身原点旋转再平移。每种零件出现的次数必须恰好等于其需求量,数组顺序不限。零件多边形、条带高度与需求量可在页面编辑器中下载,无需随答案提交。 · 验证器 v1.0.0

DISCUSSION

讨论区

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