P02 · 装箱与覆盖 · 经典问题 · 基线易突破 · 难

单位圆内的等圆装箱 · n = 108

文献中也称circles in a circlepacking equal circles in a circlecci

在半径 1 的圆内放置 n 个半径相同、互不重叠的小圆,使共同半径尽可能大。

子题n = 108
目标最大化 共同半径

纪录对比

共同半径 · 越大越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好[0.0867753037108808912992375018415, 0.0867753037108808912992375018425]见来源署名packomania.com ↗
本站纪录暂无选手纪录——

严格定义

  • 容器半径 1 的圆,圆心在 (1, 1),两个坐标都在 0 到 2 之间
  • 提交恰好 n 个圆:一个共同半径 radius 与 n 个圆心 centers
  • 约束每个圆完整落在容器内;两两内部不重叠,相切允许
  • 目标让共同半径尽可能大
挑战这个纪录 ↗

当前展示:起步布局

2y0
0x2
已验证构造r = 0.086775303

帮助理解

哪里有优化空间

最优构形是「卡死」的接触结构:圆彼此顶住、顶住边界,常出现斜排、错位、以及不碰任何邻居的游离圆。规整的网格摆法几乎从不最优。

前沿在哪里

n = 1..14 与 19 已证明;其余规模的最优性仍未知。本站接入 Packomania 中 n = 1..300 的公开构型,大规模部分集中成一张表供算法批量挑战。

查看来源
单位圆内的等圆装箱 n = 108 的当前构型
构型与历史

起步布局

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

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

答案怎么写

容器是半径 1 的圆,圆心在 (1, 1),所以两个坐标都在 0 到 2 之间。坐标和半径用同一个单位,直接写成小数,例如 "0.5",最多九位小数。

提交 radius 与 centers。每个数写成十进制字符串,例如 "0.2"。

起步布局答案

{
  "centers": [
    [
      "1.063952677",
      "0.089017343"
    ],
    [
      "0.890456638",
      "0.093369095"
    ],
    [
      "1.235139016",
      "0.117566439"
    ],
    [
      "0.720916843",
      "0.130464528"
    ],
    [
      "1.397833125",
      "0.17798531"
    ],
    [
      "0.561456353",
      "0.198963911"
    ],
    [
      "0.982230277",
      "0.24212274"
    ],
    [
      "1.546159182",
      "0.268091882"
    ],
    [
      "1.212090116",
      "0.289579699"
    ],
    [
      "0.417136602",
      "0.297046941"
    ],
    [
      "0.750818627",
      "0.301419775"
    ],
    [
      "1.374784225",
      "0.34999857"
    ],
    [
      "0.591358137",
      "0.369919159"
    ],
    [
      "1.674760275",
      "0.384631885"
    ],
    [
      "1.071307648",
      "0.391069158"
    ],
    [
      "0.897777581",
      "0.393739216"
    ],
    [
      "0.293303178",
      "0.421589291"
    ],
    [
      "1.514957198",
      "0.45232819"
    ],
    [
      "1.229764401",
      "0.463703353"
    ],
    [
      "0.744347124",
      "0.474849683"
    ],
    [
      "0.456867761",
      "0.479610326"
    ],
    [
      "1.694956104",
      "0.557003407"
    ],
    [
      "1.376770652",
      "0.557324818"
    ],
    [
      "1.076259006",
      "0.56454912"
    ],
    [
      "0.902728939",
      "0.567219178"
    ],
    [
      "0.602217292",
      "0.57444348"
    ],
    [
      "0.29509672",
      "0.595130631"
    ],
    [
      "1.534730097",
      "0.637710602"
    ],
    [
      "1.228600305",
      "0.647687209"
    ],
    [
      "1.842691251",
      "0.648075574"
    ],
    [
      "0.754558592",
      "0.657581569"
    ],
    [
      "0.454046946",
      "0.664805871"
    ],
    [
      "0.144292788",
      "0.681025842"
    ],
    [
      "1.685329088",
      "0.730286799"
    ],
    [
      "1.380941604",
      "0.730825298"
    ],
    [
      "1.080429958",
      "0.7380496"
    ],
    [
      "0.906899891",
      "0.740719658"
    ],
    [
      "0.606388245",
      "0.74794396"
    ],
    [
      "0.299267673",
      "0.768631111"
    ],
    [
      "1.533282904",
      "0.813963387"
    ],
    [
      "1.232771258",
      "0.821187689"
    ],
    [
      "1.842370308",
      "0.821625885"
    ],
    [
      "0.758729545",
      "0.831082049"
    ],
    [
      "0.458217899",
      "0.838306351"
    ],
    [
      "0.099401001",
      "0.848669932"
    ],
    [
      "1.68950004",
      "0.903787279"
    ],
    [
      "1.385112557",
      "0.904325778"
    ],
    [
      "1.084600911",
      "0.91155008"
    ],
    [
      "0.911070844",
      "0.914220138"
    ],
    [
      "0.610559198",
      "0.92144444"
    ],
    [
      "0.249942265",
      "0.935024673"
    ],
    [
      "1.913008946",
      "0.980150319"
    ],
    [
      "1.537453857",
      "0.987463867"
    ],
    [
      "1.236942211",
      "0.994688169"
    ],
    [
      "0.762900497",
      "1.004582529"
    ],
    [
      "0.462388851",
      "1.011806831"
    ],
    [
      "0.087035049",
      "1.021779425"
    ],
    [
      "1.749976797",
      "1.06645988"
    ],
    [
      "1.38928351",
      "1.077826258"
    ],
    [
      "1.088771864",
      "1.08505056"
    ],
    [
      "0.915241797",
      "1.087720618"
    ],
    [
      "0.614730151",
      "1.09494492"
    ],
    [
      "0.311377903",
      "1.097337567"
    ],
    [
      "1.900277127",
      "1.153233288"
    ],
    [
      "1.541624809",
      "1.160964347"
    ],
    [
      "1.241113163",
      "1.168188649"
    ],
    [
      "0.76707145",
      "1.178083008"
    ],
    [
      "0.158694211",
      "1.179845164"
    ],
    [
      "0.466559804",
      "1.185307311"
    ],
    [
      "1.699713629",
      "1.232572575"
    ],
    [
      "1.393454463",
      "1.251326738"
    ],
    [
      "1.092942817",
      "1.25855104"
    ],
    [
      "0.91941275",
      "1.261221097"
    ],
    [
      "0.618901104",
      "1.268445399"
    ],
    [
      "0.315548856",
      "1.270838047"
    ],
    [
      "1.855031098",
      "1.320782117"
    ],
    [
      "1.545795762",
      "1.334464826"
    ],
    [
      "1.245284116",
      "1.341689128"
    ],
    [
      "0.771242403",
      "1.351583488"
    ],
    [
      "0.157924004",
      "1.353394062"
    ],
    [
      "0.464458776",
      "1.359976417"
    ],
    [
      "1.703884582",
      "1.406073055"
    ],
    [
      "1.397625416",
      "1.424827217"
    ],
    [
      "1.097113769",
      "1.432051519"
    ],
    [
      "0.923583703",
      "1.434721577"
    ],
    [
      "0.623072056",
      "1.441945879"
    ],
    [
      "0.305872819",
      "1.444118708"
    ],
    [
      "1.542677644",
      "1.520114489"
    ],
    [
      "1.25594245",
      "1.525055709"
    ],
    [
      "0.774745232",
      "1.527676545"
    ],
    [
      "0.485748652",
      "1.548068901"
    ],
    [
      "1.705710201",
      "1.57961406"
    ],
    [
      "1.102176457",
      "1.605528269"
    ],
    [
      "0.92864639",
      "1.608198326"
    ],
    [
      "0.326245717",
      "1.616469393"
    ],
    [
      "1.40809913",
      "1.629697503"
    ],
    [
      "0.625809881",
      "1.650551414"
    ],
    [
      "1.248750735",
      "1.698457245"
    ],
    [
      "1.583314229",
      "1.702654863"
    ],
    [
      "0.788602457",
      "1.710704473"
    ],
    [
      "0.455036985",
      "1.732799194"
    ],
    [
      "1.017748893",
      "1.757175604"
    ],
    [
      "1.439851409",
      "1.800318739"
    ],
    [
      "0.603510017",
      "1.822663381"
    ],
    [
      "1.280503013",
      "1.869078481"
    ],
    [
      "0.766302593",
      "1.882816441"
    ],
    [
      "1.111024033",
      "1.906450776"
    ],
    [
      "0.937535333",
      "1.911085897"
    ]
  ],
  "radius": "0.086775303"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 108
}

起步布局答案

{
  "centers": [
    [
      "1.063952677",
      "0.089017343"
    ],
    [
      "0.890456638",
      "0.093369095"
    ],
    [
      "1.235139016",
      "0.117566439"
    ],
    [
      "0.720916843",
      "0.130464528"
    ],
    [
      "1.397833125",
      "0.17798531"
    ],
    [
      "0.561456353",
      "0.198963911"
    ],
    [
      "0.982230277",
      "0.24212274"
    ],
    [
      "1.546159182",
      "0.268091882"
    ],
    [
      "1.212090116",
      "0.289579699"
    ],
    [
      "0.417136602",
      "0.297046941"
    ],
    [
      "0.750818627",
      "0.301419775"
    ],
    [
      "1.374784225",
      "0.34999857"
    ],
    [
      "0.591358137",
      "0.369919159"
    ],
    [
      "1.674760275",
      "0.384631885"
    ],
    [
      "1.071307648",
      "0.391069158"
    ],
    [
      "0.897777581",
      "0.393739216"
    ],
    [
      "0.293303178",
      "0.421589291"
    ],
    [
      "1.514957198",
      "0.45232819"
    ],
    [
      "1.229764401",
      "0.463703353"
    ],
    [
      "0.744347124",
      "0.474849683"
    ],
    [
      "0.456867761",
      "0.479610326"
    ],
    [
      "1.694956104",
      "0.557003407"
    ],
    [
      "1.376770652",
      "0.557324818"
    ],
    [
      "1.076259006",
      "0.56454912"
    ],
    [
      "0.902728939",
      "0.567219178"
    ],
    [
      "0.602217292",
      "0.57444348"
    ],
    [
      "0.29509672",
      "0.595130631"
    ],
    [
      "1.534730097",
      "0.637710602"
    ],
    [
      "1.228600305",
      "0.647687209"
    ],
    [
      "1.842691251",
      "0.648075574"
    ],
    [
      "0.754558592",
      "0.657581569"
    ],
    [
      "0.454046946",
      "0.664805871"
    ],
    [
      "0.144292788",
      "0.681025842"
    ],
    [
      "1.685329088",
      "0.730286799"
    ],
    [
      "1.380941604",
      "0.730825298"
    ],
    [
      "1.080429958",
      "0.7380496"
    ],
    [
      "0.906899891",
      "0.740719658"
    ],
    [
      "0.606388245",
      "0.74794396"
    ],
    [
      "0.299267673",
      "0.768631111"
    ],
    [
      "1.533282904",
      "0.813963387"
    ],
    [
      "1.232771258",
      "0.821187689"
    ],
    [
      "1.842370308",
      "0.821625885"
    ],
    [
      "0.758729545",
      "0.831082049"
    ],
    [
      "0.458217899",
      "0.838306351"
    ],
    [
      "0.099401001",
      "0.848669932"
    ],
    [
      "1.68950004",
      "0.903787279"
    ],
    [
      "1.385112557",
      "0.904325778"
    ],
    [
      "1.084600911",
      "0.91155008"
    ],
    [
      "0.911070844",
      "0.914220138"
    ],
    [
      "0.610559198",
      "0.92144444"
    ],
    [
      "0.249942265",
      "0.935024673"
    ],
    [
      "1.913008946",
      "0.980150319"
    ],
    [
      "1.537453857",
      "0.987463867"
    ],
    [
      "1.236942211",
      "0.994688169"
    ],
    [
      "0.762900497",
      "1.004582529"
    ],
    [
      "0.462388851",
      "1.011806831"
    ],
    [
      "0.087035049",
      "1.021779425"
    ],
    [
      "1.749976797",
      "1.06645988"
    ],
    [
      "1.38928351",
      "1.077826258"
    ],
    [
      "1.088771864",
      "1.08505056"
    ],
    [
      "0.915241797",
      "1.087720618"
    ],
    [
      "0.614730151",
      "1.09494492"
    ],
    [
      "0.311377903",
      "1.097337567"
    ],
    [
      "1.900277127",
      "1.153233288"
    ],
    [
      "1.541624809",
      "1.160964347"
    ],
    [
      "1.241113163",
      "1.168188649"
    ],
    [
      "0.76707145",
      "1.178083008"
    ],
    [
      "0.158694211",
      "1.179845164"
    ],
    [
      "0.466559804",
      "1.185307311"
    ],
    [
      "1.699713629",
      "1.232572575"
    ],
    [
      "1.393454463",
      "1.251326738"
    ],
    [
      "1.092942817",
      "1.25855104"
    ],
    [
      "0.91941275",
      "1.261221097"
    ],
    [
      "0.618901104",
      "1.268445399"
    ],
    [
      "0.315548856",
      "1.270838047"
    ],
    [
      "1.855031098",
      "1.320782117"
    ],
    [
      "1.545795762",
      "1.334464826"
    ],
    [
      "1.245284116",
      "1.341689128"
    ],
    [
      "0.771242403",
      "1.351583488"
    ],
    [
      "0.157924004",
      "1.353394062"
    ],
    [
      "0.464458776",
      "1.359976417"
    ],
    [
      "1.703884582",
      "1.406073055"
    ],
    [
      "1.397625416",
      "1.424827217"
    ],
    [
      "1.097113769",
      "1.432051519"
    ],
    [
      "0.923583703",
      "1.434721577"
    ],
    [
      "0.623072056",
      "1.441945879"
    ],
    [
      "0.305872819",
      "1.444118708"
    ],
    [
      "1.542677644",
      "1.520114489"
    ],
    [
      "1.25594245",
      "1.525055709"
    ],
    [
      "0.774745232",
      "1.527676545"
    ],
    [
      "0.485748652",
      "1.548068901"
    ],
    [
      "1.705710201",
      "1.57961406"
    ],
    [
      "1.102176457",
      "1.605528269"
    ],
    [
      "0.92864639",
      "1.608198326"
    ],
    [
      "0.326245717",
      "1.616469393"
    ],
    [
      "1.40809913",
      "1.629697503"
    ],
    [
      "0.625809881",
      "1.650551414"
    ],
    [
      "1.248750735",
      "1.698457245"
    ],
    [
      "1.583314229",
      "1.702654863"
    ],
    [
      "0.788602457",
      "1.710704473"
    ],
    [
      "0.455036985",
      "1.732799194"
    ],
    [
      "1.017748893",
      "1.757175604"
    ],
    [
      "1.439851409",
      "1.800318739"
    ],
    [
      "0.603510017",
      "1.822663381"
    ],
    [
      "1.280503013",
      "1.869078481"
    ],
    [
      "0.766302593",
      "1.882816441"
    ],
    [
      "1.111024033",
      "1.906450776"
    ],
    [
      "0.937535333",
      "1.911085897"
    ]
  ],
  "radius": "0.086775303"
}

提交 radius 与 centers。每个数写成十进制字符串,例如 "0.2"。 · 验证器 v1.0.0

DISCUSSION

讨论区

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

还没有帖子。第一个聊聊这道题的思路?