极值竞技场
中/EN
P55 · 极值构型 · 经典问题 · 应用前沿 · 基线易突破

单位正方形内的最优量化 · n = 30

在边长为 1 的正方形里放 n 个点。正方形内的每一个位置，都由离它最近的那个点负责；你的分数，是「位置到负责它的点的距离的平方」在整个正方形上的平均值。把这个平均值压到最低。

子题n = 30
目标最小化 平均平方距离
已知最好（未证明）0.005545370492276本站离线搜索：33 个确定性起点各走 Lloyd 至收敛，起点 9 胜出，tools/p55-lloyd.ts 可逐位复现；最优性未知
已证明下界5/(18√3·30)任何布局都不低于 0.005345835825829 · 当前纪录高出下界 3.7%Fejes Tóth 矩定理：平均平方距离不可能低于把地图剖成 n 个等面积正六边形的水平；正方形铺不出正六边形，这条线永远取不到，只能逼近

严格定义

  • 容器单位正方形，左下角是原点 (0, 0)，右上角是 (1, 1)
  • 提交恰好 n 个点的坐标，十进制小数，最多九位；两点不得重合
  • 归属每个位置归离它最近的那个点；恰好等距的位置构成零面积集合，归给谁不影响分数
  • 目标让 E(P) = ∫∫ min‖x − pᵢ‖² dx 尽可能小。精确有理数计分，向上取整到 10⁻¹⁸
放大来摆，然后提交 ↗
1y0
0x1
已验证构造30 块辖区，最贵的那块占了总代价的 3.9%

帮助理解

一个比喻：复活点

把正方形当成一张地图，这 n 个点就是你放的复活点。玩家均匀地随机出现在地图上任何位置，然后被送到离他最近的复活点。你的分数，就是这段路程平方的平均值。

哪里有优化空间

把每个点挪到它辖区的重心、反复迭代，就是 Lloyd 算法：它一定会停，但停在驻点，不是最优解。这个能量有很多局部极小，落进哪一个，完全取决于起点。能优化的就是这一段。

前沿在哪里

n ≤ 2 已证明；n = 3、4、5 依赖一个未证明的对称性猜想（Roychowdhury, arXiv:1608.03815）；n ≥ 6 文献原话是「极其困难，至今不知道答案」。另有一条对每个 n 都成立的下界 5/(18√3·n)：那是正六边形的水平，正方形永远铺不出。

当前第一名

0.005545370492276

平均平方距离

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

答案怎么写

容器是边长 1 的正方形：左下角是原点 (0, 0)，右上角是 (1, 1)。每一个位置都归离它最近的那个点管，所以整块正方形被划成 n 块，谁也不重叠、谁也不漏下。坐标写成小数，例如 "0.25"，最多九位小数。

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是整块地图上的平均平方距离，越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.587623960",
      "0.076067761"
    ],
    [
      "0.420671473",
      "0.113932290"
    ],
    [
      "0.085939961",
      "0.527258064"
    ],
    [
      "0.579138252",
      "0.665538467"
    ],
    [
      "0.583086179",
      "0.455410084"
    ],
    [
      "0.914060039",
      "0.472741936"
    ],
    [
      "0.412376040",
      "0.923932239"
    ],
    [
      "0.412620360",
      "0.746648855"
    ],
    [
      "0.917695768",
      "0.891502229"
    ],
    [
      "0.251581927",
      "0.654890428"
    ],
    [
      "0.752577809",
      "0.117780691"
    ],
    [
      "0.254830478",
      "0.249396158"
    ],
    [
      "0.088326998",
      "0.726559352"
    ],
    [
      "0.082304232",
      "0.108497771"
    ],
    [
      "0.416913821",
      "0.544589916"
    ],
    [
      "0.748418073",
      "0.345109572"
    ],
    [
      "0.084083135",
      "0.912716589"
    ],
    [
      "0.911673002",
      "0.273440648"
    ],
    [
      "0.587379640",
      "0.253351145"
    ],
    [
      "0.579328527",
      "0.886067710"
    ],
    [
      "0.747078081",
      "0.554628503"
    ],
    [
      "0.420861748",
      "0.334461533"
    ],
    [
      "0.745169522",
      "0.750603842"
    ],
    [
      "0.084598358",
      "0.320820766"
    ],
    [
      "0.915401642",
      "0.679179234"
    ],
    [
      "0.252428778",
      "0.076149457"
    ],
    [
      "0.747571222",
      "0.923850543"
    ],
    [
      "0.915916865",
      "0.087283411"
    ],
    [
      "0.252921919",
      "0.445371497"
    ],
    [
      "0.247422191",
      "0.882219309"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 30
}

当前第一名的答案

{
  "points": [
    [
      "0.587623960",
      "0.076067761"
    ],
    [
      "0.420671473",
      "0.113932290"
    ],
    [
      "0.085939961",
      "0.527258064"
    ],
    [
      "0.579138252",
      "0.665538467"
    ],
    [
      "0.583086179",
      "0.455410084"
    ],
    [
      "0.914060039",
      "0.472741936"
    ],
    [
      "0.412376040",
      "0.923932239"
    ],
    [
      "0.412620360",
      "0.746648855"
    ],
    [
      "0.917695768",
      "0.891502229"
    ],
    [
      "0.251581927",
      "0.654890428"
    ],
    [
      "0.752577809",
      "0.117780691"
    ],
    [
      "0.254830478",
      "0.249396158"
    ],
    [
      "0.088326998",
      "0.726559352"
    ],
    [
      "0.082304232",
      "0.108497771"
    ],
    [
      "0.416913821",
      "0.544589916"
    ],
    [
      "0.748418073",
      "0.345109572"
    ],
    [
      "0.084083135",
      "0.912716589"
    ],
    [
      "0.911673002",
      "0.273440648"
    ],
    [
      "0.587379640",
      "0.253351145"
    ],
    [
      "0.579328527",
      "0.886067710"
    ],
    [
      "0.747078081",
      "0.554628503"
    ],
    [
      "0.420861748",
      "0.334461533"
    ],
    [
      "0.745169522",
      "0.750603842"
    ],
    [
      "0.084598358",
      "0.320820766"
    ],
    [
      "0.915401642",
      "0.679179234"
    ],
    [
      "0.252428778",
      "0.076149457"
    ],
    [
      "0.747571222",
      "0.923850543"
    ],
    [
      "0.915916865",
      "0.087283411"
    ],
    [
      "0.252921919",
      "0.445371497"
    ],
    [
      "0.247422191",
      "0.882219309"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是整块地图上的平均平方距离，越小越好。 · 验证器 v1.0.0