P13 · 装箱与覆盖 · 经典问题

半径成等差的圆装入正方形 · n = 3

把半径分别为 1, 2, …, n 的 n 个圆互不重叠地放进一个正方形,使正方形边长尽可能小。

子题n = 3
目标最小化 正方形边长
已证明最优8.535533906半径 2 与 3 的两圆圆心至少相距 5,逼出边长 5(1+√2/2)

已完成已经有达到上限的答案,这道子题没有可争的了

严格定义

  • 容器边长 side 的正方形,左下角是原点,side 由你给出,它就是分数;单位取最小圆的半径
  • 提交side 与 centers,centers 按半径 1, 2, …, n 的顺序排列
  • 约束第 i 个圆的半径恰好是 i;两两内部不重叠;每个圆完整落在正方形内
  • 目标让正方形边长尽可能小
打开编辑器看看
8.535533906y0
0x8.535533906
已验证构造side = 8.535533906

帮助理解

哪里有优化空间

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

前沿在哪里

n ≤ 4 由圆心距的初等下界证明(见各子题)。圆容器版是 Zimmermann 竞赛的赛题(见 Packomania),正方形容器版未见文献表,其余 n 开放。

查看来源
当前第一名

8.535533906

正方形边长

已达最优最优值已证明,无法再提升
纪录保持者参考答案
解题方式
挑战这个纪录
ANSWER FORMAT

答案怎么写

单位就是最小那个圆的半径:第 i 个圆的半径正好是 i。容器是你自己给出的正方形,左下角是原点 (0, 0),右上角是 (side, side),side 越小越好。坐标和半径用同一个单位,直接写成小数,例如 "3.5",最多九位小数。

提交 side 与 centers,centers 按半径 1,2,…,n 的顺序排列。每个数写成十进制字符串,例如 "3.5"。

当前第一名的答案

{
  "centers": [
    [
      "7.535533906",
      "1"
    ],
    [
      "6.535533906",
      "6.535533906"
    ],
    [
      "3",
      "3"
    ]
  ],
  "side": "8.535533906"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 3
}

当前第一名的答案

{
  "centers": [
    [
      "7.535533906",
      "1"
    ],
    [
      "6.535533906",
      "6.535533906"
    ],
    [
      "3",
      "3"
    ]
  ],
  "side": "8.535533906"
}

提交 side 与 centers,centers 按半径 1,2,…,n 的顺序排列。每个数写成十进制字符串,例如 "3.5"。 · 验证器 v1.0.0