AOJ 1139: Earth Observation with a Mobile Robot Team

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp

解法

2 台のロボットの距離が $R$ 未満になったり $R$ 以上になったりすることが発生する時刻をすべて列挙することを考えます。

ロボットの組を全探索します。ロボットが 2 台とも動いていると考えにくいので、一方に対するもう一方の相対的な位置の変化を考えると、この変化は同じく平面上の折れ線になります。

この折れ線を線分に分解し、それぞれの線分について中心が原点で半径 $R$ の円との交点を求めればよいですが、ロボットが近づいているのか離れているのかは交点の情報のみではわかりません。

そこで、線分と円の交点を求める関数自体は作らず、直線と円の交点を求める関数のみ作り 2 つの交点を直線が向いている順に並んでいるように返すと、そのうちどちらの点であるかでロボットが近づいているのか離れているのかがわかります。

ロボット対応する頂点を作り、現在距離 $R$ 以内にあるロボットの組に対応する頂点の間に辺を持つグラフを隣接行列で持ち、辺の有無を更新していくことを考えます。辺を新たに追加したときに一方のロボットのみがデータを記憶しているときのみ BFS をすると、BFS の回数が最大 $N$ 回となります。

時間計算量は $O(N ^ 3 + N ^ 2 T \log(N ^ 2 T))$ です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.00000001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  point operator *(double k){
    return point(x * k, y * k);
  }
  point operator /(double k){
    return point(x / k, y / k);
  }
  bool operator < (point P) const{
    return x < P.x || x == P.x && y < P.y;
  }
};
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double dot(point P, point Q){
  return P.x * Q.x + P.y * Q.y;
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
point projection(point P, line L){
  return L.A + vec(L) * dot(P - L.A, vec(L)) / abs(vec(L)) / abs(vec(L));
}
double point_line_distance(point P, line L){
  return abs(cross(L.A - P, vec(L))) / abs(vec(L));
}
struct circle{
  point C;
  double r;
  circle(point C, double r): C(C), r(r){
  }
};
vector<point> line_circle_intersection(line L, circle C){
  double d = point_line_distance(C.C, L);
  if (d > C.r){
    return vector<point>();
  }
  point P = projection(C.C, L);
  point D = vec(L) / abs(vec(L));
  double m = sqrt(C.r * C.r - d * d);
  vector<point> ans = {P - D * m, P + D * m};
  return ans;
}
int main(){
  while (true){
    int N, T;
    double R;
    cin >> N >> T >> R;
    if (N == 0 && T == 0 && R == 0){
      break;
    }
    vector<string> s(N);
    vector<point> P(N);
    vector<vector<double>> t(N, vector<double>(1));
    vector<vector<point>> v(N);
    for (int i = 0; i < N; i++){
      cin >> s[i];
      cin >> t[i][0] >> P[i].x >> P[i].y;
      while (t[i].back() != T){
        t[i].push_back(0);
        v[i].push_back(point());
        cin >> t[i].back() >> v[i].back().x >> v[i].back().y;
      }
    }
    vector<tuple<double, int, int, bool>> upd;
    for (int i = 0; i < N; i++){
      for (int j = i + 1; j < N; j++){
        if (dist(P[i], P[j]) < R){
          upd.push_back(make_tuple(0, i, j, true));
        }
        int cnt1 = v[i].size(), cnt2 = v[j].size();
        vector<tuple<double, point, int>> c;
        for (int k = 0; k < cnt1; k++){
          c.push_back(make_tuple(t[i][k], v[i][k], 0));
        }
        for (int k = 0; k < cnt2; k++){
          c.push_back(make_tuple(t[j][k], v[j][k], 1));
        }
        sort(c.begin(), c.end());
        int cnt = c.size();
        point v1(0, 0), v2(0, 0);
        vector<double> t2(cnt + 1);
        vector<point> dv(cnt);
        for (int k = 0; k < cnt; k++){
          t2[k] = get<0>(c[k]);
          if (get<2>(c[k]) == 0){
            v1 = get<1>(c[k]);
          }
          if (get<2>(c[k]) == 1){
            v2 = get<1>(c[k]);
          }
          dv[k] = v2 - v1;
        }
        t2[cnt] = T;
        point D = P[j] - P[i];
        for (int k = 0; k < cnt; k++){
          if (abs(dv[k]) > EPS){
            point D2 = D + dv[k] * (t2[k + 1] - t2[k]);
            line L(D, D2);
            if (point_line_distance(point(0, 0), L) < R){
              circle C(point(0, 0), R);
              vector<point> I = line_circle_intersection(L, C);
              for (int l = 0; l < 2; l++){
                double d = dot(I[l] - D, D2 - D) / dist(D, D2);
                if (- EPS < d && d < dist(D, D2) + EPS){
                  upd.push_back(make_tuple(t2[k] + d / abs(dv[k]), i, j, l == 0));
                }
              }
            }
            D = D2;
          }
        }
      }
    }
    sort(upd.begin(), upd.end());
    int M = upd.size();
    vector<vector<bool>> E(N, vector<bool>(N, false));
    vector<bool> used(N, false);
    used[0] = true;
    for (int i = 0; i < M; i++){
      int a = get<1>(upd[i]);
      int b = get<2>(upd[i]);
      bool e = get<3>(upd[i]);
      E[a][b] = e;
      E[b][a] = e;
      if (e && (used[a] ^ used[b])){
        queue<int> Q;
        if (!used[a]){
          used[a] = true;
          Q.push(a);
        }
        if (!used[b]){
          used[b] = true;
          Q.push(b);
        }
        while (!Q.empty()){
          int v = Q.front();
          Q.pop();
          for (int j = 0; j < N; j++){
            if (E[v][j] && !used[j]){
              used[j] = true;
              Q.push(j);
            }
          }
        }
      }
    }
    vector<string> ans;
    for (int i = 0; i < N; i++){
      if (used[i]){
        ans.push_back(s[i]);
      }
    }
    sort(ans.begin(), ans.end());
    int cnt = ans.size();
    for (int i = 0; i < cnt; i++){
      cout << ans[i] << endl;
    }
  }
}