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

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

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

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

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

纪录对比

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

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

严格定义

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

当前展示:本站纪录

742.323117936y0
0x742.323117936
已验证构造side = 742.323117936

帮助理解

角位分配与小圆填隙

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

已知证明与开放前沿

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

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

纪录详情

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

纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
纪录保持者的求解笔记暂无求解笔记(点击展开)+

纪录保持者暂未分享求解过程。

历史纪录(4 次易主)
  1. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    742.323117937→742.323117936
  2. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    742.323117939→742.323117937
  3. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    742.32311794→742.323117939
  4. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    892→742.32311794
ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "111.856682932",
      "736.098585095"
    ],
    [
      "97.910430908",
      "737.593942533"
    ],
    [
      "247.906704566",
      "91.155459866"
    ],
    [
      "282.348873177",
      "733.252514009"
    ],
    [
      "678.920292241",
      "610.606556323"
    ],
    [
      "6.601071074",
      "366.217048584"
    ],
    [
      "7.126716635",
      "232.480406766"
    ],
    [
      "387.870022560",
      "221.254348335"
    ],
    [
      "442.859139658",
      "9.068764394"
    ],
    [
      "514.731313048",
      "731.737566241"
    ],
    [
      "135.980963958",
      "244.154317846"
    ],
    [
      "12.091686273",
      "348.930547227"
    ],
    [
      "639.132657539",
      "13.678043422"
    ],
    [
      "623.456296872",
      "728.216151102"
    ],
    [
      "727.323117931",
      "104.732824800"
    ],
    [
      "16.003380355",
      "726.319769993"
    ],
    [
      "725.290453566",
      "241.782785374"
    ],
    [
      "18.002950733",
      "583.589981984"
    ],
    [
      "104.184126783",
      "440.139909636"
    ],
    [
      "423.107613001",
      "656.887212611"
    ],
    [
      "152.242197840",
      "721.319675414"
    ],
    [
      "329.318857058",
      "104.996818738"
    ],
    [
      "356.070599594",
      "439.679955447"
    ],
    [
      "468.979286281",
      "490.278109777"
    ],
    [
      "215.504647357",
      "25.000000000"
    ],
    [
      "387.472507690",
      "317.746090530"
    ],
    [
      "254.579102187",
      "585.279352992"
    ],
    [
      "714.269317796",
      "392.952555541"
    ],
    [
      "29.055721572",
      "133.500951079"
    ],
    [
      "712.265474929",
      "596.886895014"
    ],
    [
      "31.024343690",
      "195.385923213"
    ],
    [
      "648.076223838",
      "486.963686107"
    ],
    [
      "321.423854488",
      "709.309511319"
    ],
    [
      "210.131563029",
      "83.754829293"
    ],
    [
      "707.323117936",
      "455.677818048"
    ],
    [
      "480.070831482",
      "36.000000000"
    ],
    [
      "392.885382159",
      "705.317710252"
    ],
    [
      "704.323117936",
      "528.632462245"
    ],
    [
      "221.403902613",
      "397.086864333"
    ],
    [
      "469.839208992",
      "702.316553910"
    ],
    [
      "148.184396629",
      "41.022034583"
    ],
    [
      "554.344662983",
      "173.140353316"
    ],
    [
      "586.284048299",
      "251.911386483"
    ],
    [
      "642.837330263",
      "410.042489751"
    ],
    [
      "139.617681682",
      "377.780142222"
    ],
    [
      "165.417230502",
      "465.046305662"
    ],
    [
      "394.403768136",
      "506.834784784"
    ],
    [
      "48.000000000",
      "403.386283162"
    ],
    [
      "285.504647361",
      "49.000000001"
    ],
    [
      "692.261488055",
      "50.000000001"
    ],
    [
      "378.823078096",
      "162.385825393"
    ],
    [
      "474.327471692",
      "123.812378507"
    ],
    [
      "336.293722290",
      "257.292378886"
    ],
    [
      "54.000000000",
      "54.000000001"
    ],
    [
      "173.811666076",
      "565.696856838"
    ],
    [
      "390.271054195",
      "56.000000001"
    ],
    [
      "565.376612115",
      "685.323117936"
    ],
    [
      "560.668045874",
      "349.608983285"
    ],
    [
      "315.137622053",
      "367.276102335"
    ],
    [
      "682.323117935",
      "681.785494737"
    ],
    [
      "266.849227110",
      "159.965764085"
    ],
    [
      "617.577298035",
      "578.383469578"
    ],
    [
      "554.522012814",
      "470.452792720"
    ],
    [
      "678.251766454",
      "307.882814870"
    ],
    [
      "65.000000001",
      "515.100203517"
    ],
    [
      "577.429365765",
      "66.419003979"
    ],
    [
      "227.347475394",
      "675.323117935"
    ],
    [
      "346.160849112",
      "611.226454783"
    ],
    [
      "69.000000001",
      "288.286326598"
    ],
    [
      "278.485767511",
      "490.959737308"
    ],
    [
      "441.317004750",
      "398.561296655"
    ],
    [
      "483.762313322",
      "585.422636285"
    ],
    [
      "669.323117934",
      "170.914393234"
    ],
    [
      "211.988594677",
      "283.316122863"
    ],
    [
      "130.325267750",
      "157.997372586"
    ],
    [
      "466.967452384",
      "253.816505597"
    ],
    [
      "78.171697337",
      "657.126919004"
    ]
  ],
  "side": "742.323117936"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 77
}

当前第一名的答案

{
  "centers": [
    [
      "111.856682932",
      "736.098585095"
    ],
    [
      "97.910430908",
      "737.593942533"
    ],
    [
      "247.906704566",
      "91.155459866"
    ],
    [
      "282.348873177",
      "733.252514009"
    ],
    [
      "678.920292241",
      "610.606556323"
    ],
    [
      "6.601071074",
      "366.217048584"
    ],
    [
      "7.126716635",
      "232.480406766"
    ],
    [
      "387.870022560",
      "221.254348335"
    ],
    [
      "442.859139658",
      "9.068764394"
    ],
    [
      "514.731313048",
      "731.737566241"
    ],
    [
      "135.980963958",
      "244.154317846"
    ],
    [
      "12.091686273",
      "348.930547227"
    ],
    [
      "639.132657539",
      "13.678043422"
    ],
    [
      "623.456296872",
      "728.216151102"
    ],
    [
      "727.323117931",
      "104.732824800"
    ],
    [
      "16.003380355",
      "726.319769993"
    ],
    [
      "725.290453566",
      "241.782785374"
    ],
    [
      "18.002950733",
      "583.589981984"
    ],
    [
      "104.184126783",
      "440.139909636"
    ],
    [
      "423.107613001",
      "656.887212611"
    ],
    [
      "152.242197840",
      "721.319675414"
    ],
    [
      "329.318857058",
      "104.996818738"
    ],
    [
      "356.070599594",
      "439.679955447"
    ],
    [
      "468.979286281",
      "490.278109777"
    ],
    [
      "215.504647357",
      "25.000000000"
    ],
    [
      "387.472507690",
      "317.746090530"
    ],
    [
      "254.579102187",
      "585.279352992"
    ],
    [
      "714.269317796",
      "392.952555541"
    ],
    [
      "29.055721572",
      "133.500951079"
    ],
    [
      "712.265474929",
      "596.886895014"
    ],
    [
      "31.024343690",
      "195.385923213"
    ],
    [
      "648.076223838",
      "486.963686107"
    ],
    [
      "321.423854488",
      "709.309511319"
    ],
    [
      "210.131563029",
      "83.754829293"
    ],
    [
      "707.323117936",
      "455.677818048"
    ],
    [
      "480.070831482",
      "36.000000000"
    ],
    [
      "392.885382159",
      "705.317710252"
    ],
    [
      "704.323117936",
      "528.632462245"
    ],
    [
      "221.403902613",
      "397.086864333"
    ],
    [
      "469.839208992",
      "702.316553910"
    ],
    [
      "148.184396629",
      "41.022034583"
    ],
    [
      "554.344662983",
      "173.140353316"
    ],
    [
      "586.284048299",
      "251.911386483"
    ],
    [
      "642.837330263",
      "410.042489751"
    ],
    [
      "139.617681682",
      "377.780142222"
    ],
    [
      "165.417230502",
      "465.046305662"
    ],
    [
      "394.403768136",
      "506.834784784"
    ],
    [
      "48.000000000",
      "403.386283162"
    ],
    [
      "285.504647361",
      "49.000000001"
    ],
    [
      "692.261488055",
      "50.000000001"
    ],
    [
      "378.823078096",
      "162.385825393"
    ],
    [
      "474.327471692",
      "123.812378507"
    ],
    [
      "336.293722290",
      "257.292378886"
    ],
    [
      "54.000000000",
      "54.000000001"
    ],
    [
      "173.811666076",
      "565.696856838"
    ],
    [
      "390.271054195",
      "56.000000001"
    ],
    [
      "565.376612115",
      "685.323117936"
    ],
    [
      "560.668045874",
      "349.608983285"
    ],
    [
      "315.137622053",
      "367.276102335"
    ],
    [
      "682.323117935",
      "681.785494737"
    ],
    [
      "266.849227110",
      "159.965764085"
    ],
    [
      "617.577298035",
      "578.383469578"
    ],
    [
      "554.522012814",
      "470.452792720"
    ],
    [
      "678.251766454",
      "307.882814870"
    ],
    [
      "65.000000001",
      "515.100203517"
    ],
    [
      "577.429365765",
      "66.419003979"
    ],
    [
      "227.347475394",
      "675.323117935"
    ],
    [
      "346.160849112",
      "611.226454783"
    ],
    [
      "69.000000001",
      "288.286326598"
    ],
    [
      "278.485767511",
      "490.959737308"
    ],
    [
      "441.317004750",
      "398.561296655"
    ],
    [
      "483.762313322",
      "585.422636285"
    ],
    [
      "669.323117934",
      "170.914393234"
    ],
    [
      "211.988594677",
      "283.316122863"
    ],
    [
      "130.325267750",
      "157.997372586"
    ],
    [
      "466.967452384",
      "253.816505597"
    ],
    [
      "78.171697337",
      "657.126919004"
    ]
  ],
  "side": "742.323117936"
}

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

DISCUSSION

讨论区

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

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