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

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

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

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

严格定义

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

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

89.750962684

容器半径

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

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "38.035961193",
      "57.072098937"
    ],
    [
      "87.217486182",
      "74.283809223"
    ],
    [
      "93.46065523",
      "99.446031795"
    ],
    [
      "21.408559512",
      "141.423347189"
    ],
    [
      "73.589769288",
      "6.601947189"
    ],
    [
      "70.922050374",
      "171.248550833"
    ],
    [
      "168.908449855",
      "113.677151945"
    ],
    [
      "162.057449004",
      "51.813531225"
    ],
    [
      "127.564280547",
      "105.831332134"
    ],
    [
      "11.795484126",
      "106.28645106"
    ],
    [
      "19.927128406",
      "126.170000154"
    ],
    [
      "34.397734192",
      "108.29259631"
    ],
    [
      "53.070634325",
      "57.586258024"
    ],
    [
      "31.690497232",
      "41.097178669"
    ],
    [
      "122.032908862",
      "157.171896919"
    ],
    [
      "91.680811503",
      "163.47667177"
    ],
    [
      "93.374260059",
      "17.090283582"
    ],
    [
      "59.236654171",
      "24.811932648"
    ],
    [
      "84.579156615",
      "51.999396368"
    ],
    [
      "109.388023557",
      "82.091257744"
    ],
    [
      "145.550133726",
      "129.914968721"
    ],
    [
      "23.384191878",
      "76.125813975"
    ],
    [
      "101.759488424",
      "124.831396611"
    ],
    [
      "66.533754151",
      "92.066807539"
    ],
    [
      "154.309022691",
      "84.756560156"
    ],
    [
      "129.712785306",
      "40.079663367"
    ],
    [
      "54.627762976",
      "141.657606829"
    ]
  ],
  "radius": "89.750962684"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 27
}

当前第一名的答案

{
  "centers": [
    [
      "38.035961193",
      "57.072098937"
    ],
    [
      "87.217486182",
      "74.283809223"
    ],
    [
      "93.46065523",
      "99.446031795"
    ],
    [
      "21.408559512",
      "141.423347189"
    ],
    [
      "73.589769288",
      "6.601947189"
    ],
    [
      "70.922050374",
      "171.248550833"
    ],
    [
      "168.908449855",
      "113.677151945"
    ],
    [
      "162.057449004",
      "51.813531225"
    ],
    [
      "127.564280547",
      "105.831332134"
    ],
    [
      "11.795484126",
      "106.28645106"
    ],
    [
      "19.927128406",
      "126.170000154"
    ],
    [
      "34.397734192",
      "108.29259631"
    ],
    [
      "53.070634325",
      "57.586258024"
    ],
    [
      "31.690497232",
      "41.097178669"
    ],
    [
      "122.032908862",
      "157.171896919"
    ],
    [
      "91.680811503",
      "163.47667177"
    ],
    [
      "93.374260059",
      "17.090283582"
    ],
    [
      "59.236654171",
      "24.811932648"
    ],
    [
      "84.579156615",
      "51.999396368"
    ],
    [
      "109.388023557",
      "82.091257744"
    ],
    [
      "145.550133726",
      "129.914968721"
    ],
    [
      "23.384191878",
      "76.125813975"
    ],
    [
      "101.759488424",
      "124.831396611"
    ],
    [
      "66.533754151",
      "92.066807539"
    ],
    [
      "154.309022691",
      "84.756560156"
    ],
    [
      "129.712785306",
      "40.079663367"
    ],
    [
      "54.627762976",
      "141.657606829"
    ]
  ],
  "radius": "89.750962684"
}

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