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

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

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

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

严格定义

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

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

104.540363768

容器半径

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

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "175.566732607",
      "172.223928193"
    ],
    [
      "54.492864968",
      "21.988204675"
    ],
    [
      "54.703591952",
      "82.094486104"
    ],
    [
      "60.770449137",
      "195.035766037"
    ],
    [
      "150.353892451",
      "16.404149385"
    ],
    [
      "170.488293633",
      "177.728173781"
    ],
    [
      "12.567047052",
      "137.021613378"
    ],
    [
      "183.0612699",
      "48.375346751"
    ],
    [
      "16.276103279",
      "68.04027651"
    ],
    [
      "198.135543125",
      "117.875384671"
    ],
    [
      "102.481814657",
      "122.828132673"
    ],
    [
      "94.111712112",
      "12.589495633"
    ],
    [
      "70.146317494",
      "19.707069717"
    ],
    [
      "120.600959217",
      "193.644879619"
    ],
    [
      "51.648368664",
      "176.789333294"
    ],
    [
      "148.089961485",
      "181.63010728"
    ],
    [
      "31.1317072",
      "152.231918885"
    ],
    [
      "159.396081184",
      "37.60692797"
    ],
    [
      "91.765453976",
      "43.500578966"
    ],
    [
      "124.568614808",
      "22.406678436"
    ],
    [
      "86.425385966",
      "186.093045867"
    ],
    [
      "132.929100403",
      "110.101672412"
    ],
    [
      "129.127804472",
      "65.262513752"
    ],
    [
      "119.170315239",
      "153.995815882"
    ],
    [
      "71.763950349",
      "141.600793977"
    ],
    [
      "46.992954279",
      "51.090533068"
    ],
    [
      "85.132472635",
      "89.019844762"
    ],
    [
      "170.107244564",
      "143.53497313"
    ],
    [
      "177.279083787",
      "84.920747608"
    ],
    [
      "30.286201204",
      "104.540363768"
    ]
  ],
  "radius": "104.540363768"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 30
}

当前第一名的答案

{
  "centers": [
    [
      "175.566732607",
      "172.223928193"
    ],
    [
      "54.492864968",
      "21.988204675"
    ],
    [
      "54.703591952",
      "82.094486104"
    ],
    [
      "60.770449137",
      "195.035766037"
    ],
    [
      "150.353892451",
      "16.404149385"
    ],
    [
      "170.488293633",
      "177.728173781"
    ],
    [
      "12.567047052",
      "137.021613378"
    ],
    [
      "183.0612699",
      "48.375346751"
    ],
    [
      "16.276103279",
      "68.04027651"
    ],
    [
      "198.135543125",
      "117.875384671"
    ],
    [
      "102.481814657",
      "122.828132673"
    ],
    [
      "94.111712112",
      "12.589495633"
    ],
    [
      "70.146317494",
      "19.707069717"
    ],
    [
      "120.600959217",
      "193.644879619"
    ],
    [
      "51.648368664",
      "176.789333294"
    ],
    [
      "148.089961485",
      "181.63010728"
    ],
    [
      "31.1317072",
      "152.231918885"
    ],
    [
      "159.396081184",
      "37.60692797"
    ],
    [
      "91.765453976",
      "43.500578966"
    ],
    [
      "124.568614808",
      "22.406678436"
    ],
    [
      "86.425385966",
      "186.093045867"
    ],
    [
      "132.929100403",
      "110.101672412"
    ],
    [
      "129.127804472",
      "65.262513752"
    ],
    [
      "119.170315239",
      "153.995815882"
    ],
    [
      "71.763950349",
      "141.600793977"
    ],
    [
      "46.992954279",
      "51.090533068"
    ],
    [
      "85.132472635",
      "89.019844762"
    ],
    [
      "170.107244564",
      "143.53497313"
    ],
    [
      "177.279083787",
      "84.920747608"
    ],
    [
      "30.286201204",
      "104.540363768"
    ]
  ],
  "radius": "104.540363768"
}

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