P73 · 极值构型 · 经典问题 · 简单

用 n 个等圆盖住正方形 · n = 35

在边长为 1 的正方形里放 n 个点。取 r 为正方形里离所有点都最远的那个位置到最近的点的距离，把 r 压到最小。等价地说：用 n 个半径 r 的等圆盘盖住整块正方形，让 r 尽可能小。

子题n = 35

目标最小化覆盖半径

已证明下界1/√(π·35)任何布局都不低于 0.095365445401779 · 当前纪录高出下界 28.0%面积下界：n 个半径 r 的圆盘至多盖住 nπr² 的面积，而正方形的面积是 1，所以 r ≥ 1/√(πn)。对每个 n 都成立，且不依赖任何未证明的猜想

严格定义

容器单位正方形，左下角是原点 (0, 0)，右上角是 (1, 1)，闭区间
提交恰好 n 个点的坐标，十进制小数，最多九位；两点不得重合
分数r(P) 是正方形上「到最近提交点的距离」的最大值。验证器精确求出它的平方，再精确开方并向上取整到 10⁻¹⁸。取整方向朝上，所以存下的数绝不会声称一个比实际更紧的覆盖 $r (P) = \max_{x \in K} \min_{i} ‖ x - p_{i} ‖$
为何有限点在自己的最近邻辖区里就是最近点，而 |x − p|² 是凸的，凸多边形上的最大值必在顶点。于是对连续区域的搜索塌缩成有限个有理顶点的枚举，全程整数运算，不碰浮点
目标在所有合法点集 P 中让 r(P) 尽可能小 $\min_{P} r (P)$

放大来摆，然后提交 ↗

1y0

1234567891011121314151617181920212223242526272829303132333435

0x1

已验证构造35 个等圆盘，共同半径 0.122037；标出的那一点是最难够到的位置，半径由它决定

帮助理解

它和填充正好相反

填充禁止重叠，圆会往里缩、躲开边界；覆盖允许重叠，反而必须把圆压进四个角。同样的 n，好的覆盖和好的填充长得完全不一样。

前沿在哪里

网格不是最优解。无限平面上的最优覆盖由 Kershner 在 1939 年解决（正六边形最省），但有边界的正方形会出现完全不同的角落效应。n = 5 与 n = 7 已证明最优；n = 6、8–30 展示的是公开文献中的当前最好构型，仍可能被改进。本站已把 HUT-TCS-A62 的矢量图逐一重建为可验证坐标。n = 31–35 可以挑战，但在找到可公开复现的文献构型前，不冒充已有 SOTA。

查看来源

当前第一名

0.122036869153125

覆盖半径

答案来源MinMax Arena

解题方式本站参考构造

挑战这个纪录 ↗

ANSWER FORMAT

答案怎么写

容器是边长 1 的正方形：左下角是原点 (0, 0)，右上角是 (1, 1)。你交的是 n 个圆心；半径不用你写，它就是「最难够到的那个位置离最近圆心的距离」，也就是你的分数。坐标写成小数，例如 "0.25"，最多九位小数。

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是盖住整块正方形所需的共同半径，越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.105975452",
      "0.060516122"
    ],
    [
      "0.680876337",
      "0.941630523"
    ],
    [
      "0.756591401",
      "0.762888737"
    ],
    [
      "0.738026408",
      "0.069252543"
    ],
    [
      "0.468080705",
      "0.938870571"
    ],
    [
      "0.030260377",
      "0.239257905"
    ],
    [
      "0.676371611",
      "0.585358525"
    ],
    [
      "0.261973595",
      "0.930747458"
    ],
    [
      "0.323628382",
      "0.414641473"
    ],
    [
      "0.970790871",
      "0.412720531"
    ],
    [
      "0.244923308",
      "0.590118270"
    ],
    [
      "0.969739614",
      "0.760742088"
    ],
    [
      "0.531919301",
      "0.061129432"
    ],
    [
      "0.543940340",
      "0.764131672"
    ],
    [
      "0.327529775",
      "0.765247989"
    ],
    [
      "0.755076688",
      "0.409881733"
    ],
    [
      "0.919255324",
      "0.091505709"
    ],
    [
      "0.456059658",
      "0.235868327"
    ],
    [
      "0.891369611",
      "0.238621092"
    ],
    [
      "0.319123669",
      "0.058369476"
    ],
    [
      "0.108608162",
      "0.413136639"
    ],
    [
      "0.461333875",
      "0.589001949"
    ],
    [
      "0.029209129",
      "0.587279476"
    ],
    [
      "0.538666120",
      "0.410998046"
    ],
    [
      "0.243408594",
      "0.237111258"
    ],
    [
      "0.891391835",
      "0.586863362"
    ],
    [
      "0.108630390",
      "0.761378912"
    ],
    [
      "0.080744677",
      "0.908494292"
    ],
    [
      "0.894024551",
      "0.939483874"
    ],
    [
      "0.672470228",
      "0.234752012"
    ],
    [
      "0",
      "0"
    ],
    [
      "1",
      "0"
    ],
    [
      "0",
      "1"
    ],
    [
      "1",
      "1"
    ],
    [
      "0.5",
      "0.5"
    ]
  ]
}

提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 35
}

当前第一名的答案

{
  "points": [
    [
      "0.105975452",
      "0.060516122"
    ],
    [
      "0.680876337",
      "0.941630523"
    ],
    [
      "0.756591401",
      "0.762888737"
    ],
    [
      "0.738026408",
      "0.069252543"
    ],
    [
      "0.468080705",
      "0.938870571"
    ],
    [
      "0.030260377",
      "0.239257905"
    ],
    [
      "0.676371611",
      "0.585358525"
    ],
    [
      "0.261973595",
      "0.930747458"
    ],
    [
      "0.323628382",
      "0.414641473"
    ],
    [
      "0.970790871",
      "0.412720531"
    ],
    [
      "0.244923308",
      "0.590118270"
    ],
    [
      "0.969739614",
      "0.760742088"
    ],
    [
      "0.531919301",
      "0.061129432"
    ],
    [
      "0.543940340",
      "0.764131672"
    ],
    [
      "0.327529775",
      "0.765247989"
    ],
    [
      "0.755076688",
      "0.409881733"
    ],
    [
      "0.919255324",
      "0.091505709"
    ],
    [
      "0.456059658",
      "0.235868327"
    ],
    [
      "0.891369611",
      "0.238621092"
    ],
    [
      "0.319123669",
      "0.058369476"
    ],
    [
      "0.108608162",
      "0.413136639"
    ],
    [
      "0.461333875",
      "0.589001949"
    ],
    [
      "0.029209129",
      "0.587279476"
    ],
    [
      "0.538666120",
      "0.410998046"
    ],
    [
      "0.243408594",
      "0.237111258"
    ],
    [
      "0.891391835",
      "0.586863362"
    ],
    [
      "0.108630390",
      "0.761378912"
    ],
    [
      "0.080744677",
      "0.908494292"
    ],
    [
      "0.894024551",
      "0.939483874"
    ],
    [
      "0.672470228",
      "0.234752012"
    ],
    [
      "0",
      "0"
    ],
    [
      "1",
      "0"
    ],
    [
      "0",
      "1"
    ],
    [
      "1",
      "1"
    ],
    [
      "0.5",
      "0.5"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是盖住整块正方形所需的共同半径，越小越好。 · 验证器 v1.0.0

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。发帖即公开署名，与纪录同一个名字；署名后的 #编号是账号的注册序号，冒不了名。发言资格与实绩绑定：破过一次纪录，就永久拥有发言权。新发言经自动审核后公开。

还没有帖子。第一个聊聊这道题的思路？