极值竞技场
中/EN
P52 · 极值构型 · 经典问题

最远与最近距离之比 · n = 9

在平面上放置 n 个点，记最远两点距离为 D、最近两点距离为 d，使比值 D/d 尽可能小。

子题n = 9
目标最小化 最远与最近距离之比

严格定义

  • 容器没有真正的容器：比值不随缩放平移改变，答案缩放到单位正方形内写下即可
  • 提交恰好 n 个点 points，两两不重合
  • 目标让 D/d 尽可能小。内部以平方比精确比较
放大来摆，然后提交 ↗
1y0
0x1
已验证构造最远与最近的一对点

帮助理解

哪里有优化空间

既要最近的不太近、又要最远的不太远，点集被迫又圆又匀：内部像六边形蜂窝，输赢却决定在边界的取舍。

前沿在哪里

这一族收录在 Friedman 的 maxmin 页（Rechenberg、Cantrell、Audet 等人的构造），全部未证明；本站已录三个值，其余 n 未录，开放。

查看来源
当前第一名

2.683281573

最远与最近距离之比

纪录保持者NUE_13
解题方式人工
挑战这个纪录 ↗
历史纪录（1 次易主）
  1. NUE_13人工
    2.828427125→2.683281573
ANSWER FORMAT

答案怎么写

把答案缩放平移到边长 1 的正方形内写下即可：比值不随缩放改变，而任何点集的宽和高都不超过它自己的直径，所以总放得下。左下角是原点 (0, 0)，右上角是 (1, 1)，坐标最多九位小数。

提交 points，每个坐标写成十进制字符串，例如 "0.5"。比值与整体的缩放和平移无关，正方形只是写下答案的地方。

当前第一名的答案

{
  "points": [
    [
      "0.125000000",
      "0.125000000"
    ],
    [
      "0.500000000",
      "0.000000000"
    ],
    [
      "0.875000000",
      "0.125000000"
    ],
    [
      "0.000000000",
      "0.500000000"
    ],
    [
      "0.500000000",
      "0.500000000"
    ],
    [
      "1.000000000",
      "0.500000000"
    ],
    [
      "0.125000000",
      "0.875000000"
    ],
    [
      "0.500000000",
      "1.000000000"
    ],
    [
      "0.875000000",
      "0.875000000"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 9
}

当前第一名的答案

{
  "points": [
    [
      "0.125000000",
      "0.125000000"
    ],
    [
      "0.500000000",
      "0.000000000"
    ],
    [
      "0.875000000",
      "0.125000000"
    ],
    [
      "0.000000000",
      "0.500000000"
    ],
    [
      "0.500000000",
      "0.500000000"
    ],
    [
      "1.000000000",
      "0.500000000"
    ],
    [
      "0.125000000",
      "0.875000000"
    ],
    [
      "0.500000000",
      "1.000000000"
    ],
    [
      "0.875000000",
      "0.875000000"
    ]
  ]
}

提交 points，每个坐标写成十进制字符串，例如 "0.5"。比值与整体的缩放和平移无关，正方形只是写下答案的地方。 · 验证器 v1.0.0