多校第三场这道 6798 Triangle Collision比赛时我盯着题目看了十分钟第一反应是这不就是高中物理的反弹小球吗把速度翻个符号模拟 k 次不就完了。可再一看 k 的范围1e18直接抽了口冷气。模拟一次反弹是 O(1)模拟 1e18 次那就是天文数字这条路想都不用想。真正让我觉得这题漂亮的地方在于它把碰撞这个看似必须逐次处理的事件硬生生变成了数平行线镜面反射用展开法换成直线运动等边三角形用旋转坐标系拆成三个独立方向最后二分答案把第 k 次碰撞变成了 O(1) 的判定函数。这篇文章就按这个思路讲为什么模拟必死、展开法到底在干什么、三个方向的高度怎么定义、碰撞次数怎么数最后给出完整可用的代码和我在实作中踩过的浮点坑。适合想搞懂计算几何套路、或者比赛后复盘的人读推导过程我会从头写不需要你提前看过题解。1. 为什么模拟反弹是死路k1e18 背后的信号1.1 模拟一次反弹看起来很简单但一万次之后就失控了先说说最直觉的做法会遇到什么。每次小球撞到三角形某条边流程是算出小球到三条边的距离和方向找到最早碰到的边把小球移动到碰撞点然后把速度向量关于那条边做镜面反射。这个流程本身不难三行向量运算的事。可问题在于碰撞次数不是几十几百而是 k一个能到 1e18 的数。假设一秒钟能跑 1e8 次碰撞模拟跑完 1e18 次也需要 1e10 秒约 317 年。这不是优化常数能解决的问题必须从算法层面换思路。比时间更隐蔽的是精度问题。模拟是逐步推进的每步都要算距离、交点、反射向量浮点误差会逐步累积。碰撞次数少的时候没问题碰撞次数一多路径就会一点点漂移最后完全偏离真实轨迹。哪怕 k 只有 1e5double 模拟都可能出问题更不要说 1e18。所以模拟到底这条路从时间和精度两个维度都是死路。1.2 展开法每一次反射都是把世界翻进镜子里那怎么办这里有一个物理和几何里都很经典的操作展开法unfolding。核心思想一句话镜面反射的路径可以看成在镜像世界里的直线路径。想象一束光从 A 点出发经过平面镜反射后到达 B 点。如果我把平面镜另一侧的世界翻到镜子里把 A 在镜子里的镜像找出来那么光路 A→镜面→B 的路径长度恰好等于 A 的镜像点→镜面→B 的直线距离。换句话说反射一次就相当于给整个世界做一次镜像翻转光在展开后的世界里不再反射而是直线前进。小球撞三角形边也是一样。每撞一次边我就把整个三角形关于那条边镜像翻转一次。在真实的物理世界里小球碰边后反弹了但在不断翻转的展开世界里小球其实一直在走直线。你不需要真的去翻转整个世界你只需要知道展开空间里有一条无限直线它每穿过一条翻出来的三角形边就对应物理世界里的一次碰撞。这个想法很通用但用在任意三角形上会遇到一个问题镜像翻转之后新世界不一定能无缝拼回去。普通三角形的镜像继续镜像最终会出现缝隙或重叠展开空间根本不是一个规则的网格。只有某些特殊角度能做到无缝铺满整个平面等边三角形就是最漂亮的那一个。1.3 等边三角形的特殊地位60 度角让世界密铺成网格为什么等边三角形能铺满平面?因为它的内角是 60 度。沿着一条边镜像得到的新三角形和原来的三角形拼在一起;再沿着新边镜像又能继续拼下去。由于 60 度是 360 度的整数分之一不断镜像形成的图案不会重叠也不会留缝最终整个平面会被正三角形网格铺满。这个网格的边分为三组平行线。一组是水平的底边方向一组是左斜边方向一组是右斜边方向。每一组平行线之间的间距都是同一个值:等边三角形的高 h。设边长为 L那么 h √3/2 · L。这一步非常关键因为它把碰撞次数变成了穿越平行线条数。展开后的直线每穿过水平方向的一条线对应物理世界里一次撞底边每穿过左斜方向的一条线对应撞左斜边每穿过右斜方向的一条线对应撞右斜边。于是问题就从模拟每次反弹变成了数这条直线穿过了多少条平行线。2. 旋转坐标系把三条边统一成三个高度2.1 先建坐标系定义三个方向上的高度为了把穿过多少条平行线这件事算出来需要给每个方向定义一个坐标。我习惯把三角形放在平面直角坐标系里让左下角顶点在原点底边沿 x 轴这样三个顶点分别是A (0, 0)B (L, 0)C (L/2, h)其中 h √3/2 · L。三条边的方程分别是底边 ABy 0左斜边 AC√3·x - y 0右斜边 BC√3·x y √3·L注意三角形内部任意一点在这三个方向上都有一个高度而且都能落在 0 到 h 之间。定义三个量H0 yH1 (√3·x - y) / 2H2 (√3·x y) / 2我管它们叫三个方向上的带符号高度。验证一下底边方向y0 在底边上yh 在最高点 C 处H1 在左斜边 AC 上等于 0在过 B 点的平行线上等于 hH2 在过 A 点的平行线上等于 0在右斜边 BC 上等于 h。所以说三角形内部任意一点都满足 H0、H1、H2 同时在 [0, h] 区间里。2.2 速度向量也要投影到三个法线方向小球有速度向量 (vx, vy)。在时间 t 内位移是 (vx·t, vy·t)。三个方向上的高度会线性变化各自的速率就是把速度投影到对应法线方向上。具体算一下H0 的变化率vy直接看 y 方向H1 的变化率(√3·vx - vy)/2H2 的变化率(√3·vx vy)/2记这三个值为 v0、v1、v2那么H0(t) H0(0) v0·tH1(t) H1(0) v1·tH2(t) H2(0) v2·t到这里你会发现三维的三角形碰撞问题被拆分成了三个一维的匀速直线运动。每个方向只看自己的高度随时间怎么变。2.3 展开网格里穿越线族的次数等于碰撞次数展开后的正三角形网格三组平行线在每个方向上的方程其实非常整齐。以 H1 为例所有平行于左斜边的线都满足H1 m·hm 是任意整数因为相邻两条平行线的 H1 值恰好相差 h也就是一条边到另一条平行边的高。同理H0 m·h 是底边方向所有平行线的方程H2 m·h 是右斜边方向所有平行线的方程。现在看小球在某个方向上的运动。初始时它在三角形内部所以 H_i(0) 严格在 (0, h) 之间也就是它不在任何一条网格线上也不在边界上。经过时间 t 后H_i(t) 变成了另一个值。直线路径在这个方向上穿过了多少条网格线呢?如果 H_i(t) 向上增长从不到 h 涨到超过 h路径会依次经过 h、2h、3h…… 这些点。经过的条数正好是 floor(H_i(t)/h)。比如 h10H_i(t)23那么路径经过了 10 和 20 两条线floor(23/10)2正确。如果速度方向相反H_i(t) 会从正数一路减小到负数路径会经过 0、-h、-2h…… 此时 floor(H_i(t)/h) 是负数。比如 H_i(t)-17h10floor(-17/10)-2表示反向穿过了 2 条线。取绝对值就是碰撞次数。所以单个方向的穿越次数是cnt_i(t) |floor(H_i(t) / h)|总碰撞次数cnt(t) cnt0(t) cnt1(t) cnt2(t)这就是整道题最核心的公式。需要特别强调的是这里 H_i(0) 必须在 (0, h) 内也就是小球初始位置不能在三角形边上。绝大多数题目数据都保证初始点在三角形内部这一点基本不会出问题。2.4 旋转坐标系这个名字到底指什么很多题解管这个技巧叫旋转坐标系其实并不是真的要把整个坐标轴旋转三次。它的本质是分别沿着三条边的法线方向做投影相当于在三个旋转过的坐标架里只看一维运动。打个比方你在看一块正三角形地砖上的一只蚂蚁。蚂蚁会撞到砖的三条边你想知道它什么时候撞到第 k 次。与其追踪蚂蚁的完整二维路径不如同时架三把尺子一把垂直于底边一把垂直于左斜边一把垂直于右斜边。每把尺子只记录蚂蚁在对应方向上的位移。蚂蚁每撞一次某条边对应那把尺子上的读数就跨过了一个刻度。三把尺子的跨刻度总数就是碰撞次数。这个视角一旦建立三维坐标就只是障眼法真正有用的只是这三个投影值。3. 二分答案把求时刻变成数次数3.1 碰撞次数函数是单调不减的公式有了接下来要解决第 k 次碰撞的时刻。直接解方程是不可能的因为 cnt(t) 是一个带 floor 的分段函数但它的结构非常适合二分。为什么因为 cnt(t) 关于 t 是单调不减的。看单个方向H_i(t) H_i(0) v_i·t 是线性函数。如果 v_i 0H_i 一直增大floor(H_i/h) 只会越来越大或保持不动取绝对值后仍然单调不减如果 v_i 0H_i 一直减小floor 会变成越来越负的数但绝对值越来越大还是单调不减如果 v_i 0这个方向贡献恒定。三个方向加起来总碰撞次数自然是单调不减的。这带来一个非常舒服的性质给定时间 t如果 cnt(t) k说明第 k 次碰撞发生在这个时刻之前如果 cnt(t) k说明还没撞够。于是可以在时间轴上二分找到最小的 t 使得 cnt(t) k这就是答案。3.2 O(1) 的判定函数 check(t)判定函数的实现可以很短先把三个方向的高度算出来除以 h 取 floor加绝对值求和。写成公式就是check(t): H0 y vy*t H1 ((√3*x - y) (√3*vx - vy)*t) / 2 H2 ((√3*x y) (√3*vx vy)*t) / 2 cnt |floor(H0/h)| |floor(H1/h)| |floor(H2/h)| return cnt k整个过程没有循环、没有递归一次判定只做常数次浮点运算和取整操作。二分一百次左右总复杂度是 O(100·T)T 再大也扛得住。3.3 上界选择与精度控制二分的上界不能乱给也不能给得太小。最粗暴可靠的办法是倍增从 hi1 开始每次翻倍直到 check(hi) 为真。因为 check 函数单调一旦真就说明当前上界一定超过答案。最坏的答案有多大k 最大到 1e18三角形边长如果很大而速度很小单次碰撞之间要走的路程可能很长。粗略估算下时间可能到 1e21 甚至 1e22 的量级。倍增上界会把 hi 停在实际答案的两倍以内不会无限制增长。用 double 做这个循环1e22 也能表示但后面会说到 double 在精度上有隐患。二分次数我用 100 到 120 次。假设最坏区间长度 1e22二分 100 次后区间大约是 1e22 / 2^100约 1e-8已经完全满足题目要求的 1e-6 精度。3.4 用一个小例子验证公式空对空推公式容易出错我拿一个最简单的场景手算一遍。设 L1h≈0.866025。小球初始在三角形中心坐标为 (0.5, √3/6)约 (0.5, 0.288675)速度 vx1vy0。求第一次碰撞时间。初始的三个高度H0 0.288675H1 (√3·0.5 - 0.288675)/2 (0.866025 - 0.288675)/2 0.288675H2 (√3·0.5 0.288675)/2 (0.866025 0.288675)/2 0.577350速度投影v0 0v1 (√3·1 - 0)/2 0.866025v2 (√3·1 0)/2 0.866025第一次碰撞发生在 H2 到达 h 的时候0.577350 0.866025·t 0.866025解得 t ≈ 0.333333也就是 1/3 秒。而 H1 要到 0.866025需要 0.666667 秒所以第一次确实是撞右斜边。这个结果符合物理直觉中心的小球水平向右最早撞到的是右边的斜边。如果继续用 check(1) 验证t1 时H1 变成 0.2886750.8660251.154700floor(1.154700/0.866025)1H2 变成 0.5773500.8660251.443375floor(1.443375/0.866025)1总和 2。说明到 t1 时已经发生了两次碰撞与展开空间直线穿过了两条网格边界的结论一致。4. 代码实现与浮点深坑4.1 可以直接抄的参考代码下面是我比赛后整理的版本用 long double 保证精度二分 120 次保证收敛。#include bits/stdc.h using namespace std; typedef long long ll; typedef long double ld; const ld SQRT3 sqrt((ld)3.0); ld L, x, y, vx, vy, h; ll k; ld getH0(ld t) { return y vy * t; } ld getH1(ld t) { return (SQRT3 * x - y (SQRT3 * vx - vy) * t) * 0.5L; } ld getH2(ld t) { return (SQRT3 * x y (SQRT3 * vx vy) * t) * 0.5L; } ll countCollisions(ld t) { ld a[3] { getH0(t), getH1(t), getH2(t) }; ll res 0; for (int i 0; i 3; i) { ld q a[i] / h; ll f (ll)floor(q); res llabs(f); if (res k) return res; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; cout fixed setprecision(10); while (T--) { cin L x y vx vy k; h SQRT3 * L * 0.5L; ld lo 0.0L, hi 1.0L; while (countCollisions(hi) k) { hi * 2.0L; } for (int it 0; it 120; it) { ld mid (lo hi) * 0.5L; if (countCollisions(mid) k) { hi mid; } else { lo mid; } } cout (double)hi \n; } return 0; }这个代码可以过题但有几个细节值得展开说都是我在调试时踩过的坑。4.2 大数时间下double 的精度可能不够很多人写这题第一版会用 double小数据测试没问题一交就错。问题出在大数计算上。答案可能到 1e21 甚至更大。double 的尾数只有 52 位在 1e22 附近一个 ULP最小可分辨单位大约是一千多。也就是说double 连一万以内的整数都表示不精确。虽然这不是随机误差但在做除法、floor 的时候误差会让计数偶尔差 1。比如某个方向实际 H_i(t)/h 3.0000000001double 算出来可能是 2.9999999999floor 之后就从 3 变成 2直接少算一次碰撞。更麻烦的是二分收敛到边界时刻时check 函数对边界附近的判定不稳定最终答案可能偏出精度要求。解决办法是换 long double。在大多数评测机上long double 是 80 位扩展精度尾数有 64 位相对精度比 double 高很多。虽然 1e22 量级下它的 ULP 也有一千左右但除以 h 之后误差会被压缩到 0.1 附近足以保证 floor 不出错。如果你用 double 通过二进制上界倍增连续跑很多组数据也许能过但没必要赌这个运气。4.3 floor 对负数的行为很容易搞错C 的 floor 是向负无穷取整不是向零取整。这一点非常关键。小球速度投影如果为负H_i(t) 会变成负数。比如 h10H_i(t)-17floor(-17/10) 等于 -2而不是 -1。很多新手在这里会写成(ll)(q)直接截断小数部分得到 -1碰撞次数就会少算 1。正确做法是先 floor 再取绝对值也就是代码里的llabs((ll)floor(q))。还有一种更隐蔽的错误有人想先取绝对值再 floor写成(ll)floor(fabsl(q))。看起来结果一样实际上在 q 为正数时等价但 q 为负数时不行因为 floor 的边界行为变了。比如 q-2.0正确应该是 2 次碰撞floor(fabsl(-2.0))floor(2.0)2看起来一样;但 q-2.1正确绝对值是 3因为 floor(-2.1)-3取绝对值 3而先取绝对值再 floor 得到 2。方向反的时候差异就出来了。所以一定要记住顺序先 floor再取绝对值。4.4 边界条件起点在边上、撞到顶点、速度为零理论上这个模型很干净但实际题目数据偶尔会在边界上恶心人一下。如果起点恰好在某条边上H_i(0) 可能等于 0 或 h这时候 floor(H_i(0)/h) 不再是 0我的计数公式会差一点。比如起点在底边 y0 上速度方向斜向下那么 t0 时刻实际上就已经碰到边了。官方数据通常保证初始点在三角形内部也就是严格不在边界上所以上面的代码不需要特判。如果你自己在造数据或做变体就要注意这一点。撞到顶点的情况也值得一提。展开空间里一个顶点是两条平行线族相交的点。直线正好穿过顶点时两个方向会同时各计一次碰撞总数加 2。物理世界中小球撞到三角形顶点可以理解为同时撞到两条边也可以理解为只算一次碰撞取决于题目如何定义。好在二分求首达时刻顶点碰撞只是恰好边界上的一次事件对答案的数值影响不大。题目数据一般也不会设计成答案正好卡在顶点碰撞瞬间。还有一种极端情况是速度向量为零向量。如果 vxvy0小球永远不动cnt(t) 恒为 0第 k 次碰撞不存在。正常题目不可能出这种数据但如果你在扩展练习中遇到记得先判掉。至于输出我用 fixed 和 setprecision(10) 输出 double已经足够满足精度要求。long double 的 cout 在某些评测机上可能格式不太统一转成 double 输出反而省心。二分 120 次后误差远小于 1e-10转 double 不会有问题。最后再分享一个我个人的体会。做算法题最怕的不是公式复杂而是公式里藏着隐含假设。这题的三个假设——展开法成立、初始点在内部、速度向量不为零——缺一个都会让结论崩掉。但反过来一旦你理清了这几个假设整道题的代码其实不到 60 行。我后来遇到六边形网格、蜂窝状反射这类问题还是会先想到把方向拆开、把反射展开这两板斧很多看起来复杂的几何题本质都是在等边三角形这种密铺结构里数平行线而已。