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

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

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

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

严格定义

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

帮助理解

哪里有优化空间

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

前沿在哪里

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

查看来源
当前第一名

159.037470501

正方形边长

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

答案怎么写

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

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

当前第一名的答案

{
  "centers": [
    [
      "1.883639801",
      "157.173551347"
    ],
    [
      "58.518632458",
      "117.403369173"
    ],
    [
      "29.117375287",
      "29.774518115"
    ],
    [
      "33.623065863",
      "4.757924005"
    ],
    [
      "154.035525657",
      "109.209440618"
    ],
    [
      "107.466389942",
      "153.035136688"
    ],
    [
      "37.506282636",
      "75.277913835"
    ],
    [
      "35.089186897",
      "151.037470501"
    ],
    [
      "52.059749646",
      "150.037470501"
    ],
    [
      "10",
      "121.108472922"
    ],
    [
      "148.033191844",
      "61.492474119"
    ],
    [
      "53.424005792",
      "58.799322726"
    ],
    [
      "124.319840259",
      "66.248416319"
    ],
    [
      "14",
      "144.772792055"
    ],
    [
      "91.642002589",
      "15.005834532"
    ],
    [
      "16",
      "16"
    ],
    [
      "142.037470501",
      "90.457620739"
    ],
    [
      "39.477450722",
      "125.410470274"
    ],
    [
      "19",
      "93.540375417"
    ],
    [
      "105.390700601",
      "95.558037973"
    ],
    [
      "21",
      "52.66060556"
    ],
    [
      "61.285171149",
      "91.878048205"
    ],
    [
      "54.387798984",
      "23.008947012"
    ],
    [
      "89.184248413",
      "54.651425946"
    ],
    [
      "82.059749646",
      "134.037470501"
    ],
    [
      "133.037381573",
      "132.505460775"
    ],
    [
      "132.037470501",
      "27"
    ]
  ],
  "side": "159.037470501"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 27
}

当前第一名的答案

{
  "centers": [
    [
      "1.883639801",
      "157.173551347"
    ],
    [
      "58.518632458",
      "117.403369173"
    ],
    [
      "29.117375287",
      "29.774518115"
    ],
    [
      "33.623065863",
      "4.757924005"
    ],
    [
      "154.035525657",
      "109.209440618"
    ],
    [
      "107.466389942",
      "153.035136688"
    ],
    [
      "37.506282636",
      "75.277913835"
    ],
    [
      "35.089186897",
      "151.037470501"
    ],
    [
      "52.059749646",
      "150.037470501"
    ],
    [
      "10",
      "121.108472922"
    ],
    [
      "148.033191844",
      "61.492474119"
    ],
    [
      "53.424005792",
      "58.799322726"
    ],
    [
      "124.319840259",
      "66.248416319"
    ],
    [
      "14",
      "144.772792055"
    ],
    [
      "91.642002589",
      "15.005834532"
    ],
    [
      "16",
      "16"
    ],
    [
      "142.037470501",
      "90.457620739"
    ],
    [
      "39.477450722",
      "125.410470274"
    ],
    [
      "19",
      "93.540375417"
    ],
    [
      "105.390700601",
      "95.558037973"
    ],
    [
      "21",
      "52.66060556"
    ],
    [
      "61.285171149",
      "91.878048205"
    ],
    [
      "54.387798984",
      "23.008947012"
    ],
    [
      "89.184248413",
      "54.651425946"
    ],
    [
      "82.059749646",
      "134.037470501"
    ],
    [
      "133.037381573",
      "132.505460775"
    ],
    [
      "132.037470501",
      "27"
    ]
  ],
  "side": "159.037470501"
}

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