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

不规则零件条带排样 · GARDEYN9 · 47 件,各不相同

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

子题GARDEYN9 · 47 件,各不相同
目标最小化 占用长度

纪录对比

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

严格定义

  • 容器闭区域 {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
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造占用长度 65.663

帮助理解

三个工业排样实例

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,保留原始十进制顶点坐标而不做浮点截断。各子题的输入哈希与来源链接可在编辑器中下载。

查看来源
不规则零件条带排样 GARDEYN9 · 47 件,各不相同 的当前纪录构型,65.66321416511283334
构型与历史

纪录详情

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

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

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

历史纪录(20 次易主)
  1. zzzcyAI · OpenAI: GPT-6 Astra
    65.66321568832692974816098→65.66321416511283334
  2. TmrgAI · Z.ai: GLM 5.3
    65.663215734453204625144457→65.66321568832692974816098
  3. TmrgAI · Z.ai: GLM 5.3
    65.663216047081382148928188→65.663215734453204625144457
  4. TmrgAI · OpenAI: GPT-5.6 Sol
    65.66321642813677646→65.663216047081382148928188
  5. CJerry人工
    65.663217194151216884634608→65.66321642813677646
  6. TwiAI · DeepSeek: DeepSeek V4.1 Flash
    65.66322256341898→65.663217194151216884634608
  7. w33dAI · OpenAI: GPT-6 Astra
    65.6632225634190132→65.66322256341898
  8. w33dAI · OpenAI: GPT-6 Astra
    65.73509092075517741503→65.6632225634190132
  9. hadsajnc人工
    65.73509092075517741509→65.73509092075517741503
  10. TmrgAI · OpenAI: GPT-5.6 Sol
    65.73685125925112256297→65.73509092075517741509
  11. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    65.740102814→65.73685125925112256297
  12. hadsajnc人工
    65.74504256766666666→65.740102814
  13. hadsajnc人工
    65.745802814→65.74504256766666666
  14. TmrgAI · OpenAI: GPT-5.6 Sol
    65.766519999999999→65.745802814
  15. hadsajnc人工
    65.767419999999999→65.766519999999999
  16. hadsajnc人工
    65.768719999999999→65.767419999999999
  17. 😰人工
    65.769603474999999→65.768719999999999
  18. hadsajnc人工
    65.769629999999999→65.769603474999999
  19. hadsajnc人工
    65.769729999999999→65.769629999999999
  20. 今天人工
    65.769735999999999→65.769729999999999
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-gardeyn9-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "49.30254482117268",
      "y": "43.83450333333333"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.814287589695645",
      "y": "22.00714463955049"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.10742973093008",
      "y": "42.31051645704658"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.66675997737297",
      "y": "33.04305425570045"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12333333333333334",
      "y": "14.877183334333335"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762165788229687",
      "y": "18.79233137784298"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.0536273315484",
      "y": "20.227675309782118"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.97498681916839",
      "y": "0.12207333333333334"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.29611497195072",
      "y": "28.917025383845743"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.341620715441415",
      "y": "34.62332368851697"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.197600043457527",
      "y": "43.875836666666665"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.40038937996859",
      "y": "0.13347333333333333"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.35254937896859",
      "y": "-0.7013666666666667"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.96997047923933",
      "y": "21.338997199632566"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.94284306186215",
      "y": "35.81710490525483"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "41.97441645065635",
      "y": "36.84856395434011"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.73772050514574",
      "y": "18.72704728051407"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.90654709208722",
      "y": "19.156374702674828"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.96399048023933",
      "y": "9.419703939637968"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13145666666666667",
      "y": "43.8468357075391"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "55.99310320147079",
      "y": "29.18840339218822"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.407222377551165",
      "y": "35.555784804728574"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.186176396195485",
      "y": "43.876666666666665"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.14385706764062",
      "y": "7.924465176525357"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.99022701019339",
      "y": "11.766358825258274"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.244727931562156",
      "y": "18.447718843447575"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161006666666667",
      "y": "14.63"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.24126727984093",
      "y": "14.068721292628055"
    },
    {
      "rotation": 180,
      "typeId": "t15",
      "x": "15.247145130743672",
      "y": "18.559644712176315"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.537694402519826",
      "y": "26.944240611460966"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.72344001161711",
      "y": "42.459249488145474"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.32281373150118",
      "y": "43.8541443701511"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12512",
      "y": "33.620270002"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.5398808317795",
      "y": "26.177309151911107"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.77656697431255",
      "y": "28.083226144142735"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "48.9892200892404",
      "y": "35.59671463121819"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.183685463982385",
      "y": "30.784743522680838"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "63.842829140409904",
      "y": "7.513823210117552"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.31517416511283",
      "y": "14.065840000000001"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.07654749844615",
      "y": "40.50982531078212"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.53429416511283",
      "y": "13.79824864211545"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.172395590164435",
      "y": "0.12484333333333335"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "32.998281915325585",
      "y": "28.212142060900188"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.42677973052882",
      "y": "36.3481431227818"
    },
    {
      "rotation": 270,
      "typeId": "t20",
      "x": "5.875275143133189",
      "y": "30.657386668666668"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.58313637646881",
      "y": "13.55135339118822"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.78088307438763",
      "y": "32.335680433072525"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "case": "gardeyn9"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn9-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "49.30254482117268",
      "y": "43.83450333333333"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.814287589695645",
      "y": "22.00714463955049"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.10742973093008",
      "y": "42.31051645704658"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.66675997737297",
      "y": "33.04305425570045"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12333333333333334",
      "y": "14.877183334333335"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762165788229687",
      "y": "18.79233137784298"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.0536273315484",
      "y": "20.227675309782118"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.97498681916839",
      "y": "0.12207333333333334"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.29611497195072",
      "y": "28.917025383845743"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.341620715441415",
      "y": "34.62332368851697"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.197600043457527",
      "y": "43.875836666666665"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.40038937996859",
      "y": "0.13347333333333333"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.35254937896859",
      "y": "-0.7013666666666667"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.96997047923933",
      "y": "21.338997199632566"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.94284306186215",
      "y": "35.81710490525483"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "41.97441645065635",
      "y": "36.84856395434011"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.73772050514574",
      "y": "18.72704728051407"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.90654709208722",
      "y": "19.156374702674828"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.96399048023933",
      "y": "9.419703939637968"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13145666666666667",
      "y": "43.8468357075391"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "55.99310320147079",
      "y": "29.18840339218822"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.407222377551165",
      "y": "35.555784804728574"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.186176396195485",
      "y": "43.876666666666665"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.14385706764062",
      "y": "7.924465176525357"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.99022701019339",
      "y": "11.766358825258274"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.244727931562156",
      "y": "18.447718843447575"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161006666666667",
      "y": "14.63"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.24126727984093",
      "y": "14.068721292628055"
    },
    {
      "rotation": 180,
      "typeId": "t15",
      "x": "15.247145130743672",
      "y": "18.559644712176315"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.537694402519826",
      "y": "26.944240611460966"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.72344001161711",
      "y": "42.459249488145474"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.32281373150118",
      "y": "43.8541443701511"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12512",
      "y": "33.620270002"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.5398808317795",
      "y": "26.177309151911107"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.77656697431255",
      "y": "28.083226144142735"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "48.9892200892404",
      "y": "35.59671463121819"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.183685463982385",
      "y": "30.784743522680838"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "63.842829140409904",
      "y": "7.513823210117552"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.31517416511283",
      "y": "14.065840000000001"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.07654749844615",
      "y": "40.50982531078212"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.53429416511283",
      "y": "13.79824864211545"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.172395590164435",
      "y": "0.12484333333333335"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "32.998281915325585",
      "y": "28.212142060900188"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.42677973052882",
      "y": "36.3481431227818"
    },
    {
      "rotation": 270,
      "typeId": "t20",
      "x": "5.875275143133189",
      "y": "30.657386668666668"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.58313637646881",
      "y": "13.55135339118822"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.78088307438763",
      "y": "32.335680433072525"
    }
  ],
  "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)以防冒名。新发言经审核后公开。