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

不规则零件条带排样 · GARDEYN2 · 50 件，各不相同

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

子题GARDEYN2 · 50 件，各不相同

目标最小化占用长度

严格定义

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

放大来摆，然后提交 ↗

已验证构造占用长度 47319.411

帮助理解

为什么是这三个实例

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

查看来源

当前第一名

47319.410679

占用长度

纪录保持者NUE_13

解题方式人工

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

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

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

历史纪录（1 次易主）

NUE_13人工
47319.670679→47319.410679
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-gardeyn2-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3869.787889",
      "y": "9551.177817"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "20587.013916",
      "y": "3721.50828"
    },
    {
      "rotation": 0,
      "typeId": "t10",
      "x": "45346.863884",
      "y": "1087.283537"
    },
    {
      "rotation": 0,
      "typeId": "t11",
      "x": "25595.423335",
      "y": "4152.731479"
    },
    {
      "rotation": 0,
      "typeId": "t12",
      "x": "30558.712893",
      "y": "7269.95"
    },
    {
      "rotation": 0,
      "typeId": "t13",
      "x": "14590.149562",
      "y": "4485.543801"
    },
    {
      "rotation": 180,
      "typeId": "t14",
      "x": "3356.098462",
      "y": "9838.9"
    },
    {
      "rotation": 180,
      "typeId": "t15",
      "x": "26628.200169",
      "y": "1994.257899"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "39038.063404",
      "y": "6508.780574"
    },
    {
      "rotation": 0,
      "typeId": "t17",
      "x": "24718.64819",
      "y": "528.118675"
    },
    {
      "rotation": 180,
      "typeId": "t18",
      "x": "21810.394304",
      "y": "7305.044063"
    },
    {
      "rotation": 90,
      "typeId": "t19",
      "x": "37632.258688",
      "y": "6658.258846"
    },
    {
      "rotation": 0,
      "typeId": "t2",
      "x": "3356.148462",
      "y": "9495.95"
    },
    {
      "rotation": 180,
      "typeId": "t20",
      "x": "15203.309559",
      "y": "7405.875466"
    },
    {
      "rotation": 90,
      "typeId": "t21",
      "x": "25377.417888",
      "y": "1920.725308"
    },
    {
      "rotation": 180,
      "typeId": "t22",
      "x": "26954.416669",
      "y": "1488.05"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "10567.337151",
      "y": "0.05"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "1702.05",
      "y": "9999.95"
    },
    {
      "rotation": 90,
      "typeId": "t25",
      "x": "47030.976082",
      "y": "0.05"
    },
    {
      "rotation": 0,
      "typeId": "t26",
      "x": "7516.937889",
      "y": "6999.95"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "46255.390679",
      "y": "1105.347765"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "35970.856061",
      "y": "0.05"
    },
    {
      "rotation": 0,
      "typeId": "t29",
      "x": "36298.803217",
      "y": "9185.98"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "0.05",
      "y": "9235.13585"
    },
    {
      "rotation": 270,
      "typeId": "t30",
      "x": "18333.061186",
      "y": "9999.95"
    },
    {
      "rotation": 90,
      "typeId": "t31",
      "x": "11570.286831",
      "y": "5394.717803"
    },
    {
      "rotation": 90,
      "typeId": "t32",
      "x": "31575.208448",
      "y": "0.05"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "30235.451247",
      "y": "9999.95"
    },
    {
      "rotation": 0,
      "typeId": "t34",
      "x": "26954.422975",
      "y": "0.04"
    },
    {
      "rotation": 180,
      "typeId": "t35",
      "x": "19747.620384",
      "y": "6940.927268"
    },
    {
      "rotation": 270,
      "typeId": "t36",
      "x": "15154.987889",
      "y": "9587.552964"
    },
    {
      "rotation": 90,
      "typeId": "t37",
      "x": "41151.348348",
      "y": "0"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "10306.366669",
      "y": "3922.05"
    },
    {
      "rotation": 180,
      "typeId": "t39",
      "x": "45616.285922",
      "y": "3970.473537"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "4010.05",
      "y": "2722.05"
    },
    {
      "rotation": 0,
      "typeId": "t40",
      "x": "30234.960765",
      "y": "8460.793665"
    },
    {
      "rotation": 270,
      "typeId": "t41",
      "x": "6611.887889",
      "y": "9842.175577"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "21509.575409",
      "y": "1549.913597"
    },
    {
      "rotation": 0,
      "typeId": "t43",
      "x": "19152.592881",
      "y": "2721.963597"
    },
    {
      "rotation": 0,
      "typeId": "t44",
      "x": "41116.051787",
      "y": "507.325607"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "32648.827227",
      "y": "8589.766616"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "40210.863217",
      "y": "9983.393249"
    },
    {
      "rotation": 0,
      "typeId": "t47",
      "x": "36370.338437",
      "y": "5083.959825"
    },
    {
      "rotation": 270,
      "typeId": "t48",
      "x": "28051.842454",
      "y": "1304.1"
    },
    {
      "rotation": 0,
      "typeId": "t49",
      "x": "21496.195569",
      "y": "1965.175106"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "13459.821408",
      "y": "5227.788244"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "40189.410679",
      "y": "3998"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "11528.436859",
      "y": "9995"
    },
    {
      "rotation": 180,
      "typeId": "t8",
      "x": "6611.837889",
      "y": "9999.95"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "33075.647864",
      "y": "7231.512329"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

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

子题参数

{
  "case": "gardeyn2"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn2-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3869.787889",
      "y": "9551.177817"
    },
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "20587.013916",
      "y": "3721.50828"
    },
    {
      "rotation": 0,
      "typeId": "t10",
      "x": "45346.863884",
      "y": "1087.283537"
    },
    {
      "rotation": 0,
      "typeId": "t11",
      "x": "25595.423335",
      "y": "4152.731479"
    },
    {
      "rotation": 0,
      "typeId": "t12",
      "x": "30558.712893",
      "y": "7269.95"
    },
    {
      "rotation": 0,
      "typeId": "t13",
      "x": "14590.149562",
      "y": "4485.543801"
    },
    {
      "rotation": 180,
      "typeId": "t14",
      "x": "3356.098462",
      "y": "9838.9"
    },
    {
      "rotation": 180,
      "typeId": "t15",
      "x": "26628.200169",
      "y": "1994.257899"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "39038.063404",
      "y": "6508.780574"
    },
    {
      "rotation": 0,
      "typeId": "t17",
      "x": "24718.64819",
      "y": "528.118675"
    },
    {
      "rotation": 180,
      "typeId": "t18",
      "x": "21810.394304",
      "y": "7305.044063"
    },
    {
      "rotation": 90,
      "typeId": "t19",
      "x": "37632.258688",
      "y": "6658.258846"
    },
    {
      "rotation": 0,
      "typeId": "t2",
      "x": "3356.148462",
      "y": "9495.95"
    },
    {
      "rotation": 180,
      "typeId": "t20",
      "x": "15203.309559",
      "y": "7405.875466"
    },
    {
      "rotation": 90,
      "typeId": "t21",
      "x": "25377.417888",
      "y": "1920.725308"
    },
    {
      "rotation": 180,
      "typeId": "t22",
      "x": "26954.416669",
      "y": "1488.05"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "10567.337151",
      "y": "0.05"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "1702.05",
      "y": "9999.95"
    },
    {
      "rotation": 90,
      "typeId": "t25",
      "x": "47030.976082",
      "y": "0.05"
    },
    {
      "rotation": 0,
      "typeId": "t26",
      "x": "7516.937889",
      "y": "6999.95"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "46255.390679",
      "y": "1105.347765"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "35970.856061",
      "y": "0.05"
    },
    {
      "rotation": 0,
      "typeId": "t29",
      "x": "36298.803217",
      "y": "9185.98"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "0.05",
      "y": "9235.13585"
    },
    {
      "rotation": 270,
      "typeId": "t30",
      "x": "18333.061186",
      "y": "9999.95"
    },
    {
      "rotation": 90,
      "typeId": "t31",
      "x": "11570.286831",
      "y": "5394.717803"
    },
    {
      "rotation": 90,
      "typeId": "t32",
      "x": "31575.208448",
      "y": "0.05"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "30235.451247",
      "y": "9999.95"
    },
    {
      "rotation": 0,
      "typeId": "t34",
      "x": "26954.422975",
      "y": "0.04"
    },
    {
      "rotation": 180,
      "typeId": "t35",
      "x": "19747.620384",
      "y": "6940.927268"
    },
    {
      "rotation": 270,
      "typeId": "t36",
      "x": "15154.987889",
      "y": "9587.552964"
    },
    {
      "rotation": 90,
      "typeId": "t37",
      "x": "41151.348348",
      "y": "0"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "10306.366669",
      "y": "3922.05"
    },
    {
      "rotation": 180,
      "typeId": "t39",
      "x": "45616.285922",
      "y": "3970.473537"
    },
    {
      "rotation": 180,
      "typeId": "t4",
      "x": "4010.05",
      "y": "2722.05"
    },
    {
      "rotation": 0,
      "typeId": "t40",
      "x": "30234.960765",
      "y": "8460.793665"
    },
    {
      "rotation": 270,
      "typeId": "t41",
      "x": "6611.887889",
      "y": "9842.175577"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "21509.575409",
      "y": "1549.913597"
    },
    {
      "rotation": 0,
      "typeId": "t43",
      "x": "19152.592881",
      "y": "2721.963597"
    },
    {
      "rotation": 0,
      "typeId": "t44",
      "x": "41116.051787",
      "y": "507.325607"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "32648.827227",
      "y": "8589.766616"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "40210.863217",
      "y": "9983.393249"
    },
    {
      "rotation": 0,
      "typeId": "t47",
      "x": "36370.338437",
      "y": "5083.959825"
    },
    {
      "rotation": 270,
      "typeId": "t48",
      "x": "28051.842454",
      "y": "1304.1"
    },
    {
      "rotation": 0,
      "typeId": "t49",
      "x": "21496.195569",
      "y": "1965.175106"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "13459.821408",
      "y": "5227.788244"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "40189.410679",
      "y": "3998"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "11528.436859",
      "y": "9995"
    },
    {
      "rotation": 180,
      "typeId": "t8",
      "x": "6611.837889",
      "y": "9999.95"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "33075.647864",
      "y": "7231.512329"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

DISCUSSION

讨论区

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

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