题意分析

题目要求计算两辆汽车碰撞时最先接触的部件编号。每辆车由后左角 $(x,y)$、前左角 $(u,v)$、车宽 $w$ 描述，速度为 $s$。汽车的部件编号通过代码中的几何建模确定：

• 每辆车生成8个关键点（编号1-4及中点）和8条线段（编号1-4的线段，每段对应两个部件）。
• 部件编号规则：线段的 id 由 $(i+1)\%8/2+1$ 计算，其中 $i$ 为线段索引，因此线段0-7对应部件1-4的循环（例如线段0和1对应部件1，线段2和3对应部件2，以此类推）。

解题思路

1. 几何建模：

   • 根据输入参数构建每辆车的8个关键点和8条线段。关键点包括后左（id=1）、前左（id=2）、前右（id=3）、后右（id=4）及其中点（id取相邻点的最小值）。
   • 线段由相邻关键点连接而成，每个线段对应一个部件编号（1-4）。

2. 速度向量计算：

   • 计算每辆车的行驶方向向量（前左角 - 后左角的单位向量），乘以速度得到速度向量 $\vec{V1}$ 和 $\vec{V2}$。
   • 相对速度向量为 $\vec{V1} - \vec{V2}$（用于判断A车相对于B车的运动）。

3. 碰撞检测：

   • 对每辆车的每个关键点，计算其相对于另一辆车的运动轨迹（直线），检测该轨迹与另一辆车的线段是否相交。
   • 记录交点距离当前点的最小距离，确定最先接触的部件组合。

4. 结果处理：

   • 分别计算A车撞B车和B车撞A车的最短碰撞距离，比较两者：
     • 若距离相等，取部件编号较小的组合；
     • 否则取距离更短的组合作为结果。

标准代码

#include <iostream>
#include <cstdio>
#include <cmath>

#define esp 1e-6

using namespace std;

// 点结构
typedef struct pnode {
    double x, y;
    int id;
    pnode(double a, double b) : x(a), y(b) {}
    pnode(double a, double b, int i) : x(a), y(b), id(i) {}
    pnode() {}
} point;

// 直线结构
typedef struct lnode {
    double x, y, dx, dy;
    lnode(point a, point b) : x(a.x), y(a.y), dx(b.x - a.x), dy(b.y - a.y) {}
    lnode() {}
} line;

// 线段结构
typedef struct snode {
    point p1, p2;
    int id;
    snode(point a, point b, int i) : p1(a), p2(b), id(i) {}
    snode() {}
} segment;

// 车结构
typedef struct cnode {
    point p[8];
    segment s[8];
} car;

// 构造汽车的关键点和线段
car madecar(double x, double y, double u, double v, double w) {
    car Car;
    Car.p[0] = point(x, y, 1);          // 后左 (id=1)
    Car.p[2] = point(u, v, 2);          // 前左 (id=2)
    double d = sqrt((x - u) * (x - u) + (y - v) * (y - v));
    point r = point((v - y) * w / d, (x - u) * w / d);
    Car.p[4] = point(u + r.x, v + r.y, 3); // 前右 (id=3)
    Car.p[6] = point(x + r.x, y + r.y, 4); // 后右 (id=4)
    
    // 生成中点（id取相邻点的最小值）
    for (int i = 0; i < 8; i += 2) {
        point m;
        m.x = (Car.p[i].x + Car.p[(i + 2) % 8].x) / 2;
        m.y = (Car.p[i].y + Car.p[(i + 2) % 8].y) / 2;
        m.id = min(Car.p[i].id, Car.p[(i + 2) % 8].id);
        Car.p[i + 1] = m;
    }
    
    // 生成线段并分配部件编号（1-4）
    for (int i = 0; i < 8; ++i) {
        Car.s[i] = segment(Car.p[i], Car.p[(i + 1) % 8], 0);
        Car.s[i].id = (i + 1) % 8 / 2 + 1; // 线段0-1对应部件1，2-3对应部件2，依此类推
    }
    return Car;
}

// 两点间距离
double dist(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// 判断两直线是否相交（考虑线段范围）
bool lcrossl(line a, line b) {
    double t1 = b.dx * (a.y - b.y) - b.dy * (a.x - b.x);
    double t2 = b.dx * (a.y + a.dy - b.y) - b.dy * (a.x + a.dx - b.x);
    return (t1 - esp) * (t2 - esp) <= 0;
}

// 求两直线的交点
point crosspoint(line l, line m) {
    point a = point(m.x, m.y);
    point b = point(m.x + m.dx, m.y + m.dy);
    if (m.dx * l.dy == m.dy * l.dx) { // 平行或共线
        if (dist(point(l.x, l.y), a) < dist(point(l.x, l.y), b))
            return a;
        else
            return b;
    } else { // 正常相交
        double a1 = -l.dy, b1 = l.dx, c1 = l.dx * l.y - l.dy * l.x;
        double a2 = -m.dy, b2 = m.dx, c2 = m.dx * m.y - m.dy * m.x;
        double x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
        double y = (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1);
        return point(x, y);
    }
}

// 结果结构
typedef struct anode {
    int id1, id2;
    double dis;
    anode(int a, int b, double d) : id1(a), id2(b), dis(d) {}
} answer;

// 计算a车的部件与b车的部件的最早碰撞
answer crash(car a, car b, point v) {
    double dis = 1e20;
    int id1 = 1, id2 = 1; // 初始化为最小部件编号
    for (int i = 0; i < 8; ++i) { // a车的关键点
        point start = a.p[i];
        point end = point(start.x + v.x, start.y + v.y); // 运动后的点
        line path(start, end); // a车关键点的运动轨迹
        for (int j = 0; j < 8; ++j) { // b车的线段
            segment seg = b.s[j];
            line seg_line(seg.p1, seg.p2);
            if (lcrossl(path, seg_line)) { // 轨迹与线段相交
                point intersect = crosspoint(path, seg_line);
                double d = dist(start, intersect); // 交点距离起点的距离
                if (fabs(dis - d) < esp) { // 距离相等，取更小的部件编号
                    if (start.id < id1) id1 = start.id;
                    if (seg.id < id2) id2 = seg.id;
                } else if (d + esp < dis) { // 更小的距离，更新结果
                    dis = d;
                    id1 = start.id;
                    id2 = seg.id;
                }
            }
        }
    }
    return answer(id1, id2, dis);
}

int main() {
    double x1, y1, u1, v1, w1, s1, x2, y2, u2, v2, w2, s2;
    while (scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &u1, &v1, &w1, &s1) != EOF) {
        scanf("%lf%lf%lf%lf%lf%lf", &x2, &y2, &u2, v2, w2, s2);
        
        // 构建两车的几何模型
        car A = madecar(x1, y1, u1, v1, w1);
        car B = madecar(x2, y2, u2, v2, w2);
        
        // 计算速度向量（单位方向向量 × 速度）
        double d1 = dist(A.p[0], A.p[2]);
        point V1 = point((u1 - x1) * s1 / d1, (v1 - y1) * s1 / d1); // A车速度向量
        double d2 = dist(B.p[0], B.p[2]);
        point V2 = point((u2 - x2) * s2 / d2, (v2 - y2) * s2 / d2); // B车速度向量
        
        // 计算A相对B的速度和B相对A的速度
        answer an1 = crash(A, B, point(V1.x - V2.x, V1.y - V2.y)); // A撞B
        answer an2 = crash(B, A, point(V2.x - V1.x, V2.y - V1.y)); // B撞A
        
        // 处理结果：若同时碰撞，取较小部件；否则取更早的碰撞
        if (fabs(an1.dis - an2.dis) < esp) {
            int p1 = min(an1.id1, an2.id2);
            int p2 = min(an1.id2, an2.id1);
            printf("%d %d\n", p1, p2);
        } else if (an1.dis + esp < an2.dis) {
            printf("%d %d\n", an1.id1, an1.id2);
        } else {
            printf("%d %d\n", an2.id2, an2.id1); // B撞A的结果需交换部件顺序
        }
    }
    return 0;
}

代码说明

1. 几何建模：

   • madecar 函数根据输入参数生成汽车的8个关键点和8条线段，关键点的编号对应部件位置，线段的编号通过索引计算得到部件编号（1-4）。

2. 碰撞检测：

   • crash 函数遍历每辆车的关键点和另一辆车的线段，计算关键点运动轨迹与线段的交点，记录最短碰撞距离和对应的部件编号。

3. 相对运动：

   • 通过相对速度向量（A车速度 - B车速度）判断A车相对于B车的运动，反之亦然，确保双向检测碰撞。

4. 结果处理：

   • 比较双向碰撞的距离，处理同时碰撞的情况（取较小部件编号），确保输出符合题目要求。