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

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

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

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

严格定义

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

最大误差 D*

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

答案怎么写

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

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

当前第一名的答案

{
  "points": [
    [
      "0.008163265",
      "0.008163265"
    ],
    [
      "0.024489796",
      "0.408163265"
    ],
    [
      "0.040816327",
      "0.208163265"
    ],
    [
      "0.057142857",
      "0.608163265"
    ],
    [
      "0.073469388",
      "0.108163265"
    ],
    [
      "0.089795918",
      "0.508163265"
    ],
    [
      "0.106122449",
      "0.308163265"
    ],
    [
      "0.12244898",
      "0.708163265"
    ],
    [
      "0.13877551",
      "0.058163265"
    ],
    [
      "0.155102041",
      "0.458163265"
    ],
    [
      "0.171428571",
      "0.258163265"
    ],
    [
      "0.187755102",
      "0.658163265"
    ],
    [
      "0.204081633",
      "0.158163265"
    ],
    [
      "0.220408163",
      "0.558163265"
    ],
    [
      "0.236734694",
      "0.358163265"
    ],
    [
      "0.253061224",
      "0.758163265"
    ],
    [
      "0.269387755",
      "0.033163265"
    ],
    [
      "0.285714286",
      "0.433163265"
    ],
    [
      "0.302040816",
      "0.233163265"
    ],
    [
      "0.318367347",
      "0.633163265"
    ],
    [
      "0.334693878",
      "0.133163265"
    ],
    [
      "0.351020408",
      "0.533163265"
    ],
    [
      "0.367346939",
      "0.333163265"
    ],
    [
      "0.383673469",
      "0.733163265"
    ],
    [
      "0.4",
      "0.083163265"
    ],
    [
      "0.416326531",
      "0.483163265"
    ],
    [
      "0.432653061",
      "0.283163265"
    ],
    [
      "0.448979592",
      "0.683163265"
    ],
    [
      "0.465306122",
      "0.183163265"
    ],
    [
      "0.481632653",
      "0.583163265"
    ],
    [
      "0.497959184",
      "0.383163265"
    ],
    [
      "0.514285714",
      "0.783163265"
    ],
    [
      "0.530612245",
      "0.020663265"
    ],
    [
      "0.546938776",
      "0.420663265"
    ],
    [
      "0.563265306",
      "0.220663265"
    ],
    [
      "0.579591837",
      "0.620663265"
    ],
    [
      "0.595918367",
      "0.120663265"
    ],
    [
      "0.612244898",
      "0.520663265"
    ],
    [
      "0.628571429",
      "0.320663265"
    ],
    [
      "0.644897959",
      "0.720663265"
    ],
    [
      "0.66122449",
      "0.070663265"
    ],
    [
      "0.67755102",
      "0.470663265"
    ],
    [
      "0.693877551",
      "0.270663265"
    ],
    [
      "0.710204082",
      "0.670663265"
    ],
    [
      "0.726530612",
      "0.170663265"
    ],
    [
      "0.742857143",
      "0.570663265"
    ],
    [
      "0.759183673",
      "0.370663265"
    ],
    [
      "0.775510204",
      "0.770663265"
    ],
    [
      "0.791836735",
      "0.045663265"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 49
}

当前第一名的答案

{
  "points": [
    [
      "0.008163265",
      "0.008163265"
    ],
    [
      "0.024489796",
      "0.408163265"
    ],
    [
      "0.040816327",
      "0.208163265"
    ],
    [
      "0.057142857",
      "0.608163265"
    ],
    [
      "0.073469388",
      "0.108163265"
    ],
    [
      "0.089795918",
      "0.508163265"
    ],
    [
      "0.106122449",
      "0.308163265"
    ],
    [
      "0.12244898",
      "0.708163265"
    ],
    [
      "0.13877551",
      "0.058163265"
    ],
    [
      "0.155102041",
      "0.458163265"
    ],
    [
      "0.171428571",
      "0.258163265"
    ],
    [
      "0.187755102",
      "0.658163265"
    ],
    [
      "0.204081633",
      "0.158163265"
    ],
    [
      "0.220408163",
      "0.558163265"
    ],
    [
      "0.236734694",
      "0.358163265"
    ],
    [
      "0.253061224",
      "0.758163265"
    ],
    [
      "0.269387755",
      "0.033163265"
    ],
    [
      "0.285714286",
      "0.433163265"
    ],
    [
      "0.302040816",
      "0.233163265"
    ],
    [
      "0.318367347",
      "0.633163265"
    ],
    [
      "0.334693878",
      "0.133163265"
    ],
    [
      "0.351020408",
      "0.533163265"
    ],
    [
      "0.367346939",
      "0.333163265"
    ],
    [
      "0.383673469",
      "0.733163265"
    ],
    [
      "0.4",
      "0.083163265"
    ],
    [
      "0.416326531",
      "0.483163265"
    ],
    [
      "0.432653061",
      "0.283163265"
    ],
    [
      "0.448979592",
      "0.683163265"
    ],
    [
      "0.465306122",
      "0.183163265"
    ],
    [
      "0.481632653",
      "0.583163265"
    ],
    [
      "0.497959184",
      "0.383163265"
    ],
    [
      "0.514285714",
      "0.783163265"
    ],
    [
      "0.530612245",
      "0.020663265"
    ],
    [
      "0.546938776",
      "0.420663265"
    ],
    [
      "0.563265306",
      "0.220663265"
    ],
    [
      "0.579591837",
      "0.620663265"
    ],
    [
      "0.595918367",
      "0.120663265"
    ],
    [
      "0.612244898",
      "0.520663265"
    ],
    [
      "0.628571429",
      "0.320663265"
    ],
    [
      "0.644897959",
      "0.720663265"
    ],
    [
      "0.66122449",
      "0.070663265"
    ],
    [
      "0.67755102",
      "0.470663265"
    ],
    [
      "0.693877551",
      "0.270663265"
    ],
    [
      "0.710204082",
      "0.670663265"
    ],
    [
      "0.726530612",
      "0.170663265"
    ],
    [
      "0.742857143",
      "0.570663265"
    ],
    [
      "0.759183673",
      "0.370663265"
    ],
    [
      "0.775510204",
      "0.770663265"
    ],
    [
      "0.791836735",
      "0.045663265"
    ]
  ]
}

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