那年多校联合训练第三场遇到一道让人印象深刻的几何题Triangle Collision题号 6798。题目描述很简单一个等边三角形里面放一个质点给它一个初速度碰到边界就完全弹性反弹问第 k 次碰撞发生的时刻。第一眼看到这不就是个纯模拟题嘛每次求一下与三条边的交点更新位置和速度循环 k 次完事。结果看到 k 的数据范围直接傻眼量级在 1e9 左右O(k) 的模拟就算每次操作只有几微秒也跑不完。后来翻题解才知道这类“三角形内反弹”问题有一个非常经典的处理套路镜像展开加旋转坐标系。把球在三角形里来回弹的折线轨迹变成一张无限展开平面上的直线运动碰撞次数直接变成一个取整运算。这篇文章把整个推导过程、二分思路、精度控制和调试心得完整记录下来希望能帮到同样被几何题折磨的选手。1. 题面还原与第一直觉为什么行不通1.1 题目到底想让我们算什么先还原一下题意。给定一个边长为 L 的等边三角形一个小球初始在三角形内部某个点速度向量为 (vx, vy)。小球和边界发生完全弹性碰撞也就是入射角等于反射角速度在法线方向上的分量反转。问从开始运动到第 k 次碰撞发生时一共经过了多少时间。这个问题有一个特别容易误导人的地方它披着“物理模拟”的外衣但本质是一个纯几何问题。因为三角形是等边三角形所有角度都是 60 度这种对称性决定了整个碰撞过程一定存在一个比逐帧模拟优雅得多的数学结构。如果直接去算“球下一秒钟撞到哪条边”其实是在跟自己的精度和常数过不去。1.2 按“真实世界”模拟的三宗罪第一宗罪是复杂度。k 到 1e9每次碰撞都要计算与三条边的交点时间再排序取最小哪怕这个操作是 O(1)一亿次运算也基本告别 AC 了。第二宗罪是浮点误差积累。碰撞个几千次后位置和速度方向都会因为浮点误差慢慢漂移最终可能完全偏离真实轨迹。第三宗罪是角点判定的复杂度爆炸。球不可能每次都干净地撞在一条边的内部当它恰好经过三角形顶点时同时触碰两条边速度两个分量同时反转这种特殊情况的模拟代码写起来非常恶心。所以遇到这种题第一反应不该是“模拟”而应该去思考碰撞过程能不能整体建模2. 把反弹熨平镜像展开的底层逻辑2.1 一次反射的另一种解释初中物理告诉我们光在平面镜上反射时入射角等于反射角。但还有一种等价描述你不需要让光线真的反弹你只要把这个平面镜沿着镜面翻折过去让光线在翻折后的世界里继续沿原来的直线传播它在真实世界中的轨迹完全一样。把这个思路用到三角形里。球撞到底边后向上反弹等价于把整个三角形沿底边向下翻折出一个镜像三角形球在镜像三角形里继续沿着原来的速度方向直线运动。下次再撞到边就再把当前的镜像三角形沿那条边翻折。每一步都不改变球的速度方向只是在不断翻折整个空间。于是真实三角形里那条曲折的折线轨迹在展开平面上变成了一条笔直的直线。这条直线穿过多少个三角形副本的边界就对应真实世界里发生了多少次碰撞。2.2 为什么正三角形能铺满平面不是所有三角形都能这样无限翻折下去还形成整洁的网格。但等边三角形可以因为它的每个内角都是 60 度六个 60 度角刚好拼成一个圆周 360 度所以三角形副本可以在平面上无缝隙、无重叠地铺满整张平面。这一点非常关键。展开后这个平面上的边界并不是一团乱麻而是被整理成了三组平行线。每一组平行线之间的间距都相等恰好是等边三角形的高 h L * sqrt(3) / 2。注意普通三角形虽然也能密铺平面但边界线无法整理成几组等距无限直线所以展开法在那种情况下会复杂得多。正三角形是“天选之子”这也是题目敢把 k 放到 1e9 的原因。2.3 从线段碰撞到直线穿越在展开平面上小球运动的直线每穿过一条三角形网格的边就对应一次真实碰撞。因为等边三角形密铺后同一方向的边界线段首尾相接拼成了贯穿整个平面的无限直线。所以“碰撞”这个事件变成了“直线与无限直线相交”这个更干净的问题。这里有个隐藏的好处我们不需要去判断直线具体穿过的是哪条线段只要统计它在三个方向上分别穿过了多少条平行线加起来就是总碰撞次数。三个方向的平行线组都是等距的这个“穿过多少条”就是一个楼层数之差的计算。3. 旋转坐标系与三组平行线的计数公式3.1 一组边界的法向投影想统计直线穿过了多少条“水平方向的平行线”最直接的办法是把坐标系旋转让这一组平行线变成水平线然后只看运动轨迹在竖直方向上的位移。更通用的说法是对每一组边界取它的单位法向量 n然后把运动轨迹投影到这个法向量方向上。投影值每增加一个平行线间距 h就代表穿过了一条该方向的边界线。假设三角形三个顶点分别放在 A(0, 0)、B(L, 0)、C(L/2, h)其中 h L * sqrt(3) / 2。三组边对应的单位法向量可以取方向法向量底边 AB(0, 1)边 BC(sqrt(3)/2, 0.5)边 CA(sqrt(3)/2, -0.5)这三个法向量都是单位向量而且方向刚好相差 120 度。用点积把坐标投影上去得到的有向距离在边界法向上是以 h 为周期变化的。3.2 三层求和为什么不是两条边有些同学可能会问三角形明明只有三条边为什么只需要统计三组平行线而不是六组因为每组平行线其实对应着两个方向相反的边界它们在展开平面上是同一组无限直线。底边 AB 及其所有镜像底边形成一组水平线边 BC 及镜像形成一组 60 度斜线边 CA 及镜像形成一组 -60 度斜线。所以三组就够了。每次碰撞发生球只会碰到这三组平行线中的一条。在展开平面的一般位置直线与一组平行线相交时不会恰好同时与另一组平行线相交所以三个方向各自统计的穿越次数之和就是总的碰撞次数。具体公式如下。令 p0 (x0, y0)p(t) p0 (vx * t, vy * t)对第 i 组边界s_i(t) dot(n_i, p(t)) c_i(t) | floor(s_i(t) / h) - floor(s_i(0) / h) |总碰撞次数count(t) c_1(t) c_2(t) c_3(t)为什么用 floor 相减因为 s_i / h 的 floor 值表示“当前投影点落在第几层”。起点在第 a 层终点在第 b 层中间穿过的层边界就是 |a - b|。这个逻辑特别像数楼层从 3 楼坐电梯到 7 楼中间经过了 7 楼、6 楼、5 楼、4 楼那几道楼板不应该是经过了几道楼层分界线是 4 道正好等于 floor(7) - floor(3)。速度方向如果反了就加绝对值。3.3 一个具体的投影例子为了验证公式不抽象我们构造一个最熟悉的情形。三角形 A(0, 0)、B(L, 0)、C(L/2, h)球从重心 G(L/2, h/3) 出发速度方向竖直向上。它最终会撞到顶点 C。在展开平面上画一下直线从重心向上穿过 C 点。分别算三个方向的投影底边方向起点投影为 h/3终点投影为 hfloor 从 0 变到 1撞了 1 次。边 BC 方向起点投影约 0.667h终点投影为 hfloor 从 0 变到 1撞了 1 次。边 CA 方向起点投影为 h/3 的某种偏移终点投影为 0floor 不变撞了 0 次。所以三个方向合计 2 次。但真实物理过程是球撞了一次顶点。这里就引出了著名的“角点重复计数”问题后面会专门讨论。4. 二分答案、精度与角点4.1 单调性让二分成立count(t) 随 t 增大而单调不减。因为时间越久直线走得越远穿过的边界线只会越来越多不会减少。这天然满足二分条件。于是题目从“求第 k 次碰撞的时间”变成“二分最小的 t使得 count(t) k”。check 函数每次 O(1) 计算三个方向投影和楼层差二分 70 到 100 次精度就非常稳定。4.2 check 函数的实现check 函数里只需要算三次投影bool check(long double t) p p0 v * t for i in 0..2: s0 dot(n_i, p0) s1 dot(n_i, p) c_i abs(floor(s1/h EPS) - floor(s0/h EPS)) return c0 c1 c2 k这里加 EPS 是为了处理“刚好到达边界”的情况。比如小球在某个时刻正好撞到一条边如果直接用 floor(s1/h)由于浮点误差可能算出比真实少 1 的情况导致 check 在临界点返回 false。加一个极小的 EPS 可以让“正好到达边界”被算进碰撞次数。注意 EPS 不能太大否则会把还没发生碰撞的相邻时刻提前判成 true。一般取 1e-9 左右比较安全。4.3 角点和“多算”其实不影响二分刚才从重心竖直向上的例子说明球经过三角形顶点时三个方向的楼层差之和比真实碰撞次数多算了一次。很多人看到这里会慌觉得公式不严谨。但仔细想一下二分的判断逻辑就会发现这个偏差不会影响最终答案。二分找的是最小的 t使得 count(t) k。如果第 k 次碰撞恰好发生在某个顶点那么在 t 到达这个顶点之前count(t) k 一定成立。到达顶点的那一刻count(t) 可能因为重复计数而大于等于 kcheck 返回 true二分就把右边界往左收。而在顶点之前的任意时刻count(t) 都是严格的真实值都小于 k。所以二分收敛到的时刻依然是最早发生第 k 次碰撞的时刻。换句话说我们允许 count 函数在边界点上偏大只要它不在边界点之前提前偏大就行。这个性质由“非顶点处三个方向不会同时穿越边界”保证。4.4 浮点误差控制这个问题最坑的部分其实是精度。k 到 1e9 的时候t 的答案可能非常大vx * t 乘出来可能到 1e12 甚至更大。用 double 在 1e12 量级上再做除法取 floor很容易在边界附近差出 1一旦差 1count 就错得离谱。建议直接用 long double。如果题目环境对 long double 支持不好也可以把所有坐标和速度先除以 h让边界间距变成 1再做投影能明显减少数值范围。我更推荐后一种把整个坐标系缩放到三角形高度为 1所有平行线间距为 1计算量小误差也小。二分上界也要小心。如果 r 选得太小check(r) 一直返回 false二分就会压着右边界不动最后答案错误。稳妥做法是从一个初始值开始倍增直到 check 返回 truelong double r 1; while (!check(r)) r * 2;然后对这个 r 二分100 次迭代足够。5. 完整代码骨架与调试实录5.1 核心代码结构下面是这个思路的可复现核心代码骨架关键逻辑都在注释里#include bits/stdc.h using namespace std; using ld long double; ld L, h; ld x0, y0, vx, vy; long long k; ld nx[3] {0, (ld)sqrt(3) / 2, (ld)sqrt(3) / 2}; ld ny[3] {1, (ld)0.5, -(ld)0.5}; ld proj(int i, ld x, ld y) { return nx[i] * x ny[i] * y; } long long cross_cnt(int i, ld t) { ld tx x0 vx * t; ld ty y0 vy * t; ld s0 proj(i, x0, y0) / h; ld s1 proj(i, tx, ty) / h; long long a (long long)floor(s0 1e-9L); long long b (long long)floor(s1 1e-9L); return llabs(a - b); } bool check(ld t) { long long total 0; for (int i 0; i 3; i) { total cross_cnt(i, t); } return total k; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin L x0 y0 vx vy k; h L * (ld)sqrt(3) / 2; ld l 0, r 1; while (!check(r)) r * 2; for (int it 0; it 100; it) { ld mid (l r) / 2; if (check(mid)) r mid; else l mid; } cout fixed setprecision(10) (l r) / 2 \n; return 0; }5.2 用暴力模拟对拍校准这类题的代码不长但角点、EPS 这些地方很容易出错必须写一个对拍的暴力模拟来兜底。暴力模拟的思路是事件驱动记录当前位置和速度每次计算与三条边的最近交点时间取最小值推进到这个时间点然后翻转对应边法线方向上的速度分量。特别注意顶点情况如果与两条边的交点时间几乎相等就认为发生了顶点碰撞翻转两个分量算一次事件。在小数据下跑几千次碰撞把碰撞时刻和二分结果对比误差在 1e-6 以内就算通过。对拍时绝对不要只随机测数据。必须手动构造几组坑数据比如“从重心竖直向上”这是标准的角点测试“从某条边中点的法线方向出发”这是测试对称性“速度方向几乎平行于某条边”这是测试长时间无碰撞的边界情况。5.3 现场踩过的坑踩坑一第一版用 double 计算样例能过大随机数据直接错。排查半天发现是 t 很大时vx * t 的数值已经到 1e10 量级double 的有效数字只剩十几位再除 h 后取 floor在边界附近经常差 1。换成 long double 立刻稳定。踩坑二二分右边界一开始直接拍了个 1e9某种特殊数据下答案超过这个值二分结果永远不对。后来改成倍增找上界再也没在这上面翻车。踩坑三三个方向的法向量不能随便取。有人简化成只取两个方向然后发现有斜边碰撞漏数。密铺网格必须三组平行线都统计少了任何一组都是错的。踩坑四EPS 加得太狠。第一次写了 1e-6结果某个数据恰好离边界很近导致 check 提前返回 true答案偏大。最后把 EPS 调成 1e-9 才稳定。最后聊聊个人感受。当时看到题解里“镜像展开”这个操作时真的有被惊艳到一个看似需要逐次反射的物理过程通过翻折空间就变成一条直线碰撞次数直接变成楼层差求和。后来遇到好几道“小球在闭合几何图形里反弹”的题目我都会先想一步这个图形能不能密铺密铺之后边界是不是规则平行线如果是那展开法十有八九是最优雅的解法。这种把一个动态过程“降维”成静态几何结构的思路比背任何模板都有用。希望这篇文章能把同样的灵感传递给你。