Cow-libi (USACO Silver 2023 February)

一道简单的二分查找题。

注意题意，有单独一头奶牛在给定的时间偷吃了所有的庄稼，同时每头奶年都给了一个不在场证明，现在要输出有多少头奶牛的不在场证明的确能证明他们的清白。

换句话说，就是需要判断哪些奶牛来不及从偷吃的时间地点走到不在场证明的时间地点，然后再回到下一个偷吃的时间地点。所以只需要处理两个相邻的偷吃时间地点就可以了，把所有偷吃时间地点按时间排序，然后二分查找，找到与不在场时间地点相邻的两个，就可以判断了。当然头尾要单独处理一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int G, N;
vector<pair<int,pi>> gardens;
int ans;
 
bool check(const pair<int,pi> &a, const pair<int,pi> &b) {
    long long dx = a.s.f - b.s.f;
    long long dy = a.s.s - b.s.s;
    long long dt = a.f - b.f;
    return dx * dx + dy * dy <= dt * dt;
}
 
int main() {
    cin >> G >> N;
    for(int i = 0; i < G; i++) {
        int x, y, t; 
        cin >> x >> y >> t;
        gardens.push_back({t, {x, y}});
    }
    sort(gardens.begin(), gardens.end());
 
    for (int i = 0; i < N; i++) {
        int x, y, t; 
        cin >> x >> y >> t;
        pair<int,pi> p = {t, {x, y}};
        auto it = lower_bound(gardens.begin(), gardens.end(), p);
        if (it != gardens.begin() && !check(*prev(it), p)) {
            ans++;
            continue;
        }
        if (it != gardens.end() && !check(p, *it))
            ans++;
    }
    cout << ans << endl;
    return 0;
}