BOJ 21342 - Flight Collision

BOJ 21342 - Flight Collision

set 을 잘 활용하는 시뮬레이션 느낌이다.

충돌이 같은 지점에서 세 개 이상 동시에 일어나지 않으므로 각 인접한 것들이 언제 충돌하는지 <거리, 속도, 충돌하는 인덱스들> 로 먼저 충돌하는 것부터 관리하고 먼저 충돌하는것부터 충돌시키고 $i, j,\ (i<j)$ 가 충돌했다면 $i$ 이전에 남아있는것과 $j$ 이후에 남아있는 것 두 개가 충돌한다면 다시 set에 넣어주면 된다.

<거리, 속도>으로 관리해야 시간을 정수로 다룰 수 있다. $\text{T}=\dfrac{D}{V}$

void solve() {
   int n;
   cin >> n;
   vi x(n), v(n);
   for (int i = 0; i < n; i++) cin >> x[i] >> v[i];

   vi removed(n);
   set<int> exist;
   for (int i = 0; i < n; i++) exist.insert(i);

   // <dist, velocity, i, j>
   auto cmp = [&](const array<int, 4> &a, const array<int, 4> &b) {
      if (a[0] * b[1] == b[0] * a[1]) return mp(a[2], a[3]) < mp(b[2], b[3]);
      return a[0] * b[1] < b[0] * a[1];
   };
   set<array<int, 4>, decltype(cmp)> col(cmp);
   for (int i = 0; i < n - 1; i++) {
      if (v[i] <= 0 && v[i + 1] >= 0) continue;
      int x_diff = x[i + 1] - x[i];
      int v_cur = v[i] - v[i + 1];
      if (v_cur <= 0) continue;
      int g = gcd(x_diff, v_cur);
      x_diff /= g, v_cur /= g;
      col.insert({x_diff, v_cur, i, i + 1});
   }

   while (sz(col)) {
      auto [dist, velocity, i, j] = *col.begin();
      col.erase(col.begin());
      if (removed[i] || removed[j]) continue;
      removed[i] = removed[j] = 1;
      exist.erase(i), exist.erase(j);
      auto it = exist.lower_bound(i);
      auto pit = it;
      if (it != exist.begin() && it != exist.end()) {
         pit--;
         int l = *pit, r = *it;

         int x_diff = x[r] - x[l];
         int v_cur = v[l] - v[r];
         if (v_cur <= 0) continue;
         int g = gcd(x_diff, v_cur);
         x_diff /= g, v_cur /= g;
         col.insert({x_diff, v_cur, l, r});
      }
   }
   cout << sz(exist) << endl;
   for (int i: exist) cout << i + 1 << ' ';
}