解题思路

1. 输入处理：解析每个机器人的移动路径，生成时间段列表。
2. 事件生成：对于每对机器人，计算它们之间所有可能的通信时间窗口，生成进入和离开事件。
3. 事件排序：按时间顺序处理事件，进入事件优先。
4. 传播处理：维护已获得数据的机器人集合，当两个机器人在通信范围内且其中一个有数据时，传播数据。
5. 结果输出：按字典序输出所有获得数据的机器人。

代码示例

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <iomanip>

using namespace std;

struct Segment {
    double t_start, t_end;
    double x, y;
    double vx, vy;
};

struct Robot {
    string name;
    vector<Segment> segments;
};

struct Event {
    double time;
    int i, j;
    bool is_enter;
};

bool compareEvents(const Event& a, const Event& b) {
    if (a.time != b.time) return a.time < b.time;
    return a.is_enter && !b.is_enter; // Enter events first
}

void calculateIntersections(int i, int j, const Robot& ri, const Robot& rj, double R, vector<Event>& events) {
    for (const auto& seg_i : ri.segments) {
        for (const auto& seg_j : rj.segments) {
            double t_start = max(seg_i.t_start, seg_j.t_start);
            double t_end = min(seg_i.t_end, seg_j.t_end);
            if (t_start >= t_end) continue;

            // Relative motion parameters
            double dx0 = (seg_i.x - seg_j.x) + seg_i.vx * (t_start - seg_i.t_start) - seg_j.vx * (t_start - seg_j.t_start);
            double dy0 = (seg_i.y - seg_j.y) + seg_i.vy * (t_start - seg_i.t_start) - seg_j.vy * (t_start - seg_j.t_start);
            double dvx = seg_i.vx - seg_j.vx;
            double dvy = seg_i.vy - seg_j.vy;

            // Quadratic equation: (dx0 + dvx*t)^2 + (dy0 + dvy*t)^2 = R^2
            double a = dvx * dvx + dvy * dvy;
            double b = 2 * (dx0 * dvx + dy0 * dvy);
            double c = dx0 * dx0 + dy0 * dy0 - R * R;

            if (a == 0) {
                if (b == 0) {
                    if (c <= 0) {
                        events.push_back({t_start, i, j, true});
                        events.push_back({t_end, i, j, false});
                    }
                } else {
                    double t = -c / b;
                    if (t >= t_start && t <= t_end) {
                        if (b > 0) {
                            events.push_back({t_start, i, j, true});
                            events.push_back({t, i, j, false});
                        } else {
                            events.push_back({t, i, j, true});
                            events.push_back({t_end, i, j, false});
                        }
                    }
                }
                continue;
            }

            double disc = b * b - 4 * a * c;
            if (disc < 0) {
                double mid_t = (t_start + t_end) / 2;
                double dx = dx0 + dvx * (mid_t - t_start);
                double dy = dy0 + dvy * (mid_t - t_start);
                if (dx*dx + dy*dy <= R*R) {
                    events.push_back({t_start, i, j, true});
                    events.push_back({t_end, i, j, false});
                }
                continue;
            }

            double sqrt_disc = sqrt(disc);
            double t1 = (-b - sqrt_disc) / (2 * a);
            double t2 = (-b + sqrt_disc) / (2 * a);

            vector<double> valid_times;
            if (t1 >= t_start && t1 <= t_end) valid_times.push_back(t1);
            if (t2 >= t_start && t2 <= t_end) valid_times.push_back(t2);

            if (valid_times.size() == 2) {
                sort(valid_times.begin(), valid_times.end());
                events.push_back({valid_times[0], i, j, true});
                events.push_back({valid_times[1], i, j, false});
            } else if (valid_times.size() == 1) {
                double mid_t = valid_times[0] + 1e-9;
                double dx = dx0 + dvx * (mid_t - t_start);
                double dy = dy0 + dvy * (mid_t - t_start);
                if (dx*dx + dy*dy <= R*R) {
                    events.push_back({valid_times[0], i, j, true});
                    events.push_back({t_end, i, j, false});
                } else {
                    events.push_back({t_start, i, j, true});
                    events.push_back({valid_times[0], i, j, false});
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, T, R;
    while (cin >> N >> T >> R && N != 0) {
        vector<Robot> robots(N);
        for (int i = 0; i < N; ++i) {
            cin >> robots[i].name;
            int k;
            cin >> k;
            double prev_t = -1;
            for (int j = 0; j < k; ++j) {
                double t, vx, vy;
                cin >> t >> vx >> vy;
                if (j == 0) {
                    prev_t = t;
                    robots[i].segments.push_back({t, t, vx, vy, 0, 0});
                } else {
                    robots[i].segments.back().t_end = t;
                    robots[i].segments.back().vx = vx;
                    robots[i].segments.back().vy = vy;
                    prev_t = t;
                }
            }
        }

        vector<Event> events;
        for (int i = 0; i < N; ++i) {
            for (int j = i+1; j < N; ++j) {
                calculateIntersections(i, j, robots[i], robots[j], R, events);
            }
        }

        sort(events.begin(), events.end(), compareEvents);

        unordered_set<int> infected;
        infected.insert(0);

        for (const auto& e : events) {
            if (e.time > T) break;
            if (e.is_enter) {
                bool has_i = infected.count(e.i);
                bool has_j = infected.count(e.j);
                if (has_i != has_j) {
                    if (has_i) infected.insert(e.j);
                    else infected.insert(e.i);
                }
            }
        }

        vector<string> result;
        for (int i = 0; i < N; ++i) {
            if (infected.count(i)) {
                result.push_back(robots[i].name);
            }
        }
        sort(result.begin(), result.end());
        for (const auto& name : result) {
            cout << name << '\n';
        }
    }

    return 0;
}