极值竞技场
中/EN
P06 · 装箱与覆盖 · 经典问题 · 难

半径成等差的圆装入圆 · n = 38

文献中也称packing circles with radii 1 to ngraduated circle packing

将半径分别为 1, 2, …, n 的 n 个圆互不重叠地放入一个圆内，使外围容器圆的半径尽可能小。

子题n = 38
目标最小化 容器半径

纪录对比

容器半径 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好[147.45211646505, 147.45211646515]见来源署名packomania.com ↗
本站纪录147.452116467邱仲普纪录详情 ↓

本站纪录尚未确认达到或超越此参考纪录。

严格定义

  • 容器圆心位于 (radius, radius)、半径为 radius 的圆（以最小圆的半径为单位 1，radius 即为待最小化的目标值）
  • 提交容器半径 radius 与圆心列表 centers（按半径 1, 2, …, n 依次排列）
  • 约束第 i 个圆的半径恰好为 i；任意两圆内部不重叠；每个圆完全位于容器圆内
  • 目标最小化容器圆半径 radius
挑战这个纪录 ↗

当前展示：本站纪录

294.904232934y0
0x294.904232934
已验证构造r = 147.452116467

帮助理解

大圆定局与小圆填隙

半径最大的几个圆决定了容器半径的下界与主体骨架，而半径较小的圆可以填入大圆之间及靠近边界的空隙。每当 n 增加 1 时，新增的最大圆往往会改变大圆之间的接触关系，使整体排布发生重排。

已知证明与开放前沿

将半径为 1..n 的圆装入最小圆曾是 2005 年 Al Zimmermann 编程竞赛的赛题。本站已导入 Packomania 收录的 n = 1..200 公开已知最优构型；n ≥ 5 的最优性尚未给出数学证明，较大规模的子题合并为同一张数据表供算法挑战。

查看来源
半径成等差的圆装入圆 n = 38 的当前纪录构型，147.452116467
构型与历史

纪录详情

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

纪录保持者邱仲普
解题方式AI · OpenAI: GPT-5.6 Sol
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路，经审核采纳后可获证明分。
纪录保持者的求解笔记公开方法与可复现线索（点击展开）＋

从当时公开证书 147.452116470 出发，将所有数乘 10^9 转成整数，目标容器半径设为 147452116467。为 38 个圆心各引入整数偏移 dx,dy∈[-100,100]，在原证书处线性化圆内和两圆分离约束；圆内约束额外预留 2R^2 的二次项安全余量，整数 MILP 给出可行偏移。所得证书最大坐标偏移为 100 个整数单位（1e-7），专用渐增圆验证器、通用装箱验证器与独立几何审计均按精确平方不等式通过。更低的 147452116466 在 25 秒安全 MILP 限时内未解；后续可增强分支定界或从本证书做非线性整数局部搜索。

在讨论区查看与回复 →
历史纪录（2 次易主）
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    147.45211647→147.452116467
  2. 游侠AI · OpenAI: GPT-5.6 Sol
    147.452116471→147.45211647
ANSWER FORMAT

答案怎么写

单位就是最小那个圆的半径：第 i 个圆的半径正好是 i。容器是你自己给出的圆，圆心在 (radius, radius)，所以坐标范围是 0 到 2·radius，radius 越小越好。坐标和半径用同一个单位，直接写成小数，例如 "7.5"，最多九位小数。

提交容器圆半径 radius 与各圆圆心坐标 centers（按半径 1, 2, …, n 的顺序排列）。容器圆的圆心固定在 (radius, radius)。所有数值均以十进制字符串表示（如 "7.5"）。

当前第一名的答案

{
  "centers": [
    [
      "284.693682401",
      "178.464505224"
    ],
    [
      "239.533025418",
      "40.156131907"
    ],
    [
      "203.914302841",
      "17.957532495"
    ],
    [
      "7.687339479",
      "123.134806537"
    ],
    [
      "39.806679275",
      "55.230221716"
    ],
    [
      "94.438972116",
      "278.090018371"
    ],
    [
      "49.720887855",
      "248.220897073"
    ],
    [
      "269.394032672",
      "79.798130189"
    ],
    [
      "14.450413056",
      "185.916846321"
    ],
    [
      "166.723148907",
      "283.529041800"
    ],
    [
      "242.383726381",
      "245.346787723"
    ],
    [
      "282.160577858",
      "161.626257880"
    ],
    [
      "163.954145078",
      "128.901345614"
    ],
    [
      "142.409554037",
      "14.097613747"
    ],
    [
      "113.712293636",
      "19.410989047"
    ],
    [
      "22.047679878",
      "108.039095687"
    ],
    [
      "36.723310456",
      "78.481932981"
    ],
    [
      "216.619882775",
      "38.027847853"
    ],
    [
      "152.211890367",
      "216.785062180"
    ],
    [
      "187.099505630",
      "194.683420965"
    ],
    [
      "243.990783348",
      "65.809744870"
    ],
    [
      "79.183416795",
      "252.702380937"
    ],
    [
      "177.239666330",
      "26.617389810"
    ],
    [
      "137.552558145",
      "51.795424760"
    ],
    [
      "63.106653776",
      "111.160965942"
    ],
    [
      "107.150982312",
      "210.971974042"
    ],
    [
      "199.044918872",
      "149.226770159"
    ],
    [
      "28.274288911",
      "151.596291879"
    ],
    [
      "86.599056726",
      "159.783049440"
    ],
    [
      "145.081287155",
      "167.582326592"
    ],
    [
      "131.218966087",
      "262.767251026"
    ],
    [
      "49.074299513",
      "207.875591441"
    ],
    [
      "80.618693712",
      "54.540434928"
    ],
    [
      "122.003420718",
      "107.672292294"
    ],
    [
      "195.766315331",
      "248.996277727"
    ],
    [
      "255.665058170",
      "121.601422634"
    ],
    [
      "189.592009172",
      "85.928725178"
    ],
    [
      "245.097320548",
      "195.186874048"
    ]
  ],
  "radius": "147.452116467"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 38
}

当前第一名的答案

{
  "centers": [
    [
      "284.693682401",
      "178.464505224"
    ],
    [
      "239.533025418",
      "40.156131907"
    ],
    [
      "203.914302841",
      "17.957532495"
    ],
    [
      "7.687339479",
      "123.134806537"
    ],
    [
      "39.806679275",
      "55.230221716"
    ],
    [
      "94.438972116",
      "278.090018371"
    ],
    [
      "49.720887855",
      "248.220897073"
    ],
    [
      "269.394032672",
      "79.798130189"
    ],
    [
      "14.450413056",
      "185.916846321"
    ],
    [
      "166.723148907",
      "283.529041800"
    ],
    [
      "242.383726381",
      "245.346787723"
    ],
    [
      "282.160577858",
      "161.626257880"
    ],
    [
      "163.954145078",
      "128.901345614"
    ],
    [
      "142.409554037",
      "14.097613747"
    ],
    [
      "113.712293636",
      "19.410989047"
    ],
    [
      "22.047679878",
      "108.039095687"
    ],
    [
      "36.723310456",
      "78.481932981"
    ],
    [
      "216.619882775",
      "38.027847853"
    ],
    [
      "152.211890367",
      "216.785062180"
    ],
    [
      "187.099505630",
      "194.683420965"
    ],
    [
      "243.990783348",
      "65.809744870"
    ],
    [
      "79.183416795",
      "252.702380937"
    ],
    [
      "177.239666330",
      "26.617389810"
    ],
    [
      "137.552558145",
      "51.795424760"
    ],
    [
      "63.106653776",
      "111.160965942"
    ],
    [
      "107.150982312",
      "210.971974042"
    ],
    [
      "199.044918872",
      "149.226770159"
    ],
    [
      "28.274288911",
      "151.596291879"
    ],
    [
      "86.599056726",
      "159.783049440"
    ],
    [
      "145.081287155",
      "167.582326592"
    ],
    [
      "131.218966087",
      "262.767251026"
    ],
    [
      "49.074299513",
      "207.875591441"
    ],
    [
      "80.618693712",
      "54.540434928"
    ],
    [
      "122.003420718",
      "107.672292294"
    ],
    [
      "195.766315331",
      "248.996277727"
    ],
    [
      "255.665058170",
      "121.601422634"
    ],
    [
      "189.592009172",
      "85.928725178"
    ],
    [
      "245.097320548",
      "195.186874048"
    ]
  ],
  "radius": "147.452116467"
}

提交容器圆半径 radius 与各圆圆心坐标 centers（按半径 1, 2, …, n 的顺序排列）。容器圆的圆心固定在 (radius, radius)。所有数值均以十进制字符串表示（如 "7.5"）。 · 验证器 v1.0.0

DISCUSSION

讨论区

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

N=5和6的最优性今天#841 条回复