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

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

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

子题n = 20

目标最小化正方形边长

已知最好（未证明）103.117653256值取自 Packomania（Eckard Specht）的 csqn 汇总表，该表未把这一项标为已证明最优

严格定义

容器边长 side 的正方形，左下角是原点，side 由你给出，它就是分数；单位取最小圆的半径
提交side 与 centers，centers 按半径 1, 2, …, n 的顺序排列
约束第 i 个圆的半径恰好是 i；两两内部不重叠；每个圆完整落在正方形内
目标让正方形边长尽可能小

放大来摆，然后提交 ↗

103.117653256y0

1234567891011121314151617181920

0x103.117653256

已验证构造side = 103.117653256

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源

当前第一名

103.117653256

正方形边长

已追平已知最好

纪录保持者创始基准

解题方式人工

挑战这个纪录 ↗

ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "31.468749508",
      "25.820077876"
    ],
    [
      "2.118705603",
      "49.609400041"
    ],
    [
      "32.19362125",
      "3.526421075"
    ],
    [
      "86.994705511",
      "60.570935891"
    ],
    [
      "67.448032745",
      "5.001909266"
    ],
    [
      "97.064919069",
      "62.19717426"
    ],
    [
      "59.595193275",
      "95.939432915"
    ],
    [
      "8.085241368",
      "39.170936704"
    ],
    [
      "56.542797374",
      "79.256858764"
    ],
    [
      "93.114049335",
      "46.595688351"
    ],
    [
      "41.226140916",
      "92.117653256"
    ],
    [
      "12",
      "60.424118924"
    ],
    [
      "35.556197903",
      "68.797024057"
    ],
    [
      "30.568649182",
      "42.225073137"
    ],
    [
      "15.049361899",
      "88.068150241"
    ],
    [
      "16",
      "16"
    ],
    [
      "48.984845005",
      "17"
    ],
    [
      "85.109671286",
      "19.751460358"
    ],
    [
      "84.117653256",
      "84.117653256"
    ],
    [
      "63.395802446",
      "51.078208663"
    ]
  ],
  "side": "103.117653256"
}

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

子题参数

{
  "n": 20
}

当前第一名的答案

{
  "centers": [
    [
      "31.468749508",
      "25.820077876"
    ],
    [
      "2.118705603",
      "49.609400041"
    ],
    [
      "32.19362125",
      "3.526421075"
    ],
    [
      "86.994705511",
      "60.570935891"
    ],
    [
      "67.448032745",
      "5.001909266"
    ],
    [
      "97.064919069",
      "62.19717426"
    ],
    [
      "59.595193275",
      "95.939432915"
    ],
    [
      "8.085241368",
      "39.170936704"
    ],
    [
      "56.542797374",
      "79.256858764"
    ],
    [
      "93.114049335",
      "46.595688351"
    ],
    [
      "41.226140916",
      "92.117653256"
    ],
    [
      "12",
      "60.424118924"
    ],
    [
      "35.556197903",
      "68.797024057"
    ],
    [
      "30.568649182",
      "42.225073137"
    ],
    [
      "15.049361899",
      "88.068150241"
    ],
    [
      "16",
      "16"
    ],
    [
      "48.984845005",
      "17"
    ],
    [
      "85.109671286",
      "19.751460358"
    ],
    [
      "84.117653256",
      "84.117653256"
    ],
    [
      "63.395802446",
      "51.078208663"
    ]
  ],
  "side": "103.117653256"
}

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