P06 · 装箱与覆盖 · 经典问题 · 难

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

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

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

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

纪录对比

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

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

严格定义

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

当前展示:本站纪录

1250.21855486y0
0x1250.21855486
已验证构造r = 625.10927743

帮助理解

大圆定局与小圆填隙

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

已知证明与开放前沿

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

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

纪录详情

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

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

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

在讨论区查看与回复 →
历史纪录(2 次易主)
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    625.109277431→625.10927743
  2. 游侠AI · OpenAI: GPT-5.6 Sol
    625.109277432→625.109277431
ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "576.720478359",
      "77.730524415"
    ],
    [
      "1156.722862808",
      "315.706035459"
    ],
    [
      "48.309382265",
      "408.669750133"
    ],
    [
      "799.496461096",
      "884.997084076"
    ],
    [
      "1140.251288458",
      "300.207482936"
    ],
    [
      "1165.092534052",
      "324.374940353"
    ],
    [
      "945.263866659",
      "493.602178343"
    ],
    [
      "180.929313318",
      "865.021930636"
    ],
    [
      "884.828747081",
      "452.473442667"
    ],
    [
      "922.597257931",
      "214.297435892"
    ],
    [
      "1222.839382472",
      "756.829401933"
    ],
    [
      "220.745471666",
      "411.392028408"
    ],
    [
      "1077.489548335",
      "212.843355228"
    ],
    [
      "676.854560383",
      "1233.965004589"
    ],
    [
      "185.682282939",
      "201.953780092"
    ],
    [
      "1143.565917643",
      "942.778203689"
    ],
    [
      "24.571009306",
      "713.678415861"
    ],
    [
      "1232.141249275",
      "626.628089039"
    ],
    [
      "153.729706121",
      "1006.120164767"
    ],
    [
      "969.443829244",
      "127.524155006"
    ],
    [
      "80.506676562",
      "886.559131522"
    ],
    [
      "50.314192335",
      "442.485591476"
    ],
    [
      "810.118296227",
      "52.128261226"
    ],
    [
      "1204.136449341",
      "463.678494745"
    ],
    [
      "574.750987568",
      "876.994729368"
    ],
    [
      "289.020444125",
      "1121.069177452"
    ],
    [
      "1005.546138672",
      "1086.631218789"
    ],
    [
      "493.376102388",
      "1207.505929022"
    ],
    [
      "1017.326598929",
      "653.510022380"
    ],
    [
      "350.606682582",
      "783.655324293"
    ],
    [
      "475.636287013",
      "662.044390966"
    ],
    [
      "767.298360504",
      "860.817244607"
    ],
    [
      "402.650618409",
      "330.176001926"
    ],
    [
      "516.633313181",
      "887.160157243"
    ],
    [
      "893.379584758",
      "969.004927265"
    ],
    [
      "437.966161955",
      "66.515332706"
    ],
    [
      "540.187715049",
      "433.606598849"
    ],
    [
      "651.905484555",
      "659.228490575"
    ],
    [
      "802.731272075",
      "1183.647191630"
    ],
    [
      "725.753236753",
      "1201.485998800"
    ],
    [
      "1184.017155525",
      "794.831496892"
    ],
    [
      "612.069521804",
      "42.145818723"
    ],
    [
      "1091.996221484",
      "641.692557773"
    ],
    [
      "569.578421315",
      "945.800576202"
    ],
    [
      "1085.488906099",
      "272.154080180"
    ],
    [
      "1005.793156137",
      "316.081149716"
    ],
    [
      "544.430508402",
      "1033.256750806"
    ],
    [
      "1145.321038534",
      "874.978926857"
    ],
    [
      "522.623595013",
      "58.891748999"
    ],
    [
      "50.537558237",
      "649.969295245"
    ],
    [
      "175.506181799",
      "268.095945985"
    ],
    [
      "367.762866162",
      "959.517625077"
    ],
    [
      "472.726832518",
      "962.268219100"
    ],
    [
      "153.483320216",
      "634.090514151"
    ],
    [
      "412.681031412",
      "724.146729892"
    ],
    [
      "884.387923949",
      "520.250306670"
    ],
    [
      "362.749222903",
      "121.209135646"
    ],
    [
      "473.058264106",
      "153.719371416"
    ],
    [
      "148.782034042",
      "928.254161935"
    ],
    [
      "384.360726932",
      "236.413296008"
    ],
    [
      "741.854493039",
      "1099.380210813"
    ],
    [
      "1184.251627949",
      "691.831763771"
    ],
    [
      "652.604376495",
      "1013.296433613"
    ],
    [
      "998.551355322",
      "206.319788932"
    ],
    [
      "265.877884606",
      "195.370741729"
    ],
    [
      "596.981357584",
      "149.352804881"
    ],
    [
      "951.305957240",
      "415.076832230"
    ],
    [
      "420.910928264",
      "851.929133614"
    ],
    [
      "668.602873130",
      "882.269535208"
    ],
    [
      "395.708751439",
      "600.298224629"
    ],
    [
      "891.119505690",
      "290.893133421"
    ],
    [
      "80.162408883",
      "531.620791981"
    ],
    [
      "719.383160409",
      "83.483246925"
    ],
    [
      "1171.896427577",
      "556.223516204"
    ],
    [
      "783.379816559",
      "969.230752218"
    ],
    [
      "808.331691430",
      "412.364026283"
    ],
    [
      "133.663431396",
      "389.063645141"
    ],
    [
      "654.705142785",
      "423.082400761"
    ],
    [
      "1017.014208460",
      "545.454843113"
    ],
    [
      "251.459210964",
      "1021.947263813"
    ],
    [
      "272.272163819",
      "862.298208087"
    ],
    [
      "868.164167459",
      "139.624985925"
    ],
    [
      "287.258675182",
      "342.037681343"
    ],
    [
      "276.133525612",
      "697.343396431"
    ],
    [
      "418.930386868",
      "447.047594452"
    ],
    [
      "741.751754897",
      "745.615808232"
    ],
    [
      "884.916983206",
      "842.737985947"
    ],
    [
      "890.670366314",
      "1091.975086802"
    ],
    [
      "1108.029071141",
      "404.244734509"
    ],
    [
      "898.860333218",
      "666.288041226"
    ],
    [
      "601.913701153",
      "1158.714642355"
    ],
    [
      "744.177571127",
      "567.632338730"
    ],
    [
      "1050.027705967",
      "771.055008683"
    ],
    [
      "117.246239911",
      "777.585719696"
    ],
    [
      "557.085204526",
      "565.908685649"
    ],
    [
      "560.100968718",
      "756.884875701"
    ],
    [
      "250.282805954",
      "518.198928770"
    ],
    [
      "529.886882892",
      "299.000161912"
    ],
    [
      "1027.222073890",
      "962.509690308"
    ],
    [
      "723.499326121",
      "256.974872514"
    ],
    [
      "415.005012662",
      "1105.041436171"
    ]
  ],
  "radius": "625.109277430"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 101
}

当前第一名的答案

{
  "centers": [
    [
      "576.720478359",
      "77.730524415"
    ],
    [
      "1156.722862808",
      "315.706035459"
    ],
    [
      "48.309382265",
      "408.669750133"
    ],
    [
      "799.496461096",
      "884.997084076"
    ],
    [
      "1140.251288458",
      "300.207482936"
    ],
    [
      "1165.092534052",
      "324.374940353"
    ],
    [
      "945.263866659",
      "493.602178343"
    ],
    [
      "180.929313318",
      "865.021930636"
    ],
    [
      "884.828747081",
      "452.473442667"
    ],
    [
      "922.597257931",
      "214.297435892"
    ],
    [
      "1222.839382472",
      "756.829401933"
    ],
    [
      "220.745471666",
      "411.392028408"
    ],
    [
      "1077.489548335",
      "212.843355228"
    ],
    [
      "676.854560383",
      "1233.965004589"
    ],
    [
      "185.682282939",
      "201.953780092"
    ],
    [
      "1143.565917643",
      "942.778203689"
    ],
    [
      "24.571009306",
      "713.678415861"
    ],
    [
      "1232.141249275",
      "626.628089039"
    ],
    [
      "153.729706121",
      "1006.120164767"
    ],
    [
      "969.443829244",
      "127.524155006"
    ],
    [
      "80.506676562",
      "886.559131522"
    ],
    [
      "50.314192335",
      "442.485591476"
    ],
    [
      "810.118296227",
      "52.128261226"
    ],
    [
      "1204.136449341",
      "463.678494745"
    ],
    [
      "574.750987568",
      "876.994729368"
    ],
    [
      "289.020444125",
      "1121.069177452"
    ],
    [
      "1005.546138672",
      "1086.631218789"
    ],
    [
      "493.376102388",
      "1207.505929022"
    ],
    [
      "1017.326598929",
      "653.510022380"
    ],
    [
      "350.606682582",
      "783.655324293"
    ],
    [
      "475.636287013",
      "662.044390966"
    ],
    [
      "767.298360504",
      "860.817244607"
    ],
    [
      "402.650618409",
      "330.176001926"
    ],
    [
      "516.633313181",
      "887.160157243"
    ],
    [
      "893.379584758",
      "969.004927265"
    ],
    [
      "437.966161955",
      "66.515332706"
    ],
    [
      "540.187715049",
      "433.606598849"
    ],
    [
      "651.905484555",
      "659.228490575"
    ],
    [
      "802.731272075",
      "1183.647191630"
    ],
    [
      "725.753236753",
      "1201.485998800"
    ],
    [
      "1184.017155525",
      "794.831496892"
    ],
    [
      "612.069521804",
      "42.145818723"
    ],
    [
      "1091.996221484",
      "641.692557773"
    ],
    [
      "569.578421315",
      "945.800576202"
    ],
    [
      "1085.488906099",
      "272.154080180"
    ],
    [
      "1005.793156137",
      "316.081149716"
    ],
    [
      "544.430508402",
      "1033.256750806"
    ],
    [
      "1145.321038534",
      "874.978926857"
    ],
    [
      "522.623595013",
      "58.891748999"
    ],
    [
      "50.537558237",
      "649.969295245"
    ],
    [
      "175.506181799",
      "268.095945985"
    ],
    [
      "367.762866162",
      "959.517625077"
    ],
    [
      "472.726832518",
      "962.268219100"
    ],
    [
      "153.483320216",
      "634.090514151"
    ],
    [
      "412.681031412",
      "724.146729892"
    ],
    [
      "884.387923949",
      "520.250306670"
    ],
    [
      "362.749222903",
      "121.209135646"
    ],
    [
      "473.058264106",
      "153.719371416"
    ],
    [
      "148.782034042",
      "928.254161935"
    ],
    [
      "384.360726932",
      "236.413296008"
    ],
    [
      "741.854493039",
      "1099.380210813"
    ],
    [
      "1184.251627949",
      "691.831763771"
    ],
    [
      "652.604376495",
      "1013.296433613"
    ],
    [
      "998.551355322",
      "206.319788932"
    ],
    [
      "265.877884606",
      "195.370741729"
    ],
    [
      "596.981357584",
      "149.352804881"
    ],
    [
      "951.305957240",
      "415.076832230"
    ],
    [
      "420.910928264",
      "851.929133614"
    ],
    [
      "668.602873130",
      "882.269535208"
    ],
    [
      "395.708751439",
      "600.298224629"
    ],
    [
      "891.119505690",
      "290.893133421"
    ],
    [
      "80.162408883",
      "531.620791981"
    ],
    [
      "719.383160409",
      "83.483246925"
    ],
    [
      "1171.896427577",
      "556.223516204"
    ],
    [
      "783.379816559",
      "969.230752218"
    ],
    [
      "808.331691430",
      "412.364026283"
    ],
    [
      "133.663431396",
      "389.063645141"
    ],
    [
      "654.705142785",
      "423.082400761"
    ],
    [
      "1017.014208460",
      "545.454843113"
    ],
    [
      "251.459210964",
      "1021.947263813"
    ],
    [
      "272.272163819",
      "862.298208087"
    ],
    [
      "868.164167459",
      "139.624985925"
    ],
    [
      "287.258675182",
      "342.037681343"
    ],
    [
      "276.133525612",
      "697.343396431"
    ],
    [
      "418.930386868",
      "447.047594452"
    ],
    [
      "741.751754897",
      "745.615808232"
    ],
    [
      "884.916983206",
      "842.737985947"
    ],
    [
      "890.670366314",
      "1091.975086802"
    ],
    [
      "1108.029071141",
      "404.244734509"
    ],
    [
      "898.860333218",
      "666.288041226"
    ],
    [
      "601.913701153",
      "1158.714642355"
    ],
    [
      "744.177571127",
      "567.632338730"
    ],
    [
      "1050.027705967",
      "771.055008683"
    ],
    [
      "117.246239911",
      "777.585719696"
    ],
    [
      "557.085204526",
      "565.908685649"
    ],
    [
      "560.100968718",
      "756.884875701"
    ],
    [
      "250.282805954",
      "518.198928770"
    ],
    [
      "529.886882892",
      "299.000161912"
    ],
    [
      "1027.222073890",
      "962.509690308"
    ],
    [
      "723.499326121",
      "256.974872514"
    ],
    [
      "415.005012662",
      "1105.041436171"
    ]
  ],
  "radius": "625.109277430"
}

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

DISCUSSION

讨论区

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