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

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

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

子题GARDEYN1 · 50 件，10 种

目标最小化占用长度

严格定义

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

放大来摆，然后提交 ↗

已验证构造占用长度 16176.892

帮助理解

为什么是这三个实例

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

查看来源

当前第一名

16176.8923

占用长度

纪录保持者NUE_13

解题方式人工

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

纪录保持者的求解笔记公开方法与可复现线索（点击展开）＋

微调，目前长度由零件29控制，成功缩小0.4

在讨论区查看与回复 →

历史纪录（2 次易主）

NUE_13人工
16177.209→16176.8923
2026-09-13
NUE_13人工
16177.649→16177.209
2026-09-13

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-gardeyn1-v1",
  "placements": [
    {
      "rotation": 0,
      "typeId": "t0",
      "x": "8402.8923",
      "y": "3143.713"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "7512.8923",
      "y": "323.3301"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "11830.55",
      "y": "5684.8635"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "13613.341",
      "y": "13113.829"
    },
    {
      "rotation": 180,
      "typeId": "t0",
      "x": "9324.816",
      "y": "14931.517"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "3122.1805",
      "y": "7473.209"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "11572.971",
      "y": "5622.589"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "6817.1535",
      "y": "7192.511"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "2563.269",
      "y": "7331.8044"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "5051.2073",
      "y": "17520.593"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9025.2895",
      "y": "9139.4"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9984.072",
      "y": "17403.58"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "9827.209",
      "y": "17892.098"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "4339.8555",
      "y": "11234.661"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "7030.008",
      "y": "8542.25"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16117.057",
      "y": "12873.43"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16142.025",
      "y": "16631.055"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16172.4619",
      "y": "0.039916992"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13554.31",
      "y": "16241.8"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13613.533",
      "y": "19610.777"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "7050.693",
      "y": "21.866768"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "16141.802",
      "y": "5210.6094"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "7662.1357",
      "y": "19999.9"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.0075683594",
      "y": "7662.0066"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.226621",
      "y": "15325.195"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "3121.0687",
      "y": "10551.242"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "7512.8923",
      "y": "3644.462"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "9689.268",
      "y": "14659.905"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "16176.8923",
      "y": "5460.5815"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "7455.521",
      "y": "3487.8422"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "8691.825",
      "y": "18949.924"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "2340.395",
      "y": "15208.393"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "13012.495",
      "y": "8627.4"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "4073.4349",
      "y": "6536.1056"
    },
    {
      "rotation": 270,
      "typeId": "t6",
      "x": "11833.543",
      "y": "11964.105"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "11136.127",
      "y": "11947.286"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "11650.078",
      "y": "18467.855"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "13631.062",
      "y": "5878.1064"
    },
    {
      "rotation": 180,
      "typeId": "t7",
      "x": "9025.28",
      "y": "7034.82"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "0.26257324",
      "y": "16851.88"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "3120.8728",
      "y": "2156.1348"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "9109.947",
      "y": "11933.715"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "13658.189",
      "y": "7410.749"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "3967.1253",
      "y": "6312.5836"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "4398.348",
      "y": "15612.374"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "3092.8097",
      "y": "81.23071"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "9185.76",
      "y": "12745.366"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "7790.705",
      "y": "14871.91"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "9461.071",
      "y": "10495.854"
    },
    {
      "rotation": 270,
      "typeId": "t9",
      "x": "3912.7524",
      "y": "9880.816"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

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

子题参数

{
  "case": "gardeyn1"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn1-v1",
  "placements": [
    {
      "rotation": 0,
      "typeId": "t0",
      "x": "8402.8923",
      "y": "3143.713"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "7512.8923",
      "y": "323.3301"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "11830.55",
      "y": "5684.8635"
    },
    {
      "rotation": 90,
      "typeId": "t0",
      "x": "13613.341",
      "y": "13113.829"
    },
    {
      "rotation": 180,
      "typeId": "t0",
      "x": "9324.816",
      "y": "14931.517"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "3122.1805",
      "y": "7473.209"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "11572.971",
      "y": "5622.589"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "6817.1535",
      "y": "7192.511"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "2563.269",
      "y": "7331.8044"
    },
    {
      "rotation": 270,
      "typeId": "t1",
      "x": "5051.2073",
      "y": "17520.593"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9025.2895",
      "y": "9139.4"
    },
    {
      "rotation": 90,
      "typeId": "t2",
      "x": "9984.072",
      "y": "17403.58"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "9827.209",
      "y": "17892.098"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "4339.8555",
      "y": "11234.661"
    },
    {
      "rotation": 270,
      "typeId": "t2",
      "x": "7030.008",
      "y": "8542.25"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16117.057",
      "y": "12873.43"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16142.025",
      "y": "16631.055"
    },
    {
      "rotation": 90,
      "typeId": "t3",
      "x": "16172.4619",
      "y": "0.039916992"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13554.31",
      "y": "16241.8"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "13613.533",
      "y": "19610.777"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "7050.693",
      "y": "21.866768"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "16141.802",
      "y": "5210.6094"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "7662.1357",
      "y": "19999.9"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.0075683594",
      "y": "7662.0066"
    },
    {
      "rotation": 270,
      "typeId": "t4",
      "x": "0.226621",
      "y": "15325.195"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "3121.0687",
      "y": "10551.242"
    },
    {
      "rotation": 0,
      "typeId": "t5",
      "x": "7512.8923",
      "y": "3644.462"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "9689.268",
      "y": "14659.905"
    },
    {
      "rotation": 180,
      "typeId": "t5",
      "x": "16176.8923",
      "y": "5460.5815"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "7455.521",
      "y": "3487.8422"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "8691.825",
      "y": "18949.924"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "2340.395",
      "y": "15208.393"
    },
    {
      "rotation": 90,
      "typeId": "t6",
      "x": "13012.495",
      "y": "8627.4"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "4073.4349",
      "y": "6536.1056"
    },
    {
      "rotation": 270,
      "typeId": "t6",
      "x": "11833.543",
      "y": "11964.105"
    },
    {
      "rotation": 0,
      "typeId": "t7",
      "x": "11136.127",
      "y": "11947.286"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "11650.078",
      "y": "18467.855"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "13631.062",
      "y": "5878.1064"
    },
    {
      "rotation": 180,
      "typeId": "t7",
      "x": "9025.28",
      "y": "7034.82"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "0.26257324",
      "y": "16851.88"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "3120.8728",
      "y": "2156.1348"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "9109.947",
      "y": "11933.715"
    },
    {
      "rotation": 90,
      "typeId": "t8",
      "x": "13658.189",
      "y": "7410.749"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "3967.1253",
      "y": "6312.5836"
    },
    {
      "rotation": 270,
      "typeId": "t8",
      "x": "4398.348",
      "y": "15612.374"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "3092.8097",
      "y": "81.23071"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "9185.76",
      "y": "12745.366"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "7790.705",
      "y": "14871.91"
    },
    {
      "rotation": 90,
      "typeId": "t9",
      "x": "9461.071",
      "y": "10495.854"
    },
    {
      "rotation": 270,
      "typeId": "t9",
      "x": "3912.7524",
      "y": "9880.816"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

DISCUSSION

讨论区

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

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