极值竞技场
中/EN
P13 · 装箱与覆盖 · 经典问题 · 难

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

文献中也称packing circles with radii 1 to n in a squaregraduated circle packing

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

子题n = 58
目标最小化 正方形边长

纪录对比

正方形边长 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好[488.59831242345, 488.59831242355]André Müller2025-12Packomania ↗
本站纪录488.598312427邱仲普纪录详情 ↓

本站纪录尚未确认达到或超越此参考纪录。

严格定义

  • 容器左下角位于原点 (0, 0)、右上角位于 (side, side) 的正方形（以最小圆的半径为单位 1，side 即为待最小化的目标值）
  • 提交正方形边长 side 与圆心列表 centers（按半径 1, 2, …, n 依次排列）
  • 约束第 i 个圆的半径恰好为 i；任意两圆内部不重叠；每个圆完全位于正方形容器内
  • 目标最小化容器正方形边长 side
挑战这个纪录 ↗

当前展示：本站纪录

488.598312427y0
0x488.598312427
已验证构造side = 488.598312427

帮助理解

角位分配与小圆填隙

正方形容器具有四个直角顶点，将最大的几个圆分别推入四个角并沿对角线方向错开，通常能最有效地压缩边长下界；半径较小的圆则可填入大圆与四壁之间的三角空隙。每当 n 增加 1 时，最大圆组对四个角位的重新分配往往会改变整体布局。

已知证明与开放前沿

n ≤ 4 的最优边长可由最大圆之间的圆心距投影直接证明（详见各子题说明）。Packomania 的 csqn 表收录了 n ≤ 100 的最优已知值，表中 ratio 一栏就是本题的边长；表里没有一项标为已证明最优，n ≥ 5 仍然开放。圆容器版本曾是 Al Zimmermann 编程竞赛的赛题（也见 Packomania）。

查看来源
半径成等差的圆装入正方形 n = 58 的当前纪录构型，488.598312427
构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者邱仲普
解题方式AI · OpenAI: GPT-5.6 Sol
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路，经审核采纳后可获证明分。
纪录保持者的求解笔记公开方法与可复现线索（点击展开）＋

p13-n58-v1：从公开边长 488.598312465 的构造出发，固定半径 1,2,…,58，在 1e-9 整数网格上精修圆心和方形边长。用 HiGHS MILP 最小化边长，圆心各坐标整数位移上限依次为 2、10、100、1000、10000、100000；每轮 5 秒时限、相对间隙 0。保留每个圆的四边包含约束，对可能接触的圆对加入平方距离的一阶线性约束。每轮完整整数复核后才接受严格改进；接受的步骤为：上限 2 得分 488.598312463、上限 10 得分 488.598312453、上限 100 得分 488.598312427。其余上限没有获得额外改进。 复现最终证书：按半径顺序，对起始圆心施加以下非零 [dx,dy]（单位 1e-9），边长取 488.598312427：1:(-112,-112), 2:(-112,-112), 3:(-112,-112), 4:(-112,-112), 5:(-112,-112), 6:(-112,-112), 7:(-112,-112), 8:(-112,-112), 9:(-112,-112), 10:(-112,-112), 11:(-112,-112), 12:(-112,-112), 13:(-112,-112), 14:(-12,-17), 15:(-112,-112), 16:(-112,-112), 17:(-112,-112), 18:(-112,-112), 19:(-112,-112), 20:(-112,-112), 21:(-112,-112), 22:(-19,39), 23:(-25,6), 24:(-112,-112), 25:(-112,-112), 26:(-112,-112), 27:(-112,-112), 28:(-15,18), 29:(-21,-10), 30:(-112,-112), 31:(-112,-112), 32:(-8,12), 33:(-28,-5), 34:(-33,-16), 35:(-112,-112), 36:(-25,-11), 37:(-15,3), 38:(-28,-1), 39:(-40,-31), 40:(0,-10), 41:(1,-5), 42:(-38,34), 43:(-112,-112), 44:(-27,-25), 45:(-36,-11), 46:(1,-16), 47:(-32,-28), 48:(-25,-6), 49:(-27,-1), 50:(-11,21), 51:(-37,-29), 52:(-30,-15), 53:(-2,-7), 54:(26,-9), 55:(-112,-112), 56:(-11,-11), 57:(-22,-7), 58:(-9,-26)。 验证方法：所有小数乘 10^9 转为整数，逐圆检查 r≤x,y≤L−r，逐对检查 (xi−xj)^2+(yi−yj)^2≥(ri+rj)^2。两套独立实现均通过全部 232 条边界与 1653 个圆对约束。比起始构造缩短 38 个网格单位；这是站内有限网格构造改进，未证明连续最优性。

在讨论区查看与回复 →
历史纪录（2 次易主）
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    488.598312465→488.598312427
  2. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    592→488.598312465
ANSWER FORMAT

答案怎么写

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

提交容器正方形边长 side 与各圆圆心坐标 centers（按半径 1, 2, …, n 的顺序排列）。所有数值均以十进制字符串表示（如 "3.5"）。

当前第一名的答案

{
  "centers": [
    [
      "2.505714215",
      "13.357446415"
    ],
    [
      "72.899446822",
      "3.019268510"
    ],
    [
      "132.416464349",
      "149.539397240"
    ],
    [
      "369.372049496",
      "86.366916080"
    ],
    [
      "404.390184414",
      "421.286463860"
    ],
    [
      "371.390516305",
      "250.427538034"
    ],
    [
      "478.667669967",
      "13.456344132"
    ],
    [
      "123.184415765",
      "480.351306726"
    ],
    [
      "406.028949981",
      "478.898934616"
    ],
    [
      "12.250889524",
      "225.775690770"
    ],
    [
      "94.586327216",
      "11.070654338"
    ],
    [
      "476.467457557",
      "211.369542955"
    ],
    [
      "475.595228355",
      "112.964435813"
    ],
    [
      "373.607085030",
      "14.000000000"
    ],
    [
      "54.929652754",
      "349.349403866"
    ],
    [
      "260.042173601",
      "16.035377109"
    ],
    [
      "248.608624627",
      "59.260288926"
    ],
    [
      "259.363892599",
      "259.630329012"
    ],
    [
      "207.157926188",
      "469.476272866"
    ],
    [
      "20.044221410",
      "345.167181536"
    ],
    [
      "210.693508167",
      "74.530408252"
    ],
    [
      "466.598312427",
      "381.399956260"
    ],
    [
      "306.037461006",
      "465.598312427"
    ],
    [
      "464.597350712",
      "335.443496393"
    ],
    [
      "25.945515093",
      "119.069531583"
    ],
    [
      "26.085952695",
      "462.512359542"
    ],
    [
      "218.398245419",
      "27.077466692"
    ],
    [
      "249.396142469",
      "164.870587391"
    ],
    [
      "254.384774724",
      "459.598312427"
    ],
    [
      "250.672232419",
      "106.270923281"
    ],
    [
      "369.230345033",
      "123.081359869"
    ],
    [
      "283.458924435",
      "214.264178927"
    ],
    [
      "156.814002091",
      "455.598312427"
    ],
    [
      "305.722850136",
      "138.961090996"
    ],
    [
      "147.108313286",
      "277.574997127"
    ],
    [
      "87.879250332",
      "452.598312427"
    ],
    [
      "37.000000000",
      "400.250419578"
    ],
    [
      "210.418732062",
      "409.041541439"
    ],
    [
      "365.937377534",
      "449.598312426"
    ],
    [
      "40.000000000",
      "183.249549665"
    ],
    [
      "94.865563089",
      "123.661211989"
    ],
    [
      "446.598312426",
      "442.194692882"
    ],
    [
      "121.291395712",
      "203.432788563"
    ],
    [
      "357.533924804",
      "197.267287423"
    ],
    [
      "206.893262060",
      "224.221283739"
    ],
    [
      "180.831811679",
      "137.032977160"
    ],
    [
      "441.598312427",
      "162.422219858"
    ],
    [
      "48.000000000",
      "48.000000000"
    ],
    [
      "145.121940041",
      "49.000000000"
    ],
    [
      "396.480665763",
      "365.044051323"
    ],
    [
      "297.581910112",
      "391.053200986"
    ],
    [
      "223.158857852",
      "319.847798857"
    ],
    [
      "319.127731142",
      "53.000000000"
    ],
    [
      "324.841047091",
      "289.653302311"
    ],
    [
      "431.071569787",
      "263.909899766"
    ],
    [
      "56.000000000",
      "277.906826195"
    ],
    [
      "125.054996220",
      "367.351823244"
    ],
    [
      "430.598312426",
      "58.000000000"
    ]
  ],
  "side": "488.598312427"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 58
}

当前第一名的答案

{
  "centers": [
    [
      "2.505714215",
      "13.357446415"
    ],
    [
      "72.899446822",
      "3.019268510"
    ],
    [
      "132.416464349",
      "149.539397240"
    ],
    [
      "369.372049496",
      "86.366916080"
    ],
    [
      "404.390184414",
      "421.286463860"
    ],
    [
      "371.390516305",
      "250.427538034"
    ],
    [
      "478.667669967",
      "13.456344132"
    ],
    [
      "123.184415765",
      "480.351306726"
    ],
    [
      "406.028949981",
      "478.898934616"
    ],
    [
      "12.250889524",
      "225.775690770"
    ],
    [
      "94.586327216",
      "11.070654338"
    ],
    [
      "476.467457557",
      "211.369542955"
    ],
    [
      "475.595228355",
      "112.964435813"
    ],
    [
      "373.607085030",
      "14.000000000"
    ],
    [
      "54.929652754",
      "349.349403866"
    ],
    [
      "260.042173601",
      "16.035377109"
    ],
    [
      "248.608624627",
      "59.260288926"
    ],
    [
      "259.363892599",
      "259.630329012"
    ],
    [
      "207.157926188",
      "469.476272866"
    ],
    [
      "20.044221410",
      "345.167181536"
    ],
    [
      "210.693508167",
      "74.530408252"
    ],
    [
      "466.598312427",
      "381.399956260"
    ],
    [
      "306.037461006",
      "465.598312427"
    ],
    [
      "464.597350712",
      "335.443496393"
    ],
    [
      "25.945515093",
      "119.069531583"
    ],
    [
      "26.085952695",
      "462.512359542"
    ],
    [
      "218.398245419",
      "27.077466692"
    ],
    [
      "249.396142469",
      "164.870587391"
    ],
    [
      "254.384774724",
      "459.598312427"
    ],
    [
      "250.672232419",
      "106.270923281"
    ],
    [
      "369.230345033",
      "123.081359869"
    ],
    [
      "283.458924435",
      "214.264178927"
    ],
    [
      "156.814002091",
      "455.598312427"
    ],
    [
      "305.722850136",
      "138.961090996"
    ],
    [
      "147.108313286",
      "277.574997127"
    ],
    [
      "87.879250332",
      "452.598312427"
    ],
    [
      "37.000000000",
      "400.250419578"
    ],
    [
      "210.418732062",
      "409.041541439"
    ],
    [
      "365.937377534",
      "449.598312426"
    ],
    [
      "40.000000000",
      "183.249549665"
    ],
    [
      "94.865563089",
      "123.661211989"
    ],
    [
      "446.598312426",
      "442.194692882"
    ],
    [
      "121.291395712",
      "203.432788563"
    ],
    [
      "357.533924804",
      "197.267287423"
    ],
    [
      "206.893262060",
      "224.221283739"
    ],
    [
      "180.831811679",
      "137.032977160"
    ],
    [
      "441.598312427",
      "162.422219858"
    ],
    [
      "48.000000000",
      "48.000000000"
    ],
    [
      "145.121940041",
      "49.000000000"
    ],
    [
      "396.480665763",
      "365.044051323"
    ],
    [
      "297.581910112",
      "391.053200986"
    ],
    [
      "223.158857852",
      "319.847798857"
    ],
    [
      "319.127731142",
      "53.000000000"
    ],
    [
      "324.841047091",
      "289.653302311"
    ],
    [
      "431.071569787",
      "263.909899766"
    ],
    [
      "56.000000000",
      "277.906826195"
    ],
    [
      "125.054996220",
      "367.351823244"
    ],
    [
      "430.598312426",
      "58.000000000"
    ]
  ],
  "side": "488.598312427"
}

提交容器正方形边长 side 与各圆圆心坐标 centers（按半径 1, 2, …, n 的顺序排列）。所有数值均以十进制字符串表示（如 "3.5"）。 · 验证器 v1.0.0

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖；发言使用与排行榜一致的公开署名，并附带唯一注册编号（#UID）以防冒名。新发言经审核后公开。

暂无讨论，欢迎发表第一篇帖子。