BOJ 27847 - Cow-libi

BOJ 27847 - Cow-libi

USACO를 너무 오랜만에 손대다보니 문제를 제대로 해석하는 것조차 쉽지가 않다.

이벤트를 시간순으로 정렬할 때, 어떤 소가 $(x,y,t)$ 에 있었다면 $t$에 가장 가까운 이벤트 두개만 보고 그 이벤트에 도달 가능한지를 판단해주면 된다.

이분 탐색으로 찾아주자

왜냐면 $G$개의 입력 자체가 연속해서 이동할 수 있음이 보장되기 때문에 그 두개에만 제대로 갈 수 있어도 나머지 것들은 무조건 갈 수 있기 때문이다.

그 이벤트 두개에 도달 가능한 소는 innocent하지 않으므로 이 소들의 수를 세서 $N$에서 빼준 것이 정답이다.

void solve() {  
   int G, N;  
   cin >> G >> N;  
  
   vector<array<int, 3>> event;  
   for (int i = 0; i < G; i++) {  
      int x, y, t;  
      cin >> x >> y >> t;  
      event.pb({t, x, y});  
   }  
   sort(all(event));  
   for (int i = 0; i < G - 1; i++) {  
      if (event[i][0] == event[i + 1][0]) {  
         assert(event[i][1] == event[i + 1][1] && event[i + 1][2] == event[i][2]);  
      }  
   }  
  
   int ans = 0;  
   for (int i = 0; i < N; i++) {  
      int x, y, t;  
      cin >> x >> y >> t;  
  
      auto can = [&](int j) -> bool {  
         if (j < 0 || j >= G) return true;  
         int x_diff = (x - event[j][1]);  
         int y_diff = (y - event[j][2]);  
         int dist_diff = x_diff * x_diff + y_diff * y_diff;  
         int time_diff = abs(event[j][0] - t);  
         return dist_diff <= time_diff * time_diff;  
      };  
  
      const int inf = 1e9 + 1;  
      array<int, 3> key{int(t), inf, inf};  
      int j = ubi(event, key);  
      bool c = 1;  
      if (can(0) && can(j) && can(j - 1)) {  
         ans++;  
         debug(i);  
      }  
   }  
   cout << N - ans;  
}