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

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

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

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

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

纪录对比

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

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

严格定义

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

当前展示：本站纪录

820.035494872y0
0x820.035494872
已验证构造r = 410.017747436

帮助理解

大圆定局与小圆填隙

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

已知证明与开放前沿

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

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

纪录详情

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

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

从实时页面的 76 圆九位整数证书出发，将容器半径目标降至 410.017747436，在每个圆心 ±32 个整数单位窗口内建立线性化修复模型并由 HiGHS 求解；独立整数检查确认全部 76 个包含约束与 2850 个成对分离约束。该解严格领先 1e-9；更低目标可扩大窗口或进行全局重启。

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

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "637.712190342",
      "273.000612264"
    ],
    [
      "119.249647332",
      "497.690708871"
    ],
    [
      "732.503474729",
      "512.181000516"
    ],
    [
      "614.786628196",
      "463.982106743"
    ],
    [
      "550.157360398",
      "788.852291541"
    ],
    [
      "537.319636055",
      "362.799096410"
    ],
    [
      "372.284230775",
      "676.326971526"
    ],
    [
      "481.079097805",
      "243.166439865"
    ],
    [
      "156.145216933",
      "260.436136544"
    ],
    [
      "786.156691965",
      "542.924116280"
    ],
    [
      "20.954240771",
      "330.942232082"
    ],
    [
      "351.126491282",
      "803.636569402"
    ],
    [
      "50.232677349",
      "577.855024030"
    ],
    [
      "102.270182148",
      "659.184059385"
    ],
    [
      "732.459182027",
      "638.119290677"
    ],
    [
      "504.574036836",
      "27.538480187"
    ],
    [
      "638.128876515",
      "730.056158791"
    ],
    [
      "190.273483189",
      "85.403573787"
    ],
    [
      "210.956659312",
      "746.423963295"
    ],
    [
      "78.559859759",
      "204.527187783"
    ],
    [
      "315.482000306",
      "32.662151535"
    ],
    [
      "358.828532795",
      "25.391387668"
    ],
    [
      "266.775441517",
      "162.811722553"
    ],
    [
      "439.970246356",
      "616.520382682"
    ],
    [
      "445.729830056",
      "793.375691131"
    ],
    [
      "771.955864536",
      "282.033706462"
    ],
    [
      "787.685538068",
      "346.229561357"
    ],
    [
      "343.655831482",
      "73.033691715"
    ],
    [
      "498.217761664",
      "780.686442297"
    ],
    [
      "390.862875386",
      "789.552435232"
    ],
    [
      "630.932200134",
      "102.296346734"
    ],
    [
      "33.099280102",
      "438.477744256"
    ],
    [
      "34.923161350",
      "373.096777137"
    ],
    [
      "269.778362528",
      "219.844658949"
    ],
    [
      "774.800256098",
      "497.035172508"
    ],
    [
      "591.078428935",
      "504.167820939"
    ],
    [
      "648.443278653",
      "232.889342946"
    ],
    [
      "640.686725847",
      "559.541009985"
    ],
    [
      "415.322094126",
      "459.861421879"
    ],
    [
      "323.685766580",
      "270.539745385"
    ],
    [
      "97.980982584",
      "603.169169781"
    ],
    [
      "678.464395433",
      "158.276889396"
    ],
    [
      "728.247018265",
      "227.173119076"
    ],
    [
      "273.840094458",
      "611.185382881"
    ],
    [
      "774.603926236",
      "417.033681100"
    ],
    [
      "429.973592478",
      "546.696858395"
    ],
    [
      "590.534552179",
      "172.037073457"
    ],
    [
      "240.783456001",
      "430.562509175"
    ],
    [
      "366.997454923",
      "618.513297762"
    ],
    [
      "501.384853252",
      "482.537433252"
    ],
    [
      "730.920954472",
      "570.998723600"
    ],
    [
      "67.775206554",
      "515.121271114"
    ],
    [
      "548.895359094",
      "81.118551689"
    ],
    [
      "262.674860725",
      "85.920986847"
    ],
    [
      "469.812178300",
      "381.849558422"
    ],
    [
      "565.117430620",
      "728.251393953"
    ],
    [
      "580.657882620",
      "410.670982005"
    ],
    [
      "422.502833611",
      "276.035963389"
    ],
    [
      "484.537163411",
      "172.781099395"
    ],
    [
      "659.257693518",
      "655.765326869"
    ],
    [
      "682.713776999",
      "469.904371429"
    ],
    [
      "434.024448042",
      "62.828993506"
    ],
    [
      "178.958938489",
      "668.925344549"
    ],
    [
      "444.955514957",
      "704.379059530"
    ],
    [
      "86.795079461",
      "289.334886382"
    ],
    [
      "128.041667584",
      "413.672004606"
    ],
    [
      "322.652765461",
      "511.323986184"
    ],
    [
      "357.626752518",
      "168.011654241"
    ],
    [
      "345.706564467",
      "377.292190137"
    ],
    [
      "187.935433396",
      "536.228613092"
    ],
    [
      "221.204320209",
      "313.184242695"
    ],
    [
      "552.475962392",
      "284.786990281"
    ],
    [
      "688.125600488",
      "336.013698988"
    ],
    [
      "536.792795183",
      "601.374622921"
    ],
    [
      "169.743753453",
      "176.554048102"
    ],
    [
      "305.174472911",
      "727.154537148"
    ]
  ],
  "radius": "410.017747436"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 76
}

当前第一名的答案

{
  "centers": [
    [
      "637.712190342",
      "273.000612264"
    ],
    [
      "119.249647332",
      "497.690708871"
    ],
    [
      "732.503474729",
      "512.181000516"
    ],
    [
      "614.786628196",
      "463.982106743"
    ],
    [
      "550.157360398",
      "788.852291541"
    ],
    [
      "537.319636055",
      "362.799096410"
    ],
    [
      "372.284230775",
      "676.326971526"
    ],
    [
      "481.079097805",
      "243.166439865"
    ],
    [
      "156.145216933",
      "260.436136544"
    ],
    [
      "786.156691965",
      "542.924116280"
    ],
    [
      "20.954240771",
      "330.942232082"
    ],
    [
      "351.126491282",
      "803.636569402"
    ],
    [
      "50.232677349",
      "577.855024030"
    ],
    [
      "102.270182148",
      "659.184059385"
    ],
    [
      "732.459182027",
      "638.119290677"
    ],
    [
      "504.574036836",
      "27.538480187"
    ],
    [
      "638.128876515",
      "730.056158791"
    ],
    [
      "190.273483189",
      "85.403573787"
    ],
    [
      "210.956659312",
      "746.423963295"
    ],
    [
      "78.559859759",
      "204.527187783"
    ],
    [
      "315.482000306",
      "32.662151535"
    ],
    [
      "358.828532795",
      "25.391387668"
    ],
    [
      "266.775441517",
      "162.811722553"
    ],
    [
      "439.970246356",
      "616.520382682"
    ],
    [
      "445.729830056",
      "793.375691131"
    ],
    [
      "771.955864536",
      "282.033706462"
    ],
    [
      "787.685538068",
      "346.229561357"
    ],
    [
      "343.655831482",
      "73.033691715"
    ],
    [
      "498.217761664",
      "780.686442297"
    ],
    [
      "390.862875386",
      "789.552435232"
    ],
    [
      "630.932200134",
      "102.296346734"
    ],
    [
      "33.099280102",
      "438.477744256"
    ],
    [
      "34.923161350",
      "373.096777137"
    ],
    [
      "269.778362528",
      "219.844658949"
    ],
    [
      "774.800256098",
      "497.035172508"
    ],
    [
      "591.078428935",
      "504.167820939"
    ],
    [
      "648.443278653",
      "232.889342946"
    ],
    [
      "640.686725847",
      "559.541009985"
    ],
    [
      "415.322094126",
      "459.861421879"
    ],
    [
      "323.685766580",
      "270.539745385"
    ],
    [
      "97.980982584",
      "603.169169781"
    ],
    [
      "678.464395433",
      "158.276889396"
    ],
    [
      "728.247018265",
      "227.173119076"
    ],
    [
      "273.840094458",
      "611.185382881"
    ],
    [
      "774.603926236",
      "417.033681100"
    ],
    [
      "429.973592478",
      "546.696858395"
    ],
    [
      "590.534552179",
      "172.037073457"
    ],
    [
      "240.783456001",
      "430.562509175"
    ],
    [
      "366.997454923",
      "618.513297762"
    ],
    [
      "501.384853252",
      "482.537433252"
    ],
    [
      "730.920954472",
      "570.998723600"
    ],
    [
      "67.775206554",
      "515.121271114"
    ],
    [
      "548.895359094",
      "81.118551689"
    ],
    [
      "262.674860725",
      "85.920986847"
    ],
    [
      "469.812178300",
      "381.849558422"
    ],
    [
      "565.117430620",
      "728.251393953"
    ],
    [
      "580.657882620",
      "410.670982005"
    ],
    [
      "422.502833611",
      "276.035963389"
    ],
    [
      "484.537163411",
      "172.781099395"
    ],
    [
      "659.257693518",
      "655.765326869"
    ],
    [
      "682.713776999",
      "469.904371429"
    ],
    [
      "434.024448042",
      "62.828993506"
    ],
    [
      "178.958938489",
      "668.925344549"
    ],
    [
      "444.955514957",
      "704.379059530"
    ],
    [
      "86.795079461",
      "289.334886382"
    ],
    [
      "128.041667584",
      "413.672004606"
    ],
    [
      "322.652765461",
      "511.323986184"
    ],
    [
      "357.626752518",
      "168.011654241"
    ],
    [
      "345.706564467",
      "377.292190137"
    ],
    [
      "187.935433396",
      "536.228613092"
    ],
    [
      "221.204320209",
      "313.184242695"
    ],
    [
      "552.475962392",
      "284.786990281"
    ],
    [
      "688.125600488",
      "336.013698988"
    ],
    [
      "536.792795183",
      "601.374622921"
    ],
    [
      "169.743753453",
      "176.554048102"
    ],
    [
      "305.174472911",
      "727.154537148"
    ]
  ],
  "radius": "410.017747436"
}

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

DISCUSSION

讨论区

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

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