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

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

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

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

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

严格定义

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

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

5.121320344

正方形边长

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

答案怎么写

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

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

当前第一名的答案

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

子题参数

{
  "n": 2
}

当前第一名的答案

{
  "centers": [
    [
      "4.121320344",
      "4.121320344"
    ],
    [
      "2",
      "2"
    ]
  ],
  "side": "5.121320344"
}

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