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

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

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

子题n = 30
目标最小化 正方形边长
已知最好（未证明）185.66254565值取自 Packomania（Eckard Specht）的 csqn 汇总表，该表未把这一项标为已证明最优

严格定义

  • 容器边长 side 的正方形，左下角是原点，side 由你给出，它就是分数；单位取最小圆的半径
  • 提交side 与 centers，centers 按半径 1, 2, …, n 的顺序排列
  • 约束第 i 个圆的半径恰好是 i；两两内部不重叠；每个圆完整落在正方形内
  • 目标让正方形边长尽可能小
放大来摆，然后提交 ↗
185.66254565y0
0x185.66254565
已验证构造side = 185.66254565

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

185.66254565

正方形边长

已追平已知最好
纪录保持者创始基准
解题方式人工
挑战这个纪录 ↗
ANSWER FORMAT

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "79.690820494",
      "140.795706193"
    ],
    [
      "38.215097515",
      "71.632515669"
    ],
    [
      "105.729221638",
      "182.629932702"
    ],
    [
      "80.743161751",
      "181.645815349"
    ],
    [
      "133.615065855",
      "5.033913247"
    ],
    [
      "179.586857698",
      "55.092719205"
    ],
    [
      "37.094050777",
      "43.532501059"
    ],
    [
      "125.093736102",
      "148.574699434"
    ],
    [
      "47.521397413",
      "31.394685147"
    ],
    [
      "47.396432256",
      "10.001043337"
    ],
    [
      "94.081211417",
      "174.587365688"
    ],
    [
      "12",
      "92.41912227"
    ],
    [
      "37.106871784",
      "88.604567532"
    ],
    [
      "119.384615392",
      "171.593340921"
    ],
    [
      "170.532737056",
      "117.752790532"
    ],
    [
      "115.246038784",
      "16.015464942"
    ],
    [
      "100.158923263",
      "146.734717736"
    ],
    [
      "18",
      "167.66254565"
    ],
    [
      "19",
      "62.219784528"
    ],
    [
      "20.002086674",
      "22.237488891"
    ],
    [
      "58.981287913",
      "60.996421608"
    ],
    [
      "77.099761961",
      "22"
    ],
    [
      "162.660145974",
      "78.822782668"
    ],
    [
      "24.52035203",
      "126.171763427"
    ],
    [
      "60.426406872",
      "160.66254565"
    ],
    [
      "129.157245115",
      "114.634858448"
    ],
    [
      "158.66254565",
      "158.66254565"
    ],
    [
      "157.66254565",
      "28"
    ],
    [
      "74.497328561",
      "108.528016181"
    ],
    [
      "110.542826898",
      "61.819108576"
    ]
  ],
  "side": "185.66254565"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 30
}

当前第一名的答案

{
  "centers": [
    [
      "79.690820494",
      "140.795706193"
    ],
    [
      "38.215097515",
      "71.632515669"
    ],
    [
      "105.729221638",
      "182.629932702"
    ],
    [
      "80.743161751",
      "181.645815349"
    ],
    [
      "133.615065855",
      "5.033913247"
    ],
    [
      "179.586857698",
      "55.092719205"
    ],
    [
      "37.094050777",
      "43.532501059"
    ],
    [
      "125.093736102",
      "148.574699434"
    ],
    [
      "47.521397413",
      "31.394685147"
    ],
    [
      "47.396432256",
      "10.001043337"
    ],
    [
      "94.081211417",
      "174.587365688"
    ],
    [
      "12",
      "92.41912227"
    ],
    [
      "37.106871784",
      "88.604567532"
    ],
    [
      "119.384615392",
      "171.593340921"
    ],
    [
      "170.532737056",
      "117.752790532"
    ],
    [
      "115.246038784",
      "16.015464942"
    ],
    [
      "100.158923263",
      "146.734717736"
    ],
    [
      "18",
      "167.66254565"
    ],
    [
      "19",
      "62.219784528"
    ],
    [
      "20.002086674",
      "22.237488891"
    ],
    [
      "58.981287913",
      "60.996421608"
    ],
    [
      "77.099761961",
      "22"
    ],
    [
      "162.660145974",
      "78.822782668"
    ],
    [
      "24.52035203",
      "126.171763427"
    ],
    [
      "60.426406872",
      "160.66254565"
    ],
    [
      "129.157245115",
      "114.634858448"
    ],
    [
      "158.66254565",
      "158.66254565"
    ],
    [
      "157.66254565",
      "28"
    ],
    [
      "74.497328561",
      "108.528016181"
    ],
    [
      "110.542826898",
      "61.819108576"
    ]
  ],
  "side": "185.66254565"
}

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