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

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

把半径分别为 1, 2, …, n 的 n 个圆互不重叠地放进一个圆里，使容器的半径尽可能小。

子题n = 29
目标最小化 容器半径
已知最好（未证明）99.483111566值由 Packomania（Eckard Specht）ccin 坐标文件反推（表页只印四位小数，文件带十二位半径），该表未把这一项标为已证明最优

严格定义

  • 容器圆心在 (radius, radius)、半径为 radius 的圆，radius 由你给出，它就是分数；单位取最小圆的半径
  • 提交radius 与 centers，centers 按半径 1, 2, …, n 的顺序排列
  • 约束第 i 个圆的半径恰好是 i；两两内部不重叠；每个圆完整落在容器圆内
  • 目标让容器半径尽可能小
放大来摆，然后提交 ↗
198.966223132y0
0x198.966223132
已验证构造r = 99.483111566

帮助理解

哪里有优化空间

大圆定骨架、小圆填缝：n 每加一，新来的最大圆都可能颠覆上一轮的整个布局。

前沿在哪里

半径 1..n 装入最小圆正是 2005 年 Al Zimmermann 程序设计竞赛的赛题（n = 5..50），全部最好结果收录在 Packomania 的 ccin 表，但证明一个也没有。本站尚未录入这些值。

查看来源
当前第一名

99.483111566

容器半径

已追平已知最好
纪录保持者创始基准
解题方式人工
挑战这个纪录 ↗
ANSWER FORMAT

答案怎么写

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

提交 radius 与 centers，centers 按半径 1,2,…,n 的顺序排列。容器圆心在 (radius, radius)。每个数写成十进制字符串，例如 "7.5"。

当前第一名的答案

{
  "centers": [
    [
      "38.722884898",
      "26.106831043"
    ],
    [
      "184.454622717",
      "60.84548965"
    ],
    [
      "67.494660074",
      "185.984955321"
    ],
    [
      "32.646366791",
      "164.209615456"
    ],
    [
      "117.590706799",
      "191.51827273"
    ],
    [
      "113.828117238",
      "7.115895053"
    ],
    [
      "159.27604489",
      "170.037566063"
    ],
    [
      "190.150000421",
      "111.590836025"
    ],
    [
      "51.32104859",
      "22.882790624"
    ],
    [
      "146.214282062",
      "97.8440616"
    ],
    [
      "11.961349306",
      "112.087580533"
    ],
    [
      "154.665930198",
      "31.599745879"
    ],
    [
      "170.858162869",
      "50.647359933"
    ],
    [
      "14.919415431",
      "87.190007514"
    ],
    [
      "129.967491944",
      "20.691622858"
    ],
    [
      "116.502615566",
      "144.20662261"
    ],
    [
      "54.219253653",
      "168.437058954"
    ],
    [
      "134.461456338",
      "173.07667696"
    ],
    [
      "45.340757085",
      "100.772863599"
    ],
    [
      "118.073466019",
      "108.24091076"
    ],
    [
      "31.211224663",
      "138.194198605"
    ],
    [
      "175.660118624",
      "85.316383874"
    ],
    [
      "93.547763427",
      "175.735573803"
    ],
    [
      "83.581933347",
      "80.921793386"
    ],
    [
      "77.914094343",
      "130.352885572"
    ],
    [
      "40.196665659",
      "56.067849076"
    ],
    [
      "131.44417846",
      "63.040020342"
    ],
    [
      "87.79618056",
      "29.092842784"
    ],
    [
      "160.673386465",
      "134.064695222"
    ]
  ],
  "radius": "99.483111566"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 29
}

当前第一名的答案

{
  "centers": [
    [
      "38.722884898",
      "26.106831043"
    ],
    [
      "184.454622717",
      "60.84548965"
    ],
    [
      "67.494660074",
      "185.984955321"
    ],
    [
      "32.646366791",
      "164.209615456"
    ],
    [
      "117.590706799",
      "191.51827273"
    ],
    [
      "113.828117238",
      "7.115895053"
    ],
    [
      "159.27604489",
      "170.037566063"
    ],
    [
      "190.150000421",
      "111.590836025"
    ],
    [
      "51.32104859",
      "22.882790624"
    ],
    [
      "146.214282062",
      "97.8440616"
    ],
    [
      "11.961349306",
      "112.087580533"
    ],
    [
      "154.665930198",
      "31.599745879"
    ],
    [
      "170.858162869",
      "50.647359933"
    ],
    [
      "14.919415431",
      "87.190007514"
    ],
    [
      "129.967491944",
      "20.691622858"
    ],
    [
      "116.502615566",
      "144.20662261"
    ],
    [
      "54.219253653",
      "168.437058954"
    ],
    [
      "134.461456338",
      "173.07667696"
    ],
    [
      "45.340757085",
      "100.772863599"
    ],
    [
      "118.073466019",
      "108.24091076"
    ],
    [
      "31.211224663",
      "138.194198605"
    ],
    [
      "175.660118624",
      "85.316383874"
    ],
    [
      "93.547763427",
      "175.735573803"
    ],
    [
      "83.581933347",
      "80.921793386"
    ],
    [
      "77.914094343",
      "130.352885572"
    ],
    [
      "40.196665659",
      "56.067849076"
    ],
    [
      "131.44417846",
      "63.040020342"
    ],
    [
      "87.79618056",
      "29.092842784"
    ],
    [
      "160.673386465",
      "134.064695222"
    ]
  ],
  "radius": "99.483111566"
}

提交 radius 与 centers，centers 按半径 1,2,…,n 的顺序排列。容器圆心在 (radius, radius)。每个数写成十进制字符串，例如 "7.5"。 · 验证器 v1.0.0