题目分析

本题模拟多个机器人在三维空间站表面移动，需要找出它们最早发生碰撞的时间。碰撞有两种情况：

1. 两个机器人在同一时刻到达同一个立方体表面
2. 两个机器人在同一时刻试图交换位置（对向移动）

算法思路

核心思想：周期检测 + 中国剩余定理

主要步骤：

1. 预处理机器人的移动路径

   • 计算每个机器人的完整移动循环
   • 记录每个"腿"（leg）的起点、朝向、方向和时间

2. 碰撞检测

   • 检查初始位置碰撞
   • 检查对向移动的碰撞
   • 检查同向移动在交点处的碰撞

3. 时间计算

   • 利用扩展欧几里得算法和中国剩余定理解决周期性问题

代码结构详解

1. 数据结构

struct Vec {
    int x, y, z;
    // 向量运算：取反、加法、数乘等
};

struct Leg {
    Vec s, f, d;  // 起点、朝向、方向
    int t;        // 该段移动时间
};

2. 关键算法组件

扩展欧几里得算法：

template<typename T> constexpr tuple<T, T, T> ExtendedGcd(T a, T b)

用于求解线性同余方程，处理周期性碰撞问题。

立方体交集计算：

void intersect(const Vec &a1, const Vec &a2, const Vec &b1, const Vec &b2, Vec *o1, Vec *o2)

计算两个立方体区域的交集，用于确定机器人的移动范围。

3. 主要处理流程

3.1 机器人路径计算

for (int i = 0; i < K; i++) {
    Leg leg;
    // 读取初始位置和方向
    for (;;) {
        // 计算当前leg的移动时间t
        // 检测碰撞并调整方向
        // 记录leg到路径中
        if (发现循环) break;
    }
}

移动规则：

• 当碰到障碍时：swap(leg.f, leg.d); leg.f = -leg.f;
• 当正常移动时：swap(leg.f, leg.d); leg.d = -leg.d;

3.2 碰撞检测

三种碰撞情况：

1. 初始位置碰撞：

if (r[i][0].s == r[j][0].s && r[i][0].f == r[j][0].f)
    ret = 0;

2. 对向移动碰撞：

if (r[j][ji] == -r[i][1]) {
    ret = min(ret, 计算时间);
}

3. 同向移动在交点碰撞：

if (r[i][ii].f == r[j][ji].f) {
    Vec a, b;
    intersect(...);  // 计算路径交点
    if (a == b) {    // 存在唯一交点
        // 使用中国剩余定理计算碰撞时间
        tie(x, y, g) = ExtendedGcd(rc[i], rc[j]);
        // 求解同余方程组
    }
}

4. 数学原理

中国剩余定理应用： 对于两个机器人的周期移动，碰撞时间需要满足：

t ≡ t1 (mod rc[i])
t ≡ t2 (mod rc[j])

其中 rc[i] 是机器人i的移动周期。

使用扩展欧几里得算法求解：

int64_t c = rc[i] * rc[j] / g;
int64_t t = (t1 * y) % rc[i] * rc[j] / g + (t2 * x) % rc[j] * rc[i] / g;
ret = min(ret, (t % c + c) % c);

算法复杂度

• 时间复杂度：O(K² × L²)，其中K是机器人数量，L是路径段数
• 空间复杂度：O(K × L)，存储每个机器人的移动路径

关键难点

1. 三维空间建模：准确表示机器人在立方体表面的移动
2. 周期性处理：机器人路径是循环的，需要处理周期性的碰撞
3. 方向变换：正确模拟机器人在边角处的转向行为
4. 数值计算：使用扩展欧几里得算法处理大数运算

样例分析

样例3：两个机器人初始位置相邻且对向移动，在时间0就发生交换位置碰撞。

样例2：三个机器人在单位立方体上移动，路径不会相交，输出"ok"。

该算法通过精细的路径模拟和数学计算，成功解决了复杂的三维空间碰撞检测问题。