末影之眼的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题是一道交互题：世界中有 $128$ ~128~ 座要塞，每次抛掷末影之眼可获知「距抛掷点最近的要塞」的水平方位角，且该眼有 $20\%$ ~20\%~ 的概率碎裂，最终只允许作答一次。核心解法是先用两次抛掷确定目标要塞——第二次沿第一条射线前进以拉长基线，再对两条射线求交——使落点稳定落在容错半径 $16$ ~16~ 格以内。

分析

核心观察

通过率的上限由眼数预算决定，与几何精度无关：抛掷 $2$ ~2~ 次时单点通过率的上限为 $88.33\%$ ~88.33\%~。
单次抛掷只提供方向，不提供距离，因此至少需要两条射线才能定位。
每个要塞的 Voronoi 胞是凸集，原点与目标要塞同属一个胞，因此沿射线前进绝不会切到别的要塞——这是本题的钥匙。

思路

第一步：算清眼数预算。 设共抛掷 $m$ ~m~ 次，碎裂数 $j \sim B(m, 0.2)$ ~j \sim B(m, 0.2)~，剩余眼数为 $12 - j$ ~12 - j~。通过条件为

$\displaystyle 12 - j \ge 12 - k \iff j \le k,\qquad k \sim B(12, 0.1)$

于是单点通过率为

$\displaystyle P(\text{通过}) = \sum_{k=0}^{12} P(k)\cdot P(j \le k)$

抛掷次数 $m$ ~m~	$0$ ~0~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$4$ ~4~
眼数关通过率	$100\%$ ~100\%~	$94.35\%$ ~94.35\%~	$88.33\%$ ~88.33\%~	$82.12\%$ ~82.12\%~	$75.88\%$ ~75.88\%~

抛掷次数越多，通过率越低： $k = 0$ ~k = 0~ 的概率为 $0.9^{12} = 28.2\%$ ~0.9^{12} = 28.2\%~，这类世界中任意一只眼碎裂即失败。而抛掷 $0$ ~0~ 次或 $1$ ~1~ 次都无法定位（一条射线只有方向），因此最优方案是恰好抛掷 $2$ ~2~ 次，单点通过率上限 $88.33\%$ ~88.33\%~。

期望得分。 本题共 $20$ ~20~ 个测试点、每点 $5$ ~5~ 分，故期望得分为 $100 \times 0.8833 = 88.33$ ~100 \times 0.8833 = 88.33~ 分，得分标准差约 $7.2$ ~7.2~ 分；一次提交通过全部 $20$ ~20~ 个测试点（即该题 AC）的概率为 $0.8833^{20} \approx 8.4\%$ ~0.8833^{20} \approx 8.4\%~。该上限由题目机制决定，与解法无关。

第二步：世界结构。 要塞由环算法生成，第 $c$ ~c~ 环的距离带为

$\displaystyle d(c) = 2048 + 3072c \pm 640 \text{ 格}$

即每环一条宽 $1280$ ~1280~ 格的距离带，带中心相隔 $3072$ ~3072~ 格。环内方位角按固定步长铺开：第 $0$ ~0~ 环 $3$ ~3~ 座相隔 $120^\circ$ ~120^\circ~，第 $1$ ~1~ 环 $6$ ~6~ 座相隔 $60^\circ$ ~60^\circ~，依此类推；最后一环为剩余的 $9$ ~9~ 座（ $9 \times 36^\circ = 324^\circ$ ~9 \times 36^\circ = 324^\circ~，留一个 $72^\circ$ ~72^\circ~ 空隙），本解法只依赖第 $0$ ~0~ 环，该空隙不影响任何结论。

环	座数	距离（格）
$0$ ~0~	$3$ ~3~	$1408 \sim 2688$ ~1408 \sim 2688~
$1$ ~1~	$6$ ~6~	$4480 \sim 5760$ ~4480 \sim 5760~
$2$ ~2~	$10$ ~10~	$7552 \sim 8832$ ~7552 \sim 8832~
$\vdots$ ~\vdots~	$\vdots$ ~\vdots~	$\vdots$ ~\vdots~
$7$ ~7~	$9$ ~9~	$22912 \sim 24192$ ~22912 \sim 24192~

由此可得一个直接结论：在原点抛掷时，最近的要塞必定属于第 $0$ ~0~ 环——第 $0$ ~0~ 环最远 $2688$ ~2688~ 格，第 $1$ ~1~ 环最近也有 $4480$ ~4480~ 格。

下图同时展示了要塞的环状分布与它们对应的 Voronoi 胞。每个胞内的点都会把同一座要塞视为最近要塞。

要塞分布与 Voronoi 胞

将要塞视为平面点集，它们划分出 Voronoi 图，每个要塞 $A$ ~A~ 对应区域

$\displaystyle \mathrm{cell}(A) = \{\,X : |X - A| \le |X - B| \text{ 对一切要塞 } B\,\}$

抛掷返回的方位角，本质是「当前点落在哪个 cell 内」。因此整道题等价于用两条射线找回 cell 的主人。

下文各层级的「落点率」只指几何命中率；单点通过率还要再乘眼数关通过率（两次抛掷时为 $88.33\%$ ~88.33\%~）。

L0：一次抛掷，在环带中碰运气。 抛掷一次得到角度 $\theta$ ~\theta~，沿该射线在环带中心 $2048$ ~2048~ 处作答。角度是精确的，但沿射线的距离完全未知，仅落在 $1408 \sim 2688$ ~1408 \sim 2688~ 这条宽 $1280$ ~1280~ 格的带内，落点误差为 $|D - 2048|$ ~|D - 2048|~，命中概率约为

$\displaystyle P \approx \frac{2 \times 16}{1280} \approx 2.5\%$

$D$ ~D~ 是三个均匀半径的最小值，密度偏向近端，因此取中心并非最优：取中点的实测落点率约 $1.9\%$ ~1.9\%~，沿带内均匀随机约 $2.4\%$ ~2.4\%~，而单次抛掷的最优策略（押在带近端 $1424$ ~1424~ 附近）上限可达 $7.2\%$ ~7.2\%~——但仍远低于两层策略。该层的结论是：一条射线不足以定位，至少需要两条。

一次抛掷得到的只是方向，而不是距离；下图中的环带区间正是这种不确定性的几何表示。

一次抛掷的方向与环带

L1：两次抛掷，垂直基线 $32$ ~32~ 格。 从原点 $P_1$ ~P_1~ 抛掷得到指向要塞 $A$ ~A~ 的射线，再从另一点 $P_2$ ~P_2~ 抛掷得到第二条射线，两线交会即为 $A$ ~A~。注意 $P_2$ ~P_2~ 不能落在第一条射线上，否则两射线共线、方程组退化，因此需要垂直偏移。设要塞距第一点 $D$ ~D~、基线长 $b$ ~b~、方位角量化误差 $\delta\theta \le 0.05^\circ = 8.7 \times 10^{-4}$ rad，则交会误差为

$\displaystyle \Delta \approx \frac{D^2\,\delta\theta}{b}$

其来源是：两条射线在要塞处的夹角 $\gamma$ ~\gamma~ 满足 $\sin\gamma \approx b/D$ ~\sin\gamma \approx b/D~，第一条射线转过 $\delta\theta$ ~\delta\theta~ 后在要塞距离处横向偏移 $D\,\delta\theta$ ~D\,\delta\theta~，除以 $\sin\gamma$ ~\sin\gamma~ 即得

$\displaystyle \Delta \approx \frac{D\,\delta\theta}{\sin\gamma} \approx \frac{D\,\delta\theta}{b/D} = \frac{D^2\delta\theta}{b}$

即基线越短、目标越远，交会越不稳定。代入 $D \approx 2048$ ~D \approx 2048~ 与 $\delta\theta = 8.7 \times 10^{-4}$ ~\delta\theta = 8.7 \times 10^{-4}~：当 $b = 32$ ~b = 32~ 时 $\Delta \approx 114$ ~\Delta \approx 114~ 格，是容错半径 $16$ ~16~ 的 $7$ ~7~ 倍，实测落点率 $18.5\%$ ~18.5\%~。该层说明交会思路正确，且指出下一层的方向：拉长基线。

L2：基线拉长到 $256$ ~256~ 格。 从原点垂直偏移 $256$ ~256~ 格再抛掷一次：

$\displaystyle \Delta \approx \frac{2048^2 \times 8.7 \times 10^{-4}}{256} \approx 14.3 \text{ 格}$

精度进入容错半径量级，实测落点率 $70.4\%$ ~70.4\%~。仍非满分，有两个独立原因（ $4000$ ~4000~ 个随机世界， $b = 256$ ~b = 256~ 垂直偏移）：

现象	占比
第二次抛掷点仍在 $A$ ~A~ 的 cell 内	$72.2\%$ ~72.2\%~
↳ 其中落点不超过 $16$ ~16~ 格	$94.0\%$ ~94.0\%~
第二次抛掷点已离开 $A$ ~A~ 的 cell	$27.8\%$ ~27.8\%~
↳ 其中落点不超过 $16$ ~16~ 格	$0\%$ ~0\%~

其一，误差本身处于容错边缘： $\Delta$ ~\Delta~ 随 $D$ ~D~ 增长， $D = 2688$ ~D = 2688~ 时 $\Delta \approx 24.6$ ~\Delta \approx 24.6~ 格，超过 $16$ ~16~。其二更致命：cell 在原点附近非常薄。第 $0$ ~0~ 环相邻要塞相距约 $2 \times 2048 \sin 60^\circ \approx 3547$ 格，但三座要塞半径各自独立抖动，其中垂面几乎都从原点附近穿过——实测原点到目标 cell 边界的垂直距离中位数仅约 $150$ ~150~ 格（ $p_{10} \approx 25$ ~p_{10} \approx 25~， $p_{90} \approx 400$ ~p_{90} \approx 400~）。因此垂直偏移 $256$ ~256~ 格时，超过四分之一的世界中该点已不在原 cell 内，第二次读数指向别的要塞。继续拉长垂直基线同样不可行：垂直偏移 $1792$ ~1792~ 格的实测结果中，仍在同一 cell 内的比例为 $0.0\%$ ~0.0\%~。

L3：沿射线前进。 既然垂直方向很薄，就换方向——沿第一条射线朝要塞前进，基线照样拉长。

定理. 设要塞 $A$ ~A~ 是点 $P_1$ ~P_1~ 处的最近要塞，则线段 $[P_1, A]$ ~[P_1, A]~ 上任意点 $X$ ~X~ 的最近要塞仍是 $A$ ~A~。

证明. 每个 cell 是一族半平面之交：

$\displaystyle \mathrm{cell}(A) = \bigcap_{B \ne A} \{\,X : |X - A| \le |X - B|\,\}$

其中每个 $\{\,X : |X-A| \le |X-B|\,\}$ ~\{\,X : |X-A| \le |X-B|\,\}~ 是半平面（两边平方后二次项抵消，剩余线性不等式）。半平面是凸集，凸集之交仍为凸集，故 $\mathrm{cell}(A)$ ~\mathrm{cell}(A)~ 是凸的。由题设 $P_1 \in \mathrm{cell}(A)$ ~P_1 \in \mathrm{cell}(A)~，且 $A \in \mathrm{cell}(A)$ ~A \in \mathrm{cell}(A)~（自身距离为 $0$ ~0~），凸集包含其中任意两点之间的整条线段，故 $[P_1, A] \subseteq \mathrm{cell}(A)$ ~[P_1, A] \subseteq \mathrm{cell}(A)~。线段上任一点抛掷返回的方位角都指向 $A$ ~A~。 $\blacksquare$ ~\blacksquare~

这是定理而非概率：沿射线前进永远不会切到别的要塞，L2 中「离开 cell」的失败模式被彻底消除。

剩余的取参细节：若 $P_2$ ~P_2~ 严格落在射线上，两射线共线、交会退化，因此仍需保留一个较小的垂直偏移 $s > 0$ ~s > 0~；基线 $b$ ~b~ 越接近要塞距离 $D$ ~D~，交会越稳定，误差式为

$\displaystyle \Delta \approx D\,\delta\theta \cdot \frac{\sqrt{(D-b)^2 + s^2}}{s}$

其推导与 L2 一致（横向偏移 $D\delta\theta$ ~D\delta\theta~ 除以两射线夹角的正弦，此处夹角由「 $s$ ~s~ 对着 $D-b$ ~D-b~」给出）。 $s \ll |D-b|$ ~s \ll |D-b|~ 时化为 $\Delta \approx D\,\delta\theta\,|D-b|/s$ ，即 $b$ ~b~ 应贴近 $D$ ~D~、 $s$ ~s~ 应尽量大。但 $s$ ~s~ 受 cell 宽度约束： $P_2$ ~P_2~ 必须仍在 $A$ ~A~ 的 cell 内。实测沿射线 $2048$ ~2048~ 处的横向半宽最小约 $1700$ ~1700~ 格，取数百格是安全的。

四个层级的对照：

层级	做法	落点率	失败主因
L0	$1$ ~1~ 次抛掷，射线与环带相交	$1.9\%$ ~1.9\%~（取中点）/ $2.4\%$ ~2.4\%~（带内随机）	只有方向没有距离
L1	$2$ ~2~ 次抛掷，垂直基线 $32$ ~32~	$18.5\%$ ~18.5\%~	基线过短， $\Delta \approx 114$ ~\Delta \approx 114~ 格
L2	垂直基线 $256$ ~256~	$70.4\%$ ~70.4\%~	$\Delta \approx 14$ ~\Delta \approx 14~ 格已至容错边缘；且约 $28\%$ ~28\%~ 的世界读数已指向别的要塞
L3	沿射线前进，配小垂直偏移	$100.0\%$ ~100.0\%~	——

独立复测（真机对拍）为 L1 $21.4\%$ ~21.4\%~、L2 $69.3\%$ ~69.3\%~、L3 $100.0\%$ ~100.0\%~，与上表相差 $1 \sim 3$ ~1 \sim 3~ 个百分点，属小样本涨落。

本题的关键：L2 已发现「基线越长越准」，但沿垂直方向拉长会撞上 cell 边界；凸性定理指出的方向是沿射线拉长。同一个「拉长基线」的念头，方向不同，结果从 $70.4\%$ ~70.4\%~ 变为 $100\%$ ~100\%~。

具体示例

以题面样例的世界为例：第 $0$ ~0~ 环三座要塞位于 $(-1584, -592)$ ~(-1584, -592)~、 $(1344, -1120)$ ~(1344, -1120)~、 $(432, 2560)$ ~(432, 2560)~。

输出	交互器返回	说明
`? 0 0`	`-159.5 12`	最近要塞为 $(-1584, -592)$ ~(-1584, -592)~；未碎裂
`? 0 256`	`-151.8 11`	最近要塞不变；碎裂一只，剩余 $11$ ~11~
`! -1577 -590`		两条射线交会于 $(-1577.2, -589.7)$ ~(-1577.2, -589.7)~，取整作答

作答点到要塞 $(-1584, -592)$ ~(-1584, -592)~ 的距离约 $7.2$ ~7.2~ 格，不超过 $16$ ~16~ 格；若此时 $k \ge 1$ ~k \ge 1~，则 $11 \ge 12 - k$ ~11 \ge 12 - k~ 满足，该测试点通过。

算法步骤

输出 ? 0 0 并从标准输入读取 $\theta_1$ ~\theta_1~ 与剩余眼数，换算为弧度得到第一条射线方向 ux、uz。
取第 $0$ ~0~ 环的环带（ $1408 \sim 2688$ ~1408 \sim 2688~），令 lo、hi 为带的两端；基线 b 取环带中点 $2048$ ~2048~，垂直偏移 side 取 $384$ ~384~。
由 ux、uz 沿射线前进 b 并垂直偏移 side，得到第二个抛掷点 p2x、p2z，输出 ? p2x p2z 并读取 $\theta_2$ ~\theta_2~。
将两条射线方向记为 d1、d2，计算叉积分母 den。
若 den 的绝对值大于 $10^{-12}$ ~10^{-12}~，由交会公式得到沿第一条射线的距离 t，并检查 t 是否落在环带外扩 $256$ ~256~ 格的范围内；否则将 t 置为 b。
输出 ! round(t \cdot d1x) round(t \cdot d1z) 并结束。

复杂度分析

时间： $O(1)$ ~O(1)~
空间： $O(1)$ ~O(1)~

实现注意事项

每次输出后必须刷新缓冲区（C++ 用 fflush(stdout)，Python 用 sys.stdout.flush()），否则交互器与程序可能互相等待导致超时。
方位角量化为一位小数，即 $|\delta\theta| \le 0.05^\circ = 8.7 \times 10^{-4}$ rad，这是全部误差的来源；坐标量级为 $10^3$ ~10^3~，double 精度不构成瓶颈。
第二个抛掷点与最终答案均需取整为整数坐标，取整误差不超过 $0.71$ ~0.71~ 格，且只影响几何而不再进入读数。
交会公式在两条射线接近平行时分母趋零，代码需检查分母；留出 $s > 0$ ~s > 0~ 后两射线夹角至少数十度，正常不会退化。若解出的距离明显落在环带之外，说明第二次读数指向了别的要塞，此时退化为「沿第一条射线前进到环带中点」的保底答案。
读数中的剩余眼数不参与决策：作答只有一次机会，读到第二个角度时已无选择余地。
基线取环带中点而非固定值，使 $|D - b| \le 640$ ~|D - b| \le 640~ 尽可能小；若抛掷点半径改变，只需先由半径定出所属环、再取该环带中点。
参数余量：参考实现取 $b = 2048$ ~b = 2048~、 $s = 384$ ~s = 384~。经典参数 $b = 1792$ ~b = 1792~、 $s = 128$ ~s = 128~ 的实测落点率同样是 $100\%$ ~100\%~，但穷举最坏构型（ $D = 2688$ ~D = 2688~ 且两次量化误差反向）可达 $23.1$ ~23.1~ 格，已超出容错半径 $16$ ~16~ 格——该构型约 $10^{-4}$ ~10^{-4}~ 稀有，实测未能触发；把基线取到环带中点、偏移取大一些即可把这个尾巴压掉。

$b$ ~b~	$s$ ~s~	穷举最坏落点误差	cell 横向余量
$1792$ ~1792~	$128$ ~128~	$23.1$ ~23.1~ 格	$14.5$ ~14.5~ 倍
$2048$ ~2048~	$256$ ~256~	$8.3$ ~8.3~ 格	$6.7$ ~6.7~ 倍
$2048$ ~2048~	$384$ ~384~	$5.4$ ~5.4~ 格	$4.5$ ~4.5~ 倍
$2048$ ~2048~	$512$ ~512~	$4.5$ ~4.5~ 格	$3.4$ ~3.4~ 倍

本文源代码在真实交互器上各跑 $500$ ~500~ 局：C++ 版通过率约 $87.0\%$ ~87.0\%~、Python 版约 $87.6\%$ ~87.6\%~，失败全部来自眼数关，落点失败 $0$ ~0~ 例；与理论上限 $88.33\%$ ~88.33\%~ 的偏差属抽样涨落。

源代码

#include <cmath>
#include <cstdio>

// 第 0 环环带：2048 ± 640
static const double BAND_LO = 1408.0;
static const double BAND_HI = 2688.0;

int main() {
    double th1;
    int eyes;
    printf("? 0 0\n");
    fflush(stdout);
    if (scanf("%lf %d", &th1, &eyes) != 2) return 0;

    double a1 = th1 * M_PI / 180.0;
    double ux = cos(a1), uz = sin(a1);

    double b = 0.5 * (BAND_LO + BAND_HI);   // 2048：环带中点
    const double SIDE = 384.0;              // 垂直偏移
    long long p2x = llround(b * ux - SIDE * uz);
    long long p2z = llround(b * uz + SIDE * ux);
    printf("? %lld %lld\n", p2x, p2z);
    fflush(stdout);

    double th2;
    if (scanf("%lf %d", &th2, &eyes) != 2) return 0;

    double a2 = th2 * M_PI / 180.0;
    double d1x = cos(a1), d1z = sin(a1), d2x = cos(a2), d2z = sin(a2);
    double den = d1x * d2z - d1z * d2x;

    double t = b;                           // 保底：前进到环带中点
    if (fabs(den) > 1e-12) {
        double cand = (p2x * d2z - p2z * d2x) / den;
        if (cand > BAND_LO - 256.0 && cand < BAND_HI + 256.0) t = cand;
    }
    printf("! %lld %lld\n", llround(t * d1x), llround(t * d1z));
    fflush(stdout);
    return 0;
}

import math
import sys

BAND_LO, BAND_HI = 1408.0, 2688.0


def main():
    def ask(x, z):
        sys.stdout.write('? %d %d\n' % (x, z))
        sys.stdout.flush()
        return sys.stdin.readline().split()

    first = ask(0, 0)
    if len(first) < 2:
        return
    a1 = math.radians(float(first[0]))
    ux, uz = math.cos(a1), math.sin(a1)

    b = 0.5 * (BAND_LO + BAND_HI)      # 2048：环带中点
    side = 384.0                       # 垂直偏移
    second = ask(round(b * ux - side * uz), round(b * uz + side * ux))
    if len(second) < 2:
        return
    a2 = math.radians(float(second[0]))

    den = math.cos(a1) * math.sin(a2) - math.sin(a1) * math.cos(a2)
    t = b                              # 保底：前进到环带中点
    if abs(den) > 1e-12:
        p2x, p2z = round(b * ux - side * uz), round(b * uz + side * ux)
        cand = (p2x * math.sin(a2) - p2z * math.cos(a2)) / den
        if BAND_LO - 256.0 < cand < BAND_HI + 256.0:
            t = cand
    sys.stdout.write('! %d %d\n' % (round(t * ux), round(t * uz)))
    sys.stdout.flush()


if __name__ == '__main__':
    main()

目前没有评论。