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

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

给定条带高度 H、若干零件多边形及每种的需求数量，把全部零件放入条带，使所有顶点中最大的 x 坐标 L 最小。零件只能平移并转 0°、90°、180° 或 270°，可以接触但内部不能重叠，也不能越出条带。

子题GARDEYN9 · 47 件，各不相同

目标最小化占用长度

严格定义

容器闭区域 {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.770

帮助理解

为什么是这三个实例

GARDEYN 系列来自服装裁剪和 DTF 打印的真实订单：轮廓凹凸不平、不对称，重复件不多。GARDEYN1 是 10 种零件各 5 份，GARDEYN2 是 50 件互不相同的裁片，GARDEYN9 是 47 件互不相同的打印图案、条带只有 44 高。三个子题各自完整，不能把一个的答案套到另一个上。

只准转直角

文献里的排样求解器通常允许连续旋转，但连续角度的坐标带着三角函数，无法精确验证。本题只允许 0°、90°、180°、270°，一切坐标保持有理数，验证器可以毫无容差地判定接触与重叠。这也意味着本题和允许自由旋转的公开成绩不完全可比。

前沿在哪里

没有外部纪录。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，原始十进制坐标未经浮点截断；每个子题的输入哈希与来源链接可在编辑器中下载。

查看来源

当前第一名

65.769735999999999

占用长度

答案来源MinMax Arena

解题方式本站离线搜索

挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享证明或思路，审核采纳后可获得证明分。

纪录保持者的求解笔记暂无求解笔记（点击展开）＋

纪录保持者还没有分享求解过程。

ANSWER FORMAT

答案怎么写

条带 {x ≥ 0, 0 ≤ y ≤ H}，H 是材料宽度（画成竖直方向），材料沿 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.536922",
      "y": "43.833246"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.310434",
      "y": "14.081869"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.936388",
      "y": "22.015273"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.73577",
      "y": "42.487798"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "64.106534",
      "y": "8.857996"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.303802",
      "y": "26.59188"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.079309",
      "y": "42.308482"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "14.254236",
      "y": "17.697975"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.633194",
      "y": "32.989586"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "49.140784",
      "y": "35.675826"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.769226",
      "y": "32.632156"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12339478",
      "y": "14.889212"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762715",
      "y": "18.880486"
    },
    {
      "rotation": 90,
      "typeId": "t20",
      "x": "10.523917",
      "y": "27.146084"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.447822",
      "y": "36.31345"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.171911",
      "y": "20.259862"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.976716",
      "y": "0.12277269"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.552142",
      "y": "43.86438"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12577166",
      "y": "33.646435"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.330047",
      "y": "30.869584"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.173116",
      "y": "0.13359737"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.360727",
      "y": "28.909076"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.3599937",
      "y": "34.622522"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.216326",
      "y": "43.865227"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.429454",
      "y": "0.20132125"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.346242",
      "y": "-0.68400956"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.649913",
      "y": "13.506231"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.865562",
      "y": "28.06545"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.966038",
      "y": "21.293765"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.963012",
      "y": "36.3955"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "42.062806",
      "y": "36.838852"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.737913",
      "y": "18.830784"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.396311",
      "y": "14.067703"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.141184",
      "y": "40.519108"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.626939",
      "y": "26.912271"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.972948",
      "y": "19.10906"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.640816",
      "y": "13.829794"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.960554",
      "y": "9.410119"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13183697",
      "y": "43.873856"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "33.085811",
      "y": "28.146021"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "56.082034",
      "y": "29.164982"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161658",
      "y": "14.632311"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.385334",
      "y": "35.515647"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.206991",
      "y": "43.874355"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.167263",
      "y": "7.9403256"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.961679",
      "y": "11.781264"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.18915",
      "y": "18.891047"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "case": "gardeyn9"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn9-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "49.536922",
      "y": "43.833246"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.310434",
      "y": "14.081869"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.936388",
      "y": "22.015273"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.73577",
      "y": "42.487798"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "64.106534",
      "y": "8.857996"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.303802",
      "y": "26.59188"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.079309",
      "y": "42.308482"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "14.254236",
      "y": "17.697975"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.633194",
      "y": "32.989586"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "49.140784",
      "y": "35.675826"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.769226",
      "y": "32.632156"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12339478",
      "y": "14.889212"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762715",
      "y": "18.880486"
    },
    {
      "rotation": 90,
      "typeId": "t20",
      "x": "10.523917",
      "y": "27.146084"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.447822",
      "y": "36.31345"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.171911",
      "y": "20.259862"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.976716",
      "y": "0.12277269"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.552142",
      "y": "43.86438"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12577166",
      "y": "33.646435"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.330047",
      "y": "30.869584"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.173116",
      "y": "0.13359737"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.360727",
      "y": "28.909076"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.3599937",
      "y": "34.622522"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.216326",
      "y": "43.865227"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.429454",
      "y": "0.20132125"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.346242",
      "y": "-0.68400956"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.649913",
      "y": "13.506231"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.865562",
      "y": "28.06545"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.966038",
      "y": "21.293765"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.963012",
      "y": "36.3955"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "42.062806",
      "y": "36.838852"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.737913",
      "y": "18.830784"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.396311",
      "y": "14.067703"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.141184",
      "y": "40.519108"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.626939",
      "y": "26.912271"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.972948",
      "y": "19.10906"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.640816",
      "y": "13.829794"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.960554",
      "y": "9.410119"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13183697",
      "y": "43.873856"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "33.085811",
      "y": "28.146021"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "56.082034",
      "y": "29.164982"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161658",
      "y": "14.632311"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.385334",
      "y": "35.515647"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.206991",
      "y": "43.874355"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.167263",
      "y": "7.9403256"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.961679",
      "y": "11.781264"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.18915",
      "y": "18.891047"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。所有登录用户都可以发帖；发言公开署名，与纪录使用同一个名字，署名后的 #编号是账号注册序号，冒不了名。新发言经自动审核后公开。

问题大草NUE_13#310 条回复53 分钟前