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

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

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

子题n = 24

目标最小化容器半径

已知最好（未证明）75.749142584值由 Packomania（Eckard Specht）ccin 坐标文件反推（表页只印四位小数，文件带十二位半径），该表未把这一项标为已证明最优

严格定义

容器圆心在 (radius, radius)、半径为 radius 的圆，radius 由你给出，它就是分数；单位取最小圆的半径
提交radius 与 centers，centers 按半径 1, 2, …, n 的顺序排列
约束第 i 个圆的半径恰好是 i；两两内部不重叠；每个圆完整落在容器圆内
目标让容器半径尽可能小

放大来摆，然后提交 ↗

151.498285168y0

123456789101112131415161718192021222324

0x151.498285168

已验证构造r = 75.749142584

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源

当前第一名

75.749142584

容器半径

已追平已知最好

纪录保持者创始基准

解题方式人工

挑战这个纪录 ↗

ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "37.420787944",
      "16.43626666"
    ],
    [
      "25.185578463",
      "59.882186741"
    ],
    [
      "32.114405114",
      "18.039228702"
    ],
    [
      "140.627408985",
      "105.866644993"
    ],
    [
      "123.040414281",
      "23.239466511"
    ],
    [
      "75.918414956",
      "6.000205402"
    ],
    [
      "42.753979229",
      "135.977813061"
    ],
    [
      "101.849823518",
      "138.253387659"
    ],
    [
      "90.030975188",
      "101.836959098"
    ],
    [
      "11.648323085",
      "61.12478"
    ],
    [
      "139.491940951",
      "64.394448558"
    ],
    [
      "12.426990071",
      "83.115157875"
    ],
    [
      "137.230225775",
      "88.291073946"
    ],
    [
      "127.677612846",
      "42.336710974"
    ],
    [
      "37.436123288",
      "72.939537218"
    ],
    [
      "57.960776427",
      "18.709383916"
    ],
    [
      "65.114480604",
      "88.999068232"
    ],
    [
      "30.250557468",
      "40.189739382"
    ],
    [
      "64.974977226",
      "52.999338527"
    ],
    [
      "116.40598219",
      "113.89345136"
    ],
    [
      "32.494406936",
      "109.312462706"
    ],
    [
      "95.683318022",
      "25.833223499"
    ],
    [
      "72.150489295",
      "128.375388296"
    ],
    [
      "103.656280041",
      "71.781159862"
    ]
  ],
  "radius": "75.749142584"
}

提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 24
}

当前第一名的答案

{
  "centers": [
    [
      "37.420787944",
      "16.43626666"
    ],
    [
      "25.185578463",
      "59.882186741"
    ],
    [
      "32.114405114",
      "18.039228702"
    ],
    [
      "140.627408985",
      "105.866644993"
    ],
    [
      "123.040414281",
      "23.239466511"
    ],
    [
      "75.918414956",
      "6.000205402"
    ],
    [
      "42.753979229",
      "135.977813061"
    ],
    [
      "101.849823518",
      "138.253387659"
    ],
    [
      "90.030975188",
      "101.836959098"
    ],
    [
      "11.648323085",
      "61.12478"
    ],
    [
      "139.491940951",
      "64.394448558"
    ],
    [
      "12.426990071",
      "83.115157875"
    ],
    [
      "137.230225775",
      "88.291073946"
    ],
    [
      "127.677612846",
      "42.336710974"
    ],
    [
      "37.436123288",
      "72.939537218"
    ],
    [
      "57.960776427",
      "18.709383916"
    ],
    [
      "65.114480604",
      "88.999068232"
    ],
    [
      "30.250557468",
      "40.189739382"
    ],
    [
      "64.974977226",
      "52.999338527"
    ],
    [
      "116.40598219",
      "113.89345136"
    ],
    [
      "32.494406936",
      "109.312462706"
    ],
    [
      "95.683318022",
      "25.833223499"
    ],
    [
      "72.150489295",
      "128.375388296"
    ],
    [
      "103.656280041",
      "71.781159862"
    ]
  ],
  "radius": "75.749142584"
}

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