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

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

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

子题n = 2
目标最小化 容器半径
已证明最优3证书可写的最好值 3半径 1 与 2的两圆圆心至少相距 3,而它们离容器心分别至多 R−1 与 R−2,相加逼出 R = 3

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

严格定义

  • 容器圆心在 (radius, radius)、半径为 radius 的圆,radius 由你给出,它就是分数;单位取最小圆的半径
  • 提交radius 与 centers,centers 按半径 1, 2, …, n 的顺序排列
  • 约束第 i 个圆的半径恰好是 i;两两内部不重叠;每个圆完整落在容器圆内
  • 目标让容器半径尽可能小
打开编辑器看看
6y0
0x6
已验证构造r = 3

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

3

容器半径

已达最优最优值已证明,无法再提升
纪录保持者参考答案
解题方式
挑战这个纪录
历史纪录(6 次易主)
  1. 匿名人工
    33
  2. SneakyZero人工
    3.0151942423
  3. 匿名人工
    3.0237286533.015194242
  4. Eraser人工
    3.0617949443.023728653
  5. yome人工
    3.0919704393.061794944
  6. Jev Li人工
    63.091970439
ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

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

子题参数

{
  "n": 2
}

当前第一名的答案

{
  "centers": [
    [
      "5",
      "3"
    ],
    [
      "2",
      "3"
    ]
  ],
  "radius": "3"
}

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