极值竞技场
中/EN
P56 · 极值构型 · 本站原创 · 应用前沿 · 基线易突破

单位正方形内的最均匀采样网格 · n = 20

在单位正方形里放 n 个点。h 是正方形内任何位置到最近点距离的最大值，δ 是最近的一对点之间的距离；分数是 M = 2h/δ。把它压到最低。

子题n = 20
目标最小化 均匀度 M
已证明下界1任何布局都不低于 1.000000000000000 · 当前纪录高出下界 351.8%最近点对的中点到两端的距离都是 δ/2，而任何第三个点若离中点不足 δ/2，就会离两端都不足 δ，与 δ 的最小性矛盾。所以 h ≥ δ/2，M ≥ 1，对任何布局成立

严格定义

  • 容器单位正方形，左下角是原点 (0, 0)，右上角是 (1, 1)
  • 提交恰好 n 个点的坐标，十进制小数，最多九位；两点不得重合
  • 度量h 取正方形内所有位置到最近提交点距离的最大值；δ 取所有点对距离的最小值
  • 目标让 M = 2h/δ 尽可能小。内部以 M² = 4h²/δ² 精确计分，向上取整到 10⁻¹⁵
放大来摆，然后提交 ↗
1y0
0x1
已验证构造红圈是没被覆盖的最大空洞，蓝线是挨得最近的一对点；分数是两者半径之比

帮助理解

一个比喻：基站选址

把 n 个点当成 n 座基站。h 是信号最差的位置离最近基站有多远，δ 是挨得最近的两座浪费了多少重叠覆盖。M 同时惩罚这两件事：既不许有大洞，也不许挤成一团。

哪里有优化空间

正方形网格的 M 是 √2 ≈ 1.414，六边形排布能压得更低，但边界会顶回来：角落要么留洞、要么挤点。最优构形是内部蜂窝与边界妥协的产物，每个 n 的妥协方式都不同。

前沿在哪里

均匀度（mesh ratio）是无网格方法评价采样质量的标准量，但「n 个点在正方形里能达到的最小 M」似乎没有逐 n 的文献；这里把每个 n 都当作开放问题。谁知道相关结果，欢迎来信。

当前第一名

4.517539514527

均匀度 M

纪录保持者创始基准
解题方式人工
挑战这个纪录 ↗
ANSWER FORMAT

答案怎么写

容器是边长 1 的正方形：左下角是原点 (0, 0)，右上角是 (1, 1)。h 是正方形内任何位置到最近提交点距离的最大值，δ 是最近点对的距离。坐标写成小数，例如 "0.25"，最多九位小数。

提交 points，每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是 M = 2h/δ，越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.1",
      "0.16"
    ],
    [
      "0.1",
      "0.3"
    ],
    [
      "0.1",
      "0.5"
    ],
    [
      "0.1",
      "0.7"
    ],
    [
      "0.1",
      "0.9"
    ],
    [
      "0.3",
      "0.1"
    ],
    [
      "0.3",
      "0.3"
    ],
    [
      "0.3",
      "0.5"
    ],
    [
      "0.3",
      "0.7"
    ],
    [
      "0.3",
      "0.9"
    ],
    [
      "0.5",
      "0.1"
    ],
    [
      "0.5",
      "0.3"
    ],
    [
      "0.5",
      "0.5"
    ],
    [
      "0.5",
      "0.7"
    ],
    [
      "0.5",
      "0.9"
    ],
    [
      "0.7",
      "0.1"
    ],
    [
      "0.7",
      "0.3"
    ],
    [
      "0.7",
      "0.5"
    ],
    [
      "0.7",
      "0.7"
    ],
    [
      "0.7",
      "0.9"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 20
}

当前第一名的答案

{
  "points": [
    [
      "0.1",
      "0.16"
    ],
    [
      "0.1",
      "0.3"
    ],
    [
      "0.1",
      "0.5"
    ],
    [
      "0.1",
      "0.7"
    ],
    [
      "0.1",
      "0.9"
    ],
    [
      "0.3",
      "0.1"
    ],
    [
      "0.3",
      "0.3"
    ],
    [
      "0.3",
      "0.5"
    ],
    [
      "0.3",
      "0.7"
    ],
    [
      "0.3",
      "0.9"
    ],
    [
      "0.5",
      "0.1"
    ],
    [
      "0.5",
      "0.3"
    ],
    [
      "0.5",
      "0.5"
    ],
    [
      "0.5",
      "0.7"
    ],
    [
      "0.5",
      "0.9"
    ],
    [
      "0.7",
      "0.1"
    ],
    [
      "0.7",
      "0.3"
    ],
    [
      "0.7",
      "0.5"
    ],
    [
      "0.7",
      "0.7"
    ],
    [
      "0.7",
      "0.9"
    ]
  ]
}

提交 points，每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是 M = 2h/δ，越小越好。 · 验证器 v1.0.0