P54 · 极值构型 · 经典问题 · 应用前沿 · 基线易突破

单位正方形内的最低星偏差 · n = 48

在单位正方形里放 n 个采样点。从原点量起、边平行于坐标轴的每一块矩形,占了多少面积,就该分到多少比例的点;你的分数,是所有这类矩形里最大的那个偏差。把它压到最低。

子题n = 48
目标最小化 最大误差 D*

严格定义

  • 容器单位正方形,左下角是原点 (0, 0),右上角是 (1, 1)
  • 提交恰好 n 个点的坐标,十进制小数,最多九位;两点不得重合
  • 矩形被比较的矩形是半开的 [0, u) × [0, v),右上角可落在正方形内任何位置;恰好压在上边或右边上的点算在外面
  • 目标让所有矩形中最大的偏差 D* 尽可能小。上确界在提交坐标的网格上取得,以整数精确计分
放大来摆,然后提交
1y0
0x1
已验证构造虚线框占 62.0% 的面积,照这个比例应该有 29.8 个点,实际有 48 个,差 0.3799,这就是分数

帮助理解

一个比喻:采样预算

把正方形当成一帧要渲染的画面,这 n 个点就是你全部的采样预算。哪块矩形分到的点比面积应得的多,是预算浪费在同一处;少了,是那块的细节被漏掉。

哪里有优化空间

格点和随机撒点都会在某些矩形上系统性偏置;低偏差构造(Hammersley、van der Corput)压得低得多。但对每个具体的 n,没人知道还能压到哪里。

前沿在哪里

n ≤ 21 的最优解已由 Clément、Doerr、Klamroth 与 Paquete 在 2025 年证明(Proc. Amer. Math. Soc. Ser. B 12: 78–90),所以本站从 n = 22 起;再往上,每一个 n 都是开放的。

当前第一名

0.379861111113889

最大误差 D*

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

答案怎么写

容器是边长 1 的正方形:左下角是原点 (0, 0),右上角是 (1, 1)。被比较的矩形永远从原点量起,右上角可以落在正方形里的任何位置,所以一共有无穷多块矩形要同时满足,而不是某几块。坐标写成小数,例如 "0.25",最多九位小数。

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。榜上的数字是 D*,也就是所有矩形里最大的那个误差;分数越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.008333333",
      "0.008333333"
    ],
    [
      "0.025",
      "0.408333333"
    ],
    [
      "0.041666667",
      "0.208333333"
    ],
    [
      "0.058333333",
      "0.608333333"
    ],
    [
      "0.075",
      "0.108333333"
    ],
    [
      "0.091666667",
      "0.508333333"
    ],
    [
      "0.108333333",
      "0.308333333"
    ],
    [
      "0.125",
      "0.708333333"
    ],
    [
      "0.141666667",
      "0.058333333"
    ],
    [
      "0.158333333",
      "0.458333333"
    ],
    [
      "0.175",
      "0.258333333"
    ],
    [
      "0.191666667",
      "0.658333333"
    ],
    [
      "0.208333333",
      "0.158333333"
    ],
    [
      "0.225",
      "0.558333333"
    ],
    [
      "0.241666667",
      "0.358333333"
    ],
    [
      "0.258333333",
      "0.758333333"
    ],
    [
      "0.275",
      "0.033333333"
    ],
    [
      "0.291666667",
      "0.433333333"
    ],
    [
      "0.308333333",
      "0.233333333"
    ],
    [
      "0.325",
      "0.633333333"
    ],
    [
      "0.341666667",
      "0.133333333"
    ],
    [
      "0.358333333",
      "0.533333333"
    ],
    [
      "0.375",
      "0.333333333"
    ],
    [
      "0.391666667",
      "0.733333333"
    ],
    [
      "0.408333333",
      "0.083333333"
    ],
    [
      "0.425",
      "0.483333333"
    ],
    [
      "0.441666667",
      "0.283333333"
    ],
    [
      "0.458333333",
      "0.683333333"
    ],
    [
      "0.475",
      "0.183333333"
    ],
    [
      "0.491666667",
      "0.583333333"
    ],
    [
      "0.508333333",
      "0.383333333"
    ],
    [
      "0.525",
      "0.783333333"
    ],
    [
      "0.541666667",
      "0.020833333"
    ],
    [
      "0.558333333",
      "0.420833333"
    ],
    [
      "0.575",
      "0.220833333"
    ],
    [
      "0.591666667",
      "0.620833333"
    ],
    [
      "0.608333333",
      "0.120833333"
    ],
    [
      "0.625",
      "0.520833333"
    ],
    [
      "0.641666667",
      "0.320833333"
    ],
    [
      "0.658333333",
      "0.720833333"
    ],
    [
      "0.675",
      "0.070833333"
    ],
    [
      "0.691666667",
      "0.470833333"
    ],
    [
      "0.708333333",
      "0.270833333"
    ],
    [
      "0.725",
      "0.670833333"
    ],
    [
      "0.741666667",
      "0.170833333"
    ],
    [
      "0.758333333",
      "0.570833333"
    ],
    [
      "0.775",
      "0.370833333"
    ],
    [
      "0.791666667",
      "0.770833333"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 48
}

当前第一名的答案

{
  "points": [
    [
      "0.008333333",
      "0.008333333"
    ],
    [
      "0.025",
      "0.408333333"
    ],
    [
      "0.041666667",
      "0.208333333"
    ],
    [
      "0.058333333",
      "0.608333333"
    ],
    [
      "0.075",
      "0.108333333"
    ],
    [
      "0.091666667",
      "0.508333333"
    ],
    [
      "0.108333333",
      "0.308333333"
    ],
    [
      "0.125",
      "0.708333333"
    ],
    [
      "0.141666667",
      "0.058333333"
    ],
    [
      "0.158333333",
      "0.458333333"
    ],
    [
      "0.175",
      "0.258333333"
    ],
    [
      "0.191666667",
      "0.658333333"
    ],
    [
      "0.208333333",
      "0.158333333"
    ],
    [
      "0.225",
      "0.558333333"
    ],
    [
      "0.241666667",
      "0.358333333"
    ],
    [
      "0.258333333",
      "0.758333333"
    ],
    [
      "0.275",
      "0.033333333"
    ],
    [
      "0.291666667",
      "0.433333333"
    ],
    [
      "0.308333333",
      "0.233333333"
    ],
    [
      "0.325",
      "0.633333333"
    ],
    [
      "0.341666667",
      "0.133333333"
    ],
    [
      "0.358333333",
      "0.533333333"
    ],
    [
      "0.375",
      "0.333333333"
    ],
    [
      "0.391666667",
      "0.733333333"
    ],
    [
      "0.408333333",
      "0.083333333"
    ],
    [
      "0.425",
      "0.483333333"
    ],
    [
      "0.441666667",
      "0.283333333"
    ],
    [
      "0.458333333",
      "0.683333333"
    ],
    [
      "0.475",
      "0.183333333"
    ],
    [
      "0.491666667",
      "0.583333333"
    ],
    [
      "0.508333333",
      "0.383333333"
    ],
    [
      "0.525",
      "0.783333333"
    ],
    [
      "0.541666667",
      "0.020833333"
    ],
    [
      "0.558333333",
      "0.420833333"
    ],
    [
      "0.575",
      "0.220833333"
    ],
    [
      "0.591666667",
      "0.620833333"
    ],
    [
      "0.608333333",
      "0.120833333"
    ],
    [
      "0.625",
      "0.520833333"
    ],
    [
      "0.641666667",
      "0.320833333"
    ],
    [
      "0.658333333",
      "0.720833333"
    ],
    [
      "0.675",
      "0.070833333"
    ],
    [
      "0.691666667",
      "0.470833333"
    ],
    [
      "0.708333333",
      "0.270833333"
    ],
    [
      "0.725",
      "0.670833333"
    ],
    [
      "0.741666667",
      "0.170833333"
    ],
    [
      "0.758333333",
      "0.570833333"
    ],
    [
      "0.775",
      "0.370833333"
    ],
    [
      "0.791666667",
      "0.770833333"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。榜上的数字是 D*,也就是所有矩形里最大的那个误差;分数越小越好。 · 验证器 v1.0.0