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

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

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

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

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

纪录对比

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

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

严格定义

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

当前展示：本站纪录

392.659873476y0
0x392.659873476
已验证构造side = 392.659873476

帮助理解

角位分配与小圆填隙

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

已知证明与开放前沿

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

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

纪录详情

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

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

P13, n=50: integer-grid local improvement of the public packing. Starting from the prior public certificate with square side 392.659873512, keep circle i's radius fixed at i. Scale all lengths by Q=10^9. Introduce integer center displacements u_i and an integer side reduction delta>=1; minimize the new side by maximizing delta. Bound each displacement component by +/-L and delta by L. The four square containment constraints for every circle are linear and included directly. For a pair with original center difference d and fixed radius sum R, impose the sufficient tangent inequality 2*d dot (u_i-u_j) >= R^2-|d|^2. The omitted quadratic term |u_i-u_j|^2 is nonnegative. Normalize this inequality by 2R, adding a 0.00001 grid-unit numerical margin. Pairs whose normalized original slack exceeds 8L need not be active in the local model; all pairs are checked afterwards. Solve with SciPy/HiGHS milp, integer variables, zero relative MIP gap and a 5-second limit, using L=2,10,100 in that order and retaining each strictly improving verified result. The final side is 392.659873476, a reduction of 36 grid units. Additional searches at L=100,1000,10000 with 8-second limits did not improve it. Every proposed result is parsed back onto the exact grid and accepted only after two independent integer implementations check all 200 containment inequalities and all 1225 circle pairs, without geometric tolerance. Circle radii remain exactly 1 through 50. This improves the certified finite-grid packing; it does not establish global or local optimality. Other contact arrangements and coordinated larger moves are possible next steps, followed by the same exact validation.

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

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "74.900613035",
      "389.591246097"
    ],
    [
      "3.503252805",
      "316.180228983"
    ],
    [
      "345.360469140",
      "130.334517290"
    ],
    [
      "212.916820356",
      "382.843192301"
    ],
    [
      "158.623444566",
      "205.595431407"
    ],
    [
      "143.811287828",
      "386.602610760"
    ],
    [
      "91.414986098",
      "384.128183881"
    ],
    [
      "8.046825418",
      "383.805788658"
    ],
    [
      "382.301443448",
      "222.928187321"
    ],
    [
      "10.058531795",
      "205.481810427"
    ],
    [
      "11.908042070",
      "294.240025966"
    ],
    [
      "298.162505129",
      "380.659873476"
    ],
    [
      "13.000000000",
      "116.252583838"
    ],
    [
      "79.904933395",
      "120.891848196"
    ],
    [
      "15.000000000",
      "88.324103750"
    ],
    [
      "88.395723979",
      "288.977768634"
    ],
    [
      "93.475028223",
      "17.022548806"
    ],
    [
      "86.973600345",
      "202.978839771"
    ],
    [
      "262.614761490",
      "19.111210630"
    ],
    [
      "372.650796708",
      "121.342142374"
    ],
    [
      "51.612505409",
      "100.191690156"
    ],
    [
      "370.659873476",
      "22.000000000"
    ],
    [
      "117.889832023",
      "369.650786261"
    ],
    [
      "263.261075166",
      "63.058527152"
    ],
    [
      "248.510108099",
      "275.127261705"
    ],
    [
      "297.556962196",
      "290.749856843"
    ],
    [
      "159.997274219",
      "83.362776316"
    ],
    [
      "364.659873476",
      "73.974003805"
    ],
    [
      "277.468658078",
      "169.692593336"
    ],
    [
      "138.684895052",
      "30.133175480"
    ],
    [
      "126.606252711",
      "316.344819883"
    ],
    [
      "101.089764899",
      "80.060452013"
    ],
    [
      "173.721071317",
      "359.659873476"
    ],
    [
      "291.902185246",
      "231.016922061"
    ],
    [
      "315.162125773",
      "35.000000000"
    ],
    [
      "189.187332648",
      "292.415581819"
    ],
    [
      "355.659873476",
      "262.257235626"
    ],
    [
      "206.550668563",
      "38.000000000"
    ],
    [
      "307.288915367",
      "108.579973892"
    ],
    [
      "41.263682087",
      "40.000000000"
    ],
    [
      "129.003949510",
      "244.384754221"
    ],
    [
      "42.568013271",
      "162.628575377"
    ],
    [
      "349.642217587",
      "180.017792258"
    ],
    [
      "44.000000000",
      "248.616652539"
    ],
    [
      "223.281957972",
      "119.296149692"
    ],
    [
      "251.555239548",
      "346.137955868"
    ],
    [
      "345.659873476",
      "345.659873474"
    ],
    [
      "212.225328652",
      "211.636557684"
    ],
    [
      "133.202694897",
      "154.482749031"
    ],
    [
      "50.000000000",
      "342.659873476"
    ]
  ],
  "side": "392.659873476"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 50
}

当前第一名的答案

{
  "centers": [
    [
      "74.900613035",
      "389.591246097"
    ],
    [
      "3.503252805",
      "316.180228983"
    ],
    [
      "345.360469140",
      "130.334517290"
    ],
    [
      "212.916820356",
      "382.843192301"
    ],
    [
      "158.623444566",
      "205.595431407"
    ],
    [
      "143.811287828",
      "386.602610760"
    ],
    [
      "91.414986098",
      "384.128183881"
    ],
    [
      "8.046825418",
      "383.805788658"
    ],
    [
      "382.301443448",
      "222.928187321"
    ],
    [
      "10.058531795",
      "205.481810427"
    ],
    [
      "11.908042070",
      "294.240025966"
    ],
    [
      "298.162505129",
      "380.659873476"
    ],
    [
      "13.000000000",
      "116.252583838"
    ],
    [
      "79.904933395",
      "120.891848196"
    ],
    [
      "15.000000000",
      "88.324103750"
    ],
    [
      "88.395723979",
      "288.977768634"
    ],
    [
      "93.475028223",
      "17.022548806"
    ],
    [
      "86.973600345",
      "202.978839771"
    ],
    [
      "262.614761490",
      "19.111210630"
    ],
    [
      "372.650796708",
      "121.342142374"
    ],
    [
      "51.612505409",
      "100.191690156"
    ],
    [
      "370.659873476",
      "22.000000000"
    ],
    [
      "117.889832023",
      "369.650786261"
    ],
    [
      "263.261075166",
      "63.058527152"
    ],
    [
      "248.510108099",
      "275.127261705"
    ],
    [
      "297.556962196",
      "290.749856843"
    ],
    [
      "159.997274219",
      "83.362776316"
    ],
    [
      "364.659873476",
      "73.974003805"
    ],
    [
      "277.468658078",
      "169.692593336"
    ],
    [
      "138.684895052",
      "30.133175480"
    ],
    [
      "126.606252711",
      "316.344819883"
    ],
    [
      "101.089764899",
      "80.060452013"
    ],
    [
      "173.721071317",
      "359.659873476"
    ],
    [
      "291.902185246",
      "231.016922061"
    ],
    [
      "315.162125773",
      "35.000000000"
    ],
    [
      "189.187332648",
      "292.415581819"
    ],
    [
      "355.659873476",
      "262.257235626"
    ],
    [
      "206.550668563",
      "38.000000000"
    ],
    [
      "307.288915367",
      "108.579973892"
    ],
    [
      "41.263682087",
      "40.000000000"
    ],
    [
      "129.003949510",
      "244.384754221"
    ],
    [
      "42.568013271",
      "162.628575377"
    ],
    [
      "349.642217587",
      "180.017792258"
    ],
    [
      "44.000000000",
      "248.616652539"
    ],
    [
      "223.281957972",
      "119.296149692"
    ],
    [
      "251.555239548",
      "346.137955868"
    ],
    [
      "345.659873476",
      "345.659873474"
    ],
    [
      "212.225328652",
      "211.636557684"
    ],
    [
      "133.202694897",
      "154.482749031"
    ],
    [
      "50.000000000",
      "342.659873476"
    ]
  ],
  "side": "392.659873476"
}

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

DISCUSSION

讨论区

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

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